円周率に近似できる分数

円周率に近似できる分数

締め切りが 201701/31 10:00 AM なので，その 1 分後に投稿されるように予約

設問

分母、分子ともに整数の分数を使って円周率に近似することを考えます。
小数第 n 位までが円周率と一致するもののうち、分母が最小のものをπ(n)とします。

例えば、n = 1 のとき、π(1) = 19/6 = 3.166…、
n = 2 のとき、π(2) = 22/7 = 3.1428…、
n = 3 のとき、π(3) = 245/78 = 3.14102…
となります。

標準入力から n が与えられたとき、π(n) の分母を求め、標準出力に出力してください。
なお、nは11以下の正の整数とします。
参考）小数点以下11桁までの円周率は以下の通りです。
3.14159265358

【入出力サンプル】
標準入力
2

標準出力
7

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

素直に書けばよいが，R ならではの落とし穴があった。
repeat ループは本来は for (denominator in 1:pow10n) とするのであるが，R の for ループは変域を前もって配列として確保するので，n = 1e11 の場合のようなサイズ(1:1e11）のサイズを取ろうとするとメモリー管理上不都合が生じる。そのため，本来は遅い（？）repeat ループにした。
また，評価システムの実行時間制限（1 秒以内）に沿うために不本意ながら，denominator の変域を制限した。
もちろん，Java などを用いればそんな小細工は不要である。

π = function(n) {
    pow10n = 10^n
    aproxPI = floor(pi* pow10n)
    denominator = ifelse(n < 10, 0, 165000)
    repeat {
        denominator = denominator+1
        if (denominator > pow10n) break
        if (any(floor(((floor(denominator*pi)+(-1:1))/denominator)*pow10n) == aproxPI)) break
    }
    cat(denominator)
}
π(1) # 6
π(2) # 7
π(3) # 78
π(4) # 106
π(5) # 113
π(6) # 113
π(7) # 27678
π(8) # 32763
π(9) # 33102
π(10) # 165849
π(11) # 265381

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

Java の場合

static int PI(int n) {
    double aproxPI, x, PI;
    double [] y = {-2.0, -1.0, 0.0, 1.0, 2.0};
    double pow10 = Math.pow(10,  n);
    int denominator;
    int i;
    boolean ok;
    aproxPI = Math.floor(Math.PI*pow10)/pow10;
    for (denominator = 1; denominator
        ok = false;
        for (i = 0; i < 5; i++) {
            x = y[i]+Math.floor(denominator*Math.PI);
            PI = Math.floor(x/denominator*pow10)/pow10;
            if (PI == aproxPI) {
                ok = true;
                break;
            }
        }
        if (ok) {
            break;
        }
    }
    return denominator;
}

撤去作業の果てに現れる数列

撤去作業の果てに現れる数列
締め切りが 2017/01/27 10:00 AM なので，その 1 分後に投稿されるように予約

【概要】
0から始まる無限に続く整数の列がスタートです。
その列から「素数の ni 個前を撤去する」という操作を繰り返します。
操作の結果得られる列の、最初の10項をコンマ区切りで出力してください。

【詳細】
{ ni } を表す文字列が3 2 3のように標準入力からやってきます。空白区切りの 10進数 です。
この入力の場合は、下表のように列は変化します：

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,...
↓ n1=3 なので、0,2,4,8,10,14,16,20,26,28,...などを撤去する。
1,3,5,6,7,9,11,12,13,15,17,18,19,21,22,23,24,25,27,29,...
↓ n2=2 なので、1,5,7,11,13,17,21,25,29,35,37,41,...などを撤去する。
3,6,9,12,15,18,19,22,23,24,27,30,31,32,33,36,39,42,43,46,...
↓ n3=3 なので、12,18,24,36,42,48,54,...などを撤去する。
3,6,9,15,19,22,23,27,30,31,32,33,39,43,46,47,49,52,53,57,...

結果、最初の 10項は
3,6,9,15,19,22,23,27,30,31
となるので、これを出力すればよいというわけです。

【例】
入力　　　 出力
3 2 3　　　3,6,9,15,19,22,23,27,30,31
2 3　　　　4,6,7,10,12,13,16,18,20,22

【補足】
 • 不正な入力に対処する必要はありません。
 • 入力に含まれる数は、1〜100 の整数です。
 • 入力に含まれる数字の数は、1〜20個 です。
 • 素数の判定は、ライブラリがあればそれを利用して構いません。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

f = function(x) {
    mx = 1e+05 # 十分に広い範囲の素数表を作る（プログラムは十分に速いので大きくても心配ない）
    tbl = 1:mx
    tbl[1] = 0
    for (i in 2:floor(sqrt(mx))) {
        if (tbl[i]) {
            mx2 = mx%/%i
            tbl[2:mx2 * i] = 0
        }
    }
    prime = tbl[tbl != 0] # 素数表
    a = 0:max(prime)      # 0 から素数表の最大素数までの整数列
    for (n in x) {        # 入力されるそれぞれの ni について
        b = a %in% prime  # 整数列中の素数がある位置
        s = which(b) - n  # 位置の n 個前
        s = s[s > 0]      # 位置を範囲内に限る
        a = a[-s]         # n 個前の数を除いた物を新たな整数列とし，次の n での処理に廻す
    }
    cat(a[1:10], sep=",")
}
x = c(3, 2, 3)
f(x) # 3,6,9,15,19,22,23,27,30,31
f(c(1,4,2,2,2,4,2,1,3,3,1,1,2,2,2,1,3,4,3,2)) # 0,1260,1327,1328,1329,1330,1331,1332,1333,1339
f(c(3,3,6,4,3,2,3,1,1,2,2,3,6,5,4,3,3,3,4,3)) # 1,1307,1313,1327,1328,1329,1330,1331,1332,1333
f(c(2,1,1,2,1,2,2,3,2,1,2,2,1,1,1,2,1,1,2,2)) # 2,1129,1130,1131,1134,1327,1328,1329,1330,1331
f(c(1,3,2,1,1,2,5,4,3,5,4,4,4,3,2,2,2,5,3,3)) # 3,61,1123,1328,1330,1916,2287,2470,2477,2480
f(c(1,4,2,1,1,3,2,1,3,4,1,1,3,1,4,2,2,2,4,2)) # 892,1262,1327,1332,1381,2447,2477,2478,2971,3023
f(c(5,2,2,1,3,4,2,4,4,1,5,2,5,2,2,5,5,3,4,1)) # 1669,2166,2557,2971,2973,3271,3739,3745,3787,3953
f(c(5,2,2,1,1,4,2,4,6,5,7,7,3,2,3,2,4,2,1,3)) # 513,1327,1329,1381,1382,1385,1631,1675,2171,3271
f(c(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)) # 1129,1130,1327,1328,1329,1330,1331,1332,1333,1334
f(c(1,100,1,100,1,100,1,100,1,100,1,100,1,100,1,100,1,100,1,100)) # 169,200,204,209,214,354,356,701,702,763
f(c(100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100)) # 2,28,41,94,145,166,167,184,187,209
f(c(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)) # 327,480,711,993,1263,1382,1735,2477,2499,3313
f(c(20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1)) # 85,224,271,272,274,275,292,294,295,296

整数剰余計算の定義

ドツボにはまった

R では -5 %% 6 は 1 になるが，
AWK や Java では -5 % 6 は -5 になる。

連続する整数の各桁の数字の和

連続する整数の各桁の数字の和

締め切りが 2017/01/24 10:00 AM なので，その 1 分後に投稿されるように予約

設問

a, b という2つの正の整数が与えられたとき、aからbまでの連続する整数について、各桁の数字の和を求めることを考えます。

例えば、a = 7, b = 16のとき、7, 8, 9, 10, 11, 12, 13, 14, 15, 16の各桁の数字を足して、
7 + 8 + 9 + 1 + 0 + 1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 = 52
となります。

また、a = 12, b = 19のときは、
1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 + 1 + 7 + 1 + 8 + 1 + 9 = 52
となり、同じ値になります。

このように、同じ値が得られる正の整数 a, b のペアは一つとは限りません。
標準入力から a, b の値がスペースで区切って与えられたとき、与えられた a, b の範囲に重なる（両端を含む）ようなペアがいくつあるかを求め、標準出力に出力してください。
（a = 21, b = 28 なども同じ値になりますが、7〜16 と 21〜28は重なる範囲がないため対象外です。）

例えば、上記の a = 7, b = 16 の場合、a = 12, b = 19 の他にも a = 3, b = 13 の場合があり、合わせて2通りですので、以下のように出力します。

【入出力サンプル】
標準入力
7 16

標準出力
2

※a, b は32ビット整数の範囲で、0 < b - a < 2500 を満たす数が与えられるものとします。

========================================================================================

R で書くと実行時間制限にかかるので，Java に書き直して O.K.
ただ，Java だと，処理系によりメモリーオーバーになるので小細工が必要になる

R によるプログラム

f = function(a, b, range=8000) {
    if (b-a < 1000) {
        max = b+2*(b-a)
        min = 2
    } else {
        max = b+range
        min = a-range
    }
    x = integer(max)
    x[min-1] = sum(as.numeric(unlist(strsplit(as.character(min-1), ""))))
    for (i in min:max) {
        x[i] = x[i-1]+sum(as.numeric(unlist(strsplit(as.character(i), ""))))
    }
    s = x[b]-x[a-1]
    count = 0
    for (i in a:(b-1)) {
        for (j in min:a) {
            if (x[i]-x[j-1] == s) {
                count = count+1
            }
        }
    }
    for (i in (a+1):b) {
        for (j in i:max) {
            if (x[j]-x[i-1] == s) {
                count = count+1
            }
        }
    }
    count
}
f(7, 16) # 2
f(100, 150) # 15
f(2000, 2017) # 3
f(12345678, 12347654)) # 167
f(123456789, 123459012) # 294

