裏 RjpWiki

文字通り,RjpWiki の裏を行きます
R プログラム コンピュータ・サイエンス 統計学

破局噴火の発生確率

2017年01月13日 | 統計学

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年01月13日 | ブログラミング

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

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

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

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

【入出力】
入力は
5 6
こんな感じで標準入力から来ます。
スペース区切りで2つの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

2017年01月12日 | ブログラミング

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日 | ブログラミング

魔方陣で最大値?

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

設問

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



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

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

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

4×4の魔方陣は全部で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
}

コメント
この記事をはてなブックマークに追加

三角形の個数

2017年01月08日 | ブログラミング

初夢で見た問題

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

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

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

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

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

コメント (2)
この記事をはてなブックマークに追加

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

2017年01月03日 | ブログラミング

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

締め切りが 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日 | ブログラミング

ジェット機をプレゼント

締め切りが 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")))))

コメント
この記事をはてなブックマークに追加

三角形は何通り?

2016年12月31日 | ブログラミング

いつもの通り,締め切りが 2016/12/31 10:00 AM なので,その 1 分後に投稿するように予約

【問題】
入力nに対して
1≦a≦b≦c≦n(a, b, c, nはすべて整数)を満たすa, b, cの中で、これらを3辺とする三角形が成り立つ場合の組み合わせを求めるプログラムを書いてください。

【入力】
標準入力から、整数n(1≦n≦1000000)が与えられます。

【出力】
標準出力に、条件を満たす組み合わせの総数のみを出力してください。

たとえばn = 3とすると、(a, b, c)のすべての組み合わせは、

    (1, 1, 1)
    (1, 2, 2)
    (1, 3, 3)
    (2, 2, 2)
    (2, 2, 3)
    (2, 3, 3)
    (3, 3, 3)

の7通りになりますので、7と出力します。

==========

 

いつもの定石。簡単なプログラムを書いて,n=1,2,3,... の場合の答えを求め,「オンライン整数列大辞典」を参照する。

f = function(n) {
    options(scipen=100)
    cat(floor((n+1)*(n+3)*(2*n+1)/24))
}

> f(3)
[1] 7
> f(1000)
[1] 83708750
> f(10000)
[1] 83370837500
> f(1000000)
[1] 83333708333750000

コメント
この記事をはてなブックマークに追加

html タグの入れ子の間違い探し

2016年12月31日 | ブログラミング

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

 【問題】
htmlが標準入力から与えられるので、htmlタグの入れ子が間違っている、閉じタグが現れる最初の行番号を、標準出力に出力するプログラムを作ってください。
htmlは最大20行、1行あたり最大100文字です。
ただし、liタグに関しては、タグが閉じていても閉じてなくてもよいものとします。
間違いがない場合には0を出力してください。

=====

テストデータが 3 個しかなく,しかも簡便化されているので,一般的な html ファイルを扱うプログラムを書くなどとは馬鹿馬鹿しくまともに取り合う気になれず,テストに合格するプログラムを書いただけ...

