締め切りが 2016/09/29 10:00 AM なので，その 1 分後に投稿されるように予約
設問
次のルールで生成される迷路を考えます。
レベル 1 の迷路から始めましょう。レベル 1 の迷路を M1 と呼びます。M1 は、3 つの点を L の字の形につないだものです。
左上の点がスタートで、右下の点がゴールです。
レベル 2 の迷路 M2 は、M1 を 3 つつなげて作ります。
M1 を 1 つ置き、さらにその上と右に 1 つずつ M1 をつなげたものです。
左上の点がスタートで、右下の点がゴールです。
レベル 3 の迷路 M3 は、M2 を 3 つつなげて作ります。
M2 を 1 つ置き、さらにその上と右に 1 つずつ M2 をつなげたものです。
左上の点がスタートで、右下の点がゴールです。
以降同様に、レベル k の迷路 Mk を、レベル k－1 の迷路 Mk－1 を 3 つつなげることで定義します。
さて、この迷路を、点と線をたどってスタートからゴールまで着く方法を考えます。
自然数 n に対し、迷路 Mn を最短距離でゴールするたどり方の数を F(n) と定義します。
例えば F(1) ＝ 1，F(2) ＝ 2 です。
同様に、F(3) ＝ 6，F(4) ＝ 42 です。
さらに、F(10) を 1000003（＝10^6＋3） で割った余りは 998593 となることが確かめられます。
標準入力から、自然数 n（1 ≦ n ≦ 10^8）が与えられます。
標準出力に F(n) を 1000003 で割った余り を出力するプログラムを書いてください。
＝＝＝＝＝
いつもの定石，すなわち，小さな問題の解を求め規則性を見つける。a(n) = a(n-1) * (a(n-1)+1)
ただし，真っ正直に計算するのでは n がばかでかいときには時間が掛かりすぎる。
ここでは，「1000003 で割った余り」を求めよということなので，答えの数列は一度ループにはまると，ループをぐるぐる回ることになるということ（これも定石）。
1~213 はループの外，214 項目の数値と同じ数値は1169 項目と同じになる（これは調べる）。
すなわち，214~1168, 1169~2123, ... は長さ955 のループ（同じ数字列の繰り返し）。
f = function(n) {
m = 1168
k = 1000003
a = numeric(m)
options(scipen=100)
a[1] = f1 = 1
a[2] = f2 = 2
for (i in 3:m) {
f3 = ((f2 %% k) * ((f2+1) %% k)) %% k
a[i] = f3
f1 = f2
f2 = f3
}
if (n >= 214) {
n = (n-214) %% 955 + 214
}
cat(a[n], " ")
}
> f(10)
998593
> f(100000000)
342482
素数で作る天秤ばかり
2016/09/20 10:00 AM なので，その 1 分後に投稿されるように予約
【問題】
天秤ばかりを使って重さを量りたいと考えています。
ただし、使えるおもりは重さが素数のものしかありませんでした。
m, n をともに正の整数とし、m 以下の素数すべてがおもりの重さとして1つずつ用意されているとき、n グラムの計り方が何通りあるかを求めてください。
例えば、m = 10, n = 2のとき、2, 3, 5, 7 のおもりが一つずつありますので、左右に以下のおもりを使った4通りがあります。
（量るものを左側に置いたとします。）
左側 右側
なし 「2」
「3」 「5」
「5」 「7」
「2」、「3」 「7」
標準入力から m と n がスペースで区切って与えられるとき、n グラムの計り方が何通りあるかを標準出力に出力してください。
（ただし、 m < 50 とします。）
【入出力サンプル】
標準入力
10 2
標準出力
4
==========
bin を毎回呼び出すとそのオーバーヘッドがあるので，結果をリスト bin.list に保存しておき，関数呼び出しをリストの参照に換えることで，実行時間は速くなる
bin = function(p) {
retval = matrix(0L, nrow = 2^p, ncol = p)
for (n in 1:p) {
retval[, n] = rep(c(rep(0L, (2^p/2^n)), rep(1L, (2^p/2^n))), length = 2^p)
}
retval
}
f = function(m, n) {
bin.list = sapply(1:14, bin)
count = 0
prime = c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)
prime = prime[m >= prime]
left.use = bin.list[[length(prime)]] # bin(length(prime))
left = left.use %*% prime + n
for (i in 1:(nrow(left.use) - 1)) {
rest = prime[!left.use[i, ]]
if (sum(rest) >= left[i]) {
right.use = bin.list[[length(rest)]] # bin(length(rest))
right = right.use %*% rest
count = count + sum((left[i] == right))
}
}
cat(count)
}
f(10, 2) # 4
f(20, 10) # 90
f(30, 50) # 286
f(40, 30) # 3217
f(46, 3) # 24946
> 第５回みえ県民意識調査は、各市町の選挙人名簿を使用した等間隔無作為抽出法により、標本を抽出しており、標本数10,000人に対して、有効回答数は5,236人でした。そのため、各属性において、実際の県全体と回答者の構成が異なる部分もあることから、以下にその概略をまとめています。
「等間隔無作為抽出法」というのは統計学用語にあるのかな？ふつうは「等間隔抽出法」とか「系統抽出法」じゃないか？
「標本数10,000人」というのは大間違い。「調査対象が10,000人」ということ。「標本数」と「標本の大きさ（サンプルサイズ）」は大違い。
また，本文中で「回答数（サンプル数）」と何回も書いているが，「サンプル数」というのは統計用語にはない「標本の大きさ」とか「サンプルサイズ」というのがよい。
> 例えば、同じ調査を異なる調査対象で100回行った場合、95回以上の割合で同様の差が生じる場合は「統計的に有意な差がある」と表現し、90回以上の割合で同様の差が生じる場合は「統計的にある程度有意な差がある」と表現しています。
「統計学的に有意」の説明はいい加減。
> Ｕ＞1.64の時、平均値の差は統計的に有意であると言える（危険率５％）
うおっ。何の断りもなく「片側検定」を行っているよ。
いい加減な用語を使っていると，内容の信頼性が低下する。
顧問として，「○○大学地域学部 教授 ○○○○」の名前があるんだが...
地元なんだから，三重大学の奥村晴彦先生に監修してもらうと良いのでは？
締め切りが 2016/09/13 10:00 AM なので，その 1 分後に登録されるように予約
パターゴルフのコースを新しく作ることにしました。
そこで、各ホールの標準打数を考えています。
m ホールで合計の標準打数が n になるように、各ホールの標準打数を決めなければなりません。
なお、各ホールの標準打数は1以上5以下とし、m≦18とします。
例えば、3ホールで合計が12の場合、以下の10通りがあります。
2 5 5
3 4 5
3 5 4
4 3 5
4 4 4
4 5 3
5 2 5
5 3 4
5 4 3
5 5 2
標準入力から m と n がスペースで区切って入力されます。
このとき、各ホールの標準打数のパターン数を標準出力に出力してください。
【入出力サンプル】
標準入力
3 12
標準出力
10
＝＝＝＝＝＝＝＝＝＝
m, n が小さいときの解を網羅して，規則性を見いだす。
規則に従い，以下のような行列（18×90 の行列）を生成する。
[,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]
[1,] 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[2,] 0 1 2 3 4 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[3,] 0 0 1 3 6 10 15 18 19 18 15 10 6 3 1 0 0 0 0 0 0 0 0 0 0
[4,] 0 0 0 1 4 10 20 35 52 68 80 85 80 68 52 35 20 10 4 1 0 0 0 0 0
[5,] 0 0 0 0 1 5 15 35 70 121 185 255 320 365 381 365 320 255 185 121 70 35 15 5 1
:
:
その行列の m 行，n 列の数値が解である。
f = function(m, n) {
a = matrix(0, 18, 90)
a[1, 1] = 1
x = rep(1, 5)
for (i in 2:18) {
k = i+0:(length(x)-1)
for (j in 0:4) {
a[i, j+k] = a[i, j+k] + x
}
x = a[i, i:(i*5)]
}
cat(a[m, n])
}
> f(3, 12)
[1] 10
> f(5, 21)
[1] 70
> f(9, 35)
[1] 32211
> f(13, 60)
[1] 6175
> f(18, 72)
[1] 2546441085
締め切りが 09/02 10:00 AM に設定されている（ずいぶん先だなあ）
ということで 09/02 10:01 AM に投稿されるように予約（あとで，締め切りが延ばされても，それには関知しない）
【概要】
カードが何枚かあります。
カードには、一桁の数字が書いてあります。
カードを n 枚選んで並べて数を作ります。
たとえば、「3」「1」「4」「1」「5」が書いてあるカードから 3 枚(つまり、n=3)を選んで並べると「341」や「115」を作ることができます( 「334」や「31」は作れません）。
作れる数のうち、ある数 m にもっとも近い数を答えてください。
【入出力】
入力は
4,1234,1/2/2/3/9/9/9
のような感じです。
コンマ区切りで、n(カードの枚数)、m(この値に近い数を作る)、カード列 が並んでいます。
カード列は、カードに書いてある数字をスラッシュ区切りで並べたものです。
出力は、
1232
のような感じです。最も近い数が 2 つある場合は、小さい順に両方共出力してください。
1233,1235
のような感じです。
末尾の改行はあってもなくても構いません。
作れる数がひとつもない場合には、- を出力してください。
【例】
入力 出力
4,1234,1/2/2/3/9/9/9 1232
4,1234,1/2/2/3/3/5/5 1233,1235
【補足】
「01」のような、「0」で始まる二桁以上の数は作れません。一桁の「0」は OK です。
カードの枚数は8枚以下です。
n は 1 以上で、カードの枚数を超えることはありません。
m は 0 以上、10の9乗以下です。
6 のカードを逆さにして 9 として使ったりすることはできません。
不正な入力に対処する必要はありません。
【テスト用データ】
1,3,0/9/8
2,10,0/9/8
3,414,3/4/9/8/7
4,4981,4/5/0/1/2/3/8
5,12345,0/0/0/0/0/0/0
5,43103,3/5/0/2/1/4/9/4
6,172365,3/2/3/7/2/7/1/6
7,6523060,4/0/7/2/6/5/3/3
8,19069255,1/2/9/3/7/6/9/0
8,80465325,2/6/5/7/8/9/7/7
8,88888888,8/8/8/8/8/8/8/8
8,88888888,9/8/7/6/5/4/3/2
perm = function(n) {
z = matrix(1)
if (n > 1) {
for (i in 2:n) {
x = cbind(z, i)
a = c(1:i, 1:(i - 1))
z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
z[1:nrow(x), ] = x
for (j in 2:i - 1) {
z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
}
}
}
dimnames(z) = NULL
return(z)
}
func = function(s) {
t = as.integer(unlist(strsplit(s, "[,/]")))
n = t[1]
m = t[2]
t = t[-(1:2)]
k = length(t)
p = matrix(t[perm(k)], ncol=k)[,1:n, drop=FALSE]
p = unique(p)
if (n > 1) {
p = p[p[,1] != 0, , drop=FALSE]
}
if (nrow(p) == 0) return("-")
fac = if (n == 0) 1 else 10^((n-1):0)
d = p %*% fac
diff = abs(d-m)
suf = which(diff == min(diff))
paste(d[suf], collapse=",")
}
con = file("stdin", "r")
cat(func(readLines(con)))
PVアクセスランキング にほんブログ村