2 つの二重ループを outer 関数に置き換え，制約範囲を限ると，テストシステムでも 1 秒以内に収まった（テストデータをクリアーするということに限る。一般解ではない）。

f = function(a, b, range=2500) {
    if (b-a < 1000) {
        max = b+2*(b-a)
        min = 2
    } else {
        max = b+range
        min = a-range
    }
    x = integer(max)
    x[min-1] = sum(as.integer(strsplit(as.character(min-1), "")[[1]]))
    for (i in min:max) {
        x[i] = x[i-1]+sum(as.integer(strsplit(as.character(i), "")[[1]]))
    }
    s = x[b]-x[a-1]
    res1 = outer(x[a:(b-1)], x[min:a-1], "-")
    res2 = outer(x[b:max], x[(a+1):b-1], "-")
    sum(res1 == s)+sum(res2 == s)
}

========================================================================================

Java によるプログラム

import java.util.*;
import java.util.regex.*;

class Main {

    public static void main(String[] args) {
        System.out.println(f(7, 16));
        System.out.println(f(100, 150));
        System.out.println(f(2000, 2017));
        System.out.println(f(12345678, 12347654));
        System.out.println(f(123456789, 123459012));
     }

    static int digitsSum(int n) {
        int sum = 0;
        while (n != 0) {
            sum += n%10;
            n /= 10;
        }
        return sum;
    }