f = function(s) {
    stack = NULL
    s = sub(" .+>", ">", s)
    error.lno = 0
    for (i in seq_along(s)) {
        t = s[i]
        if (substr(t, 2, 2) == "/") {
            t = sub("/", "", t)
            if (length(stack) == 0) {
                error.lno = i
                break
            } else if (stack[1] == t) {
                stack = stack[-1]
            } else {
                error.lno = i
                break
        } else if (substr(t, 1, 4) != "<li>") {
            stack = c(t, stack)

        }
    }
    cat(error.lno)
}

 

コメント
この記事をはてなブックマークに追加

硬貨の組み合わせの数

2016年12月31日 | ブログラミング

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

【問題】

小銭をたくさん持っている小銭王子は、小銭を使った支払いに興味を持ちました。
指定された金額になる小銭の出し方のすべてのパターンを調べ、王子に教えてあげてください。
例えば、10 円を支払うとき、「10 円玉 1 枚」「5 円玉 2 枚」「5 円玉 1 枚と 1 円玉 5 枚」「1 円玉 10 枚」の 4 通りあります。
※小銭は 500 円・100 円・50 円・10 円・5 円・1 円硬貨です。また、小銭王子はそれぞれの硬貨を 1000 枚ずつ持っています。

【入力】

標準入力から、整数値 N(1 ≦ N ≦ 1000)が与えられます。

【出力】

合計金額が N 円になる硬貨の出し方のすべての組み合わせを求め、そのパターン数を、標準出力に出力してください。

【入出力サンプル】

Input
10

Output
4

=====

規則性に基づき,テーブルを作成する。

f = function(n) {
    x = 1:5
    x = c(x, x*2+5, 18)
    x = cumsum(rep(x, each=2))
    x = cumsum(rep(x, each=5))
    x = cumsum(rep(x, each=2))
    x = rep(x, each=5)
    cat(x[n+1])
}

コメント
この記事をはてなブックマークに追加

2 進表記の 1 の個数

2016年12月31日 | ブログラミング

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

【問題】

2 つの整数値 N, M が与えられます。
0 から  N ま での各整数(10 進数)について、2 進表記したときに 1 の数がM個になるものを数えてください。
たとえば、9 を 2 進表記すると 1001 ですので、1 の数は 2 ということになります。

【入力】

標準入力から、半角スペースで区切られた 2 つの整数値N(0 ≦ N ≦ 100000)、M(0 ≦ M ≦ 17)が与えられます。
 
【出力】

0 から N までの整数の中で、2 進表記したときに 1 の数が M 個あるものの個数を出力してください。

【入出力サンプル】
Input
10 2

Output
5

※11, 101, 110, 1001, 1010 の 5 つ

=====

intToBits という関数を使えば,超超簡単


f = function(s) {
    s = as.integer(unlist(strsplit(s, " ")))
    cat(sum(sapply(0:s[1], function(x) sum(as.integer(intToBits(x))) == s[2])))
}

コメント
この記事をはてなブックマークに追加

整数値の集合に条件を満たす 2 数があるか?

2016年12月31日 | ブログラミング

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

【問題】

いくつかの整数値が与えられます。
それらの中で、和がちょうど 256 になるような 2 数が存在するかどうかを調べてください。
 
【入力】

標準入力から、整数値が与えられます。

 1 行目は整数値N(2 ≦ N ≦ 100)、2 行目はN個の整数値Ak( 0 ≦ Ak ≦ 256)が半角スペースで区切られています。
 
【出力】

和が 256 になる 2 数が存在する場合は "yes"、存在しない場合は "no" と、標準出力に出力してください。
 
【入出力サンプル】
Input
4
32 64 128 192

Output
yes

=====

f = function(s) {
    x = as.integer(unlist(strsplit(s, " ")))
    y = outer(x, x, "+")
    diag(y) = 0
    cat(c("no", "yes")[(256 %in% y)+1])
}

コメント
この記事をはてなブックマークに追加

取り違えは何通り?

2016年12月31日 | ブログラミング

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

この問題,2 年前にも同じようなのが出題されたんだよね。( 完全順列 http://blog.goo.ne.jp/r-de-r/s/完全順列 )

 一人一台のパソコンを支給されている、社員N人の会社があります。
このパソコンは見た目がすべて同じため、他の人のパソコンを間違って持ち帰ってしまう場合がありました。

N人全員が他人のパソコンを持って帰ってしまうような組み合わせが何通りあるかを求めてください。
使用するプログラミング言語は問いません。

なお、出力は64bit整数に収まります。

【入出力サンプル】

Input
5

Output
44

==========

前は再帰で書いたので,別の書き方で 2 通りのプログラム

f = function(n) {
    options(scipen=100)
    a = 0
    b = 1
    for (i in 3:n) {
        x = (i - 1) * (a + b)
        a = b
        b = x
    }
    cat(x)
}

f = function(n) {
    options(scipen=100)
    k = 2:n
    cat(sum( (-1)^k * factorial(n) / factorial(k) ))
}

f(5) # 44
f(12) # 176214841
f(17) # 130850092279664

コメント
この記事をはてなブックマークに追加

ヘックス上の最長狭義単調増加列

2016年12月29日 | ブログラミング

ヘックス上の最長狭義単調増加列
締切が 2016/12/29 10:00 AM なので,その 1 分後に投稿されるように予約

【概要】
1辺4マスの六角形状のマス目があり、各マスにはa〜zの文字が入っています。
a〜zの文字は、1〜26 の数を表しています。
適当なマス目から隣のマスへ隣のマスへとたどり、どんどん増えていく数列(狭義単調増加列)を作ることを考えます。

入力で与えられる配置の場合に作ることができる狭義単調増加列の中で、もっとも要素数が多いものの要素数を計算するプログラムを書いてください。

【入出力】

入力は
javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi
こんな感じで標準入力から来ます。

マス目の東西の一列が、北から順にスラッシュ(/)区切りで並んでいます。

出力は、最長の狭義単調増加列の要素数を、10進数で。
先程の例だと左図のように,緑色の線が最長となる場合の例になりますので、
10
を出力すると正解です。

  

【例】
入力                        出力     状況
javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi    10     左図
kmyv/fuhxe/hhnnvr/dygmgwo/jbwkfu/zqthb/jxbl     9     右図

【補足】
    不正な入力に対処する必要はありません。
    長さ1でも狭義単調増加列になります。考えられる最小値は 1 になります。
    a, d, f, x のように、ちゃんと毎回増えること。a, n, n, x のようなものは NG。

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

# ヘックスの番号
#        1   2   3   4
#      5   6   7   8   9
#   10  11  12  13  14  15
# 16  17  18  19  20  21  22
#   23  24  25  26  27  28
#     29  30  31  32  33
#       34  35  36  37

# r[[i]] は,i 番目のヘックスに隣接するヘックスの番号のリスト
r = vector("list", 37)
r[[1]] = c(2, 5, 6)
r[[2]] = c(1, 3, 6, 7)
r[[3]] = c(2, 4, 7, 8)
r[[4]] = c(3, 8, 9)
r[[5]] = c(1, 6, 10, 11)
r[[6]] = c(1, 2, 5, 7, 11, 12)
r[[7]] = c(2, 3, 6, 8, 12, 13)
r[[8]] = c(3, 4, 7, 9, 13, 14)
r[[9]] = c(4, 8, 14, 15)
r[[10]] = c(5, 11, 16, 17)
r[[11]] = c(5, 6, 10, 12, 17, 18)
r[[12]] = c(6, 7, 11, 13, 18, 19)
r[[13]] = c(7, 8, 12, 14, 19, 20)
r[[14]] = c(8, 9, 13, 15, 20, 21)
r[[15]] = c(9, 14, 21, 22)
r[[16]] = c(10, 17, 23)
r[[17]] = c(10, 11, 16, 18, 23, 24)
r[[18]] = c(11, 12, 17, 19, 24, 25)
r[[19]] = c(12, 13, 18, 20, 25, 26)
r[[20]] = c(13, 14, 19, 21, 26, 27)
r[[21]] = c(14, 15, 20, 22, 27, 28)
r[[22]] = c(15, 21, 28)
r[[23]] = c(16, 17, 24, 29)
r[[24]] = c(17, 18, 23, 25, 29, 30)
r[[25]] = c(18, 19, 24, 26, 30, 31)
r[[26]] = c(19, 20, 25, 27, 31, 32)
r[[27]] = c(20, 21, 26, 28, 32, 33)
r[[28]] = c(21, 22, 27, 33)
r[[29]] = c(23, 24, 30, 34)
r[[30]] = c(24, 25, 29, 31, 34, 35)
r[[31]] = c(25, 26, 30, 32, 35, 36)
r[[32]] = c(26, 27, 31, 33, 36, 37)
r[[33]] = c(27, 28, 32, 37)
r[[34]] = c(29, 30, 35)
r[[35]] = c(30, 31, 34, 36)
r[[36]] = c(31, 32, 35, 37)
r[[37]] = c(32, 33, 36)

search = function(x, start) {
    # アルファベット列 x で,start 番目のヘックスからの径路を探索
    path = vector("list", 37) # 次のヘックス番号の候補リスト
    PATH = integer(37) # それまでにたどってきたヘックスの番号リスト
    i = 1
    path[[i]] = start
    mx = 0 # 最長径路
    repeat {
        if (length(path[[i]]) == 0) { # このノードから次のヘックス探索は終了
            i = i - 1 # 一つ前のリストに戻って繰り返し
            if (i == 0) { # 全部探索したら終わり
                break
            }
        }
        PATH[i] = start = path[[i]][1] # リストの先頭を start にして
        path[[i]] = path[[i]][-1] # 先頭を取り除く(処理済みにする)
        nxt = r[[start]] # 隣接するヘックス番号ベクトル
        nxt = nxt[x[start] < x[nxt]] # そのうちで,より大きなアルファベットのもの
        valid = setdiff(nxt, PATH) # さらに,既に通ってきたヘックス番号ではないもの
        if (length(valid) > 0) { # 次のヘックスに移動できる(径路がある)
            i = i + 1
            path[[i]] = valid # 径路の候補をリストアップ
            if (i  > mx) { # 最長経路の更新
                PATH0 = c(PATH[1:(i-1)], valid[1]) # 径路のヘックス番号ベクトル
                mx = i # 径路の長さ
            }
        }
    }
    PATH0 # 最長経路のヘックス番号ベクトル
}

f = function(s) {
    x = unlist(strsplit(gsub("/", "", s), ""))
    mx = 1 # デフォルトの最短経路は長さ 1
    for (start in seq_along(r)) { # すべてのヘックスをチェック
        # 周りのどのヘックスよりも小さいアルファベットなら本当のスタート候補
        if (all(x[start] < x[r[[start]]])) { # 周りのどのヘックスよりも小さいアルファベット
            path = search(x, start) # start から始まる径路を捜す(径路のヘックス番号ベクトルを返す)
            if (length(path) > mx) {
                mx = length(path) # 最長経路の更新
                path.max = path # 実際の径路のヘックス番号の更新
            }
        }
    }
#    cat(path.max)
    cat(mx)
}

f("javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi") # 10
f("kmyv/fuhxe/hhnnvr/dygmgwo/jbwkfu/zqthb/jxbl") # 9
f("ukps/kjcrl/ymfsqq/kbzfidr/dktjby/submc/ktps") # 8
f("zxgm/jzcwp/yacivm/ibckuek/bgoznq/svqfp/gfwn") # 7
f("pfqr/qvplf/kkrxqk/tbvravh/hurwxp/vnvwv/xjzt") # 6
f("onjw/cmtxj/jntmsv/ffttgre/sxsveu/deuey/qygd") # 5
f("neoo/boifu/dpgzxz/jhlqwwi/oijunp/fseev/tpwj") # 11
f("abcd/rstue/qpqrvf/povwswg/onutxh/nmzyi/mlkj") # 26
f("dddd/dcccd/dcbbcd/dcbabcd/dcbbcd/dcccd/dddd") # 4
f("gggg/ffffg/eeeefg/ddddefg/cccdef/bbcde/abcd") # 7
f("kjih/xyzag/wvutbf/jklmsce/ihgnrd/bcfoq/adep") # 26
f("dddd/ddddd/ccccdd/cccccdd/bbbccd/bbbcc/abbc") # 2
f("mmmm/mmmmm/mmmmmm/mmmmmmm/mmmmmm/mmmmm/mmmm") # 1
f("yxwv/zkjiu/slcbht/rmdagst/qnefru/popqv/zyxw") # 26

コメント
この記事をはてなブックマークに追加

急行停車駅をどこにする?

2016年12月27日 | ブログラミング

急行停車駅をどこにする?

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

設問

電車で移動するとき、距離が長くなると各駅停車よりも急行や特急といった電車を利用したくなります。
今回は急行と特急の停車駅を考えます。

全部で n 個の駅があり、そのうち急行の停車駅が a 個、特急の停車駅を b 個とします。
なお、特急の停車駅には必ず急行が停車するものとします。
駅が環状につながっていることはなく、開始駅と終了駅は急行、特急のいずれも停車します。

与えられる n, a, b には n > a > b > 1 の関係があるものとします。
このような停車駅の配置が何通りあるかを求めてください。

例えば、n = 4, a = 3, b = 2 のとき、以下の2通りがあります。
駅     急行停車駅     特急停車駅
A     〇     〇
B     〇     ×
C     ×     ×
D     〇     〇
    
駅     急行停車駅     特急停車駅
A     〇     〇
B     ×     ×
C     〇     ×
D     〇     〇

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

標準出力
2

なお、出力内容が32bitの整数で収まるような入力が与えられるものとします。

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

ご大層な問題説明だが,数 I レベルの問題
同じもの a が p 個,b が q 個,c が r 個,… ,合計 n 個あるとき,これらを全部使って1列に並べる順列の総数は n!/(p!q!r!···) 通り というやつだ
n 個の駅の始発駅と終着駅は急行も特急も停まるので,場合の数には関係ない。
残りの n-2 個の駅は,特急も急行も停まるのは,b-2 個,急行だけが停まるのは a-b 個,特急も急行も停まらないのは n-a
上の公式から求めるのは (n-a)! / (b-2)! / (a-b)! / (n-a)!

f = function(n, a, b) {
    both = b-2
    express.only = a-b
    dont.stop = n-a
    N= (b-2) + (a-b) + (n-a)
    cat(factorial(N) / factorial(both) / factorial(express.only) / factorial(dont.stop))
}

> f(26, 14, 7)
2141691552

コメント
この記事をはてなブックマークに追加