    static int f(int a, int b) {
        int max, min, i, j, s, count = 0;
        int range = 8000;
        if (b-a < 1000) {
            max = b+2*(b-a);
            min = 2;
        } else {
            max = b+range;
            min = a-range;
        }
        int [] x = new int[max-min+3];
        x[1] = digitsSum(min-1);
        for (i = min; max >= i; i++) {
            x[i-min+2] = x[i-1-min+2]+digitsSum(i);
        }
        s = x[b-min+2]-x[a-1-min+2];
        count = 0;
        for (i = a-min+2; b-1-min+2 >= i; i++) {
            for (j = min-min+2; a-min+2 >= j; j++) {
                if (x[i]-x[j-1] == s) {
                    count++;
                }
            }
        }
        for (i = a+1-min+2; b-min+2 >= i; i++) {
            for (j = i; max-min+2 >= j; j++) {
                if (x[j]-x[i-1] == s) {
                    count++;
                }
            }
        }
        return count;
    }
}

破局噴火の発生確率

http://www.nikkei-science.com/?p=52031

> 本誌に掲載した破局噴火の記事がウェブ上で話題になっています。破局噴火が国内のいずれかの火山で今後100年間に起きる確率は約1％であることを紹介したうえで，「期間を100倍に延ばすと1万年間で確率100％になる」としたところが数学的におかしいとの指摘です。破局噴火は膨大な量のマグマが放出される非常に大規模な噴火です。もし今後100年間起きなかった場合，100年分，地下深部から新たなマグマが供給されるので，その先の100年間に破局噴火が起きる確率は1％より高くなります。さらにその先はもっと高くなります。つまり破局噴火の発生確率はサイコロの特定の目が出る確率などとは違って，長い時間の発生確率を考えるほど上がり，その上がり方も急になっていきます。日本列島の火山活動の歴史を考えると，次の破局噴火は1万年よりもかなり前の時期に確実に起こるとみられています。「期間を100倍に延ばすと確率100％」というのは，いわば非常に甘い見積もりなわけです

確率というのは「在る事象が起きる確からしさ」で0〜1の値で表されるものです。

件の記事について言えば，

> 「期間を100倍に延ばすと確率100％」というのは，いわば非常に甘い見積もりなわけです

というのは，「期間を200倍に延ばすと確率は200%になる」ということをいっているわけで，そんなばかなということにだれも気づくでしょう。

 

ここでいっている「確率」は「期待値」に相当するものでしょう。

つまり，「今後100年間に起きる確率は約1％」というのは，「今後100年間に起きる確率は約1/100回起きる」

比例で言えば，「今後10000年間に起きる確率は約（1/100）×(10000/100)＝1回起きる」つまり，1万年あたりは1回起きるということ。

20000年には2回ということ。

 

確率と期待値を混同してはいけない。

というか，「100年間に起きる確率は約1％」という言い方自体，確率論とは異なるものだと言うこと。

少なくとも，ここで言っている「確率」と，「サイコロを振って1の目が出る確率は1/6」というときの確率は全く違うと言うこと。

単調増加で単調減少な数

単調増加で単調減少な数
2017年1月13日（金）10:00AMが締め切りなので，その 1 分後に投稿されるように予約

【概要】
たとえば，179 のような数のことを「10 進数で狭義単調増加な数」と呼ぶことにします。
つまり，各桁を見ると狭義単調増加列になっています。

逆に，8631 のような数のことを「10 進数で狭義単調減少な数」と呼ぶことにします。
つまり，各桁を見ると狭義単調減少列になっています。

さて，a 進数で狭義単調増加，b 進数で狭義単調減少な数のうち，もっとも大きな数を求めるプログラムを書いてください。

【入出力】
入力は
5 6
こんな感じで標準入力から来ます。
スペース区切りで２つの10進数が並んでいます。
スペースの前が先程の a，つまりa進数で表記すると狭義単調増加になります。
スペースの後は先程の b，つまりb進数で表記すると狭義単調減少になります。

出力は，条件を満たす値を 10 進数で。先ほどの入力なら，19 を出力すると正解です。

【例】
入力　　　　　　出力    a進数    b進数
5    6    19    34    31
6    11    101    245    92
4    3    7    13    21

【補足】
•　不正な入力に対処する必要はありません。
•　長さ 1 でも狭義単調増加列になります。
•　a も b も，2 以上 16 以下です。

==========================

bc = function(p) { # 要素の組み合わせを行列として求める
    retval = matrix(0, nrow = 2^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (2^p/2^n)), rep(1, (2^p/2^n))), length = 2^p)
    }
    retval
}

is.ok = function(u, b) { # 10 進数の u が，「「b 進数で狭義単調減少な数」か
    v = NULL
    repeat {
        v = c(v, u %% b)
        u = u %/% b
        if (u == 0) break
    }
    all(diff(v) > 0)
}

is.ok = function(u, b) { # 順次判定すれば，効率がよいので，こちらを使う
    prev = u %% b
    u = u %/% b
    repeat {
        if (u == 0) {
            return(TRUE)
        }
        v = u %% b
        if (prev >= v) { # 狭義減少になっていない桁があると FALSE
            return(FALSE)
        }
        u = u %/% b
        prev = v
    }
}

f = function(a, b) {
    mx.b = sum((b-1):1 * b ^ (0:(b-2))) # 「b 進数で狭義単調減少な数」の最大値
    w = a ^ (0:(a-2)) # a 進数の各桁の重み（要素1が最下位桁であるように逆順に保存）
    mx =  0 # 求める数（最大値）
    for (least in (a-1):1) { # 「a 進数で狭義単調増加な数」
        x = least:1 # 最下位桁が least，最上位桁が 1
        if (length(x) == 1) {
            y = 1
        } else { # 可能なすべての狭義単調増加な数の各桁
            y = apply(cbind(1, bc(least-1)), 1, function(i) x[i==1])
        }
        for (i in 1:length(y)) {
            z = y[[i]]
            u = sum(z * w[1:length(z)]) # 10 進数に変換
            if (length(z) == 1 && u > mx && is.ok(u, b)) { #「b 進数で狭義単調減少な数」か
                mx = u # 今までで一番大きければ記録
            } else if (mx.b >= u && u > mx && is.ok(u, b)) {
                mx = u
            }
        }
    }
    cat(mx) # 結果を表示
}

system.time(f(5, 6)) # 19
system.time(f(15, 16)) # 15571062
system.time(f(13, 16)) # 16558437
system.time(f(2, 16)) # 1
system.time(f(2, 2)) # 1
system.time(f(3, 2)) # 2
system.time(f(7, 11)) # 1266
system.time(f(11, 7)) # 2276
system.time(f(11, 10)) # 3210  7.252 sec.
system.time(f(16, 2)) # 2
system.time(f(16, 15)) # 35806
system.time(f(16, 16)) # 15
system.time(f(16, 13)) # 363743

KPTE

KPTE

締め切りが 2017/01/12 10:00 AM なので，その 1 分後に投稿されるように予約

仕様
標準入力

・ユーザー名,絵文字1,絵文字2,・・・,絵文字N というフォーマットのデータが複数行入力されます
・ユーザー名は [a-z] から構成される文字列です
・絵文字は [a-z] から構成される文字列からなります

例

usera,emojia,emojib,emojic
userb,emojia,emojib,emojib

標準出力

・ユーザー名,その人が利用している絵文字の種類 というのデータが複数行出力されます
・利用文字種が多い順に出力する（利用文字種が同じ入力データは存在しないものとする）

例

usera,3
userb,2

その他の仕様

・標準入力の末尾には改行があります
・標準出力の末尾に改行をつけてください
・標準入力の仕様で説明した内容以外の入力は行われません（不正入力に対するチェックは不要）

Input

tanaka,question,smoking,oden,wedding,metal,cl,three,sparkle,new
suzuki,mushroom,anchor,pizza,notes
sato,grapes,watermelon,jp,tennis,hammer
honda,ox,watch,euro
takahashi,cupid

Output

tanaka,9
sato,5
suzuki,4
honda,3
takahashi,1

==========================

f = function(s) {
    user = x = NULL
    for (i in s) {
        s2 = unlist(strsplit(i, ","))
        user = c(user, s2[1])
        x = c(x, length(table(s2[-1])))
    }
    o = order(x, decreasing=TRUE)
    user = user[o]
    x = x[o]
    for (i in seq_along(user)) {
        cat(sprintf("%s,%d\n", user[i], x[i]))
    }
}
f(readLines(file("stdin", "r")))

魔方陣で最大値？

魔方陣で最大値？

締め切りが 2017/01/09 10:00 AM なので，その 1 分後に投稿されるように予約

設問

４×４の魔方陣は1〜16までの数字を１度ずつ使ったもので、以下の左図のようなものがあります。



魔方陣は縦、横、斜めのすべての列について、その和が等しいという特徴があります。

魔方陣において、左上のマスからスタートして、右か下の隣り合うマスへの移動を繰り返して最短距離で右下のマスまで移動します。
このとき、経由したマスの数の和が最大になるような移動経路を考えます。
上図の魔方陣の場合、上図右のように移動すると和は 67 になります。

標準入力から整数 n が与えられたとき、４×４のすべての魔方陣に対してこのような移動経路を求め、その和が n になる魔方陣の個数を求め、標準出力に出力してください。

４×４の魔方陣は全部で7,040個存在することが知られています。
その中で、n=54のときは以下の2パターンに回転や鏡像を含めたものが全部で8通りありますので、以下のような入出力になります。



【入出力サンプル】
標準入力
54

標準出力
8

=================

R で書くと制限時間（1 秒）に引っかかるので，AWK で書いた（Java でも C でもよいけど）
魔方陣の生成部分はネットを参考に

func = function(num) {
    route = function(table) {
        sums = integer(20)
        sums[1] = table[1, 2] + table[1, 3] + table[1, 4] + table[2, 4] + table[3, 4]
        sums[2] = table[1, 2] + table[1, 3] + table[2, 3] + table[2, 4] + table[3, 4]
        sums[3] = table[1, 2] + table[1, 3] + table[2, 3] + table[3, 3] + table[3, 4]
        sums[4] = table[1, 2] + table[1, 3] + table[2, 3] + table[3, 3] + table[4, 3]
        sums[5] = table[1, 2] + table[2, 2] + table[2, 3] + table[2, 4] + table[3, 4]
        sums[6] = table[1, 2] + table[2, 2] + table[2, 3] + table[3, 3] + table[3, 4]
        sums[7] = table[1, 2] + table[2, 2] + table[2, 3] + table[3, 3] + table[4, 3]
        sums[8] = table[1, 2] + table[2, 2] + table[3, 2] + table[3, 3] + table[3, 4]
        sums[9] = table[1, 2] + table[2, 2] + table[3, 2] + table[3, 3] + table[4, 3]
        sums[10] = table[1, 2] + table[2, 2] + table[3, 2] + table[4, 2] + table[4, 3]
        sums[11] = table[2, 1] + table[2, 2] + table[2, 3] + table[2, 4] + table[3, 4]
        sums[12] = table[2, 1] + table[2, 2] + table[2, 3] + table[3, 3] + table[3, 4]
        sums[13] = table[2, 1] + table[2, 2] + table[2, 3] + table[3, 3] + table[4, 3]
        sums[14] = table[2, 1] + table[2, 2] + table[3, 2] + table[3, 3] + table[3, 4]
        sums[15] = table[2, 1] + table[2, 2] + table[3, 2] + table[3, 3] + table[4, 3]
        sums[16] = table[2, 1] + table[2, 2] + table[3, 2] + table[4, 2] + table[4, 3]
        sums[17] = table[2, 1] + table[3, 1] + table[3, 2] + table[3, 3] + table[3, 4]
        sums[18] = table[2, 1] + table[3, 1] + table[3, 2] + table[3, 3] + table[4, 3]
        sums[19] = table[2, 1] + table[3, 1] + table[3, 2] + table[4, 2] + table[4, 3]
        sums[20] = table[2, 1] + table[3, 1] + table[4, 1] + table[4, 2] + table[4, 3]
        max(sums + table[1, 1] + table[4, 4]) == num
    }

    table = matrix(0, 4, 4)
    used = logical(16)
    count = 0
    for (a in 1:13) {
        used[a] = TRUE
        for (d in (a + 1):15) {
            used[d] = TRUE
            for (m in (d + 1):16) {
                p = 34 - a - d - m
                if (p < a) break
                if (p > 16) next
                if (used[p]) next
                if (p == m) next
                used[m] = used[p] = TRUE
                for (f in 1:16) {
                    if (used[f]) next
                    k = 34 - a - f - p
                    if (k < 1) break
                    if (k > 16) next
                    if (used[k]) next
                    if (f == k) next
                    used[f] = used[k] = TRUE
                    for (b in 1:16) {
                        if (used[b]) next
                        c = 34 - a - b - d
                        if (c < 1) break
                        if (c > 16) next
                        if (used[c]) next
                        if (b == c) next
                        used[b] = used[c] = TRUE
                        for (g in 1:16) {
                            if (used[g]) next
                            j = 34 - d - g - m
                            if (j < 1) break
                            if (j > 16) next
                            if (used[j]) next
                            if (j == g) next
                            o = 34 - c - g - k
                            if (o < 1) break
                            if (o > 16) next
                            if (used[o]) next
                            if (o == g || o == j) next
                            n = 34 - b - f - j
                            if (n > 16) break
                            if (n < 1) next
                            if (used[n]) next
                            if (n == g || n == j || n == o) next
                            used[g] = used[j] = used[o] = used[n] = TRUE
                            for (e in 1:16) {
                                if (used[e]) next
                                h = 34 - e - f - g
                                if (h < 1) break
                                if (h > 16) next
                                if (used[h]) next
                                if (h == e) next
                                i = 34 - a - e - m
                                if (i < 1) break
                                if (i > 16) next
                                if (used[i]) next
                                if (i == e || i == h) next
                                l = 34 - d - h - p
                                if (l > 16) break
                                if (l < 1) next
                                if (used[l]) next
                                if (l == e || l == h || l == i) next
                                table[1, 1] = a
                                table[1, 2] = b
                                table[1, 3] = c
                                table[1, 4] = d
                                table[2, 1] = e
                                table[2, 2] = f
                                table[2, 3] = g
                                table[2, 4] = h
                                table[3, 1] = i
                                table[3, 2] = j
                                table[3, 3] = k
                                table[3, 4] = l
                                table[4, 1] = m
                                table[4, 2] = n
                                table[4, 3] = o
                                table[4, 4] = p
                                table2 = table[, 4:1]
                                table3 = t(table)
                                table4 = table3[, 4:1]
                                table5 = t(table2)
                                table6 = table5[, 4:1]
                                table7 = t(table4)
                                table8 = table7[, 4:1]
                                ans = sum(route(table), route(table2), route(table3), route(table4), route(table5),
                                    route(table6), route(table7), route(table8))
                                count = count + ans
                            }
                            used[g] = used[j] = used[o] = used[n] = FALSE
                        }
                        used[b] = used[c] = FALSE
                    }
                    used[f] = used[k] = FALSE
                }
                used[m] = used[p] = FALSE
            }
            used[d] = FALSE
        }
        used[a] = FALSE
    }
    count
}

三角形の個数

初夢で見た問題

円周を n 等分する点を結んでできる三角形の個数を求めよ。

回転や裏返しで同じになる三角形は別々には数えない。

n = 10 のときの三角形の個数は 8 個

n = 12345 のときの三角形の個数を求めよ（12699919 個である）

解答例は，この記事のコメントで。

ポーランド記法から変換して不要な括弧を除去

ポーランド記法から変換して不要な括弧を除去

締め切りが 2017/01/03 10:00 AM なので，その 1 分後に投稿されるように予約

設問

ポーランド記法や逆ポーランド記法を使うと、括弧を使わなくても演算を一意に表記できます。
例えば、通常の式(中置記法)で

(1 + 3) * (4 + 2)

のような場合、括弧を省略すると演算順序が変わってしまいますが、ポーランド記法で

* + 1 3 + 4 2

のように記述すると、括弧は不要です。

今回は数字は1種類のみ、演算子は「+」「*」の2種類だけを考えます。
これらの数字と演算子で構成され、数字が入る場所が n 箇所あるポーランド記法の式をすべて考え、
それらを通常の式(中置記法)に変換した上で、不要な（演算順序に影響がない）括弧を除去します。
（「+」よりも「*」の方が、演算の優先度が高い前提です）
この作業を行ったとき、括弧のペアがいくつ残るかを求めます。

例えば、n = 3 のときは以下の8パターンがあり、必要な括弧は全部で2ペアです。
（数字は何でも構いませんが、例えば「5」を使うと以下のようになります。）

+ + 5 5 5 => 5 + 5 + 5
+ * 5 5 5 => 5 * 5 + 5
* + 5 5 5 => (5 + 5) * 5 ← ペアが1つ
* * 5 5 5 => 5 * 5 * 5
+ 5 + 5 5 => 5 + 5 + 5
+ 5 * 5 5 => 5 + 5 * 5
* 5 + 5 5 => 5 * (5 + 5) ← ペアが1つ
* 5 * 5 5 => 5 * 5 * 5

標準入力から整数 n が与えられるとき、括弧のペアの総数を求め、標準出力に出力してください。
ただし、nは15以下の正の整数とします。

================================================

いつものように，n が小さいときの解から規則性を見いだす

f = function(n) {
    unit = factorial(2 * (n - 1))/factorial(n - 1)/factorial(n)
    Sum = 0
    for (i in 0:7) {
        if (n >= 2 * i + 1)
            Sum = Sum + choose(n, 2 * i + 1)*unit*i
    }
    Sum
}
f(15)

ジェット機をプレゼント

ジェット機をプレゼント

締め切りが 2017/01/01 12:00 AM なので，その 1 分後に投稿されるように予約

設問
イントロ

12月誕生日の方、おめでとうございます！
今月誕生日を迎える方に、特別な問題を用意しました。
上手くコードを書いて正解すれば、素敵なプレゼントがもらえるかもしれませんよ！
がんばって、問題を解くコードを書いてください。

問題

あなたは誕生日プレゼントとして、ジェット機をもらえることになりました。
もらえるジェット機は、組み立て式です。胴体、右翼、左翼の部品を組み合わせると、1つのジェット機が作れます。
各部品は、整数で表されており、胴体が0、右翼が1、左翼が2という値です。
部品を組み合わせて、最大何機のジェット機を組み立てられるか、計算するプログラムを書いてください。

例

以下、入力の例です。
数字は標準入力から、改行で区切られた文字として渡されます。

0
1
0
2
1
0
2
1

以下、出力の例です。「0, 1, 2」の組みが最大2個作れるので、「2」となります。
答えは、以下のように標準出力に出力してください。

2

===============

問題は大げさだけれども，要するに0, 1, 2 の度数分布を調べ，最小のものを解答するということ。
R だと min と table だけで終わる。

cat(min(table(scan(file("stdin", "r")))))