グループで乗るリフト

グループで乗るリフト

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

設問

m 人のグループがスキー場でリフトやゴンドラに乗ろうとしています。
このスキー場には n 人乗りのリフトやゴンドラがあります。
グループでまとまって移動するため、連続したリフトやゴンドラに乗ることにします。
グループのメンバーは区別せず、各リフトやゴンドラに乗る人数だけを考えるとき、
1回の移動における乗り方が何通りあるかを求めてください。
ただし、誰も乗らないリフトやゴンドラはないものとします。
また、m, n ともに 32以下の正の整数とします。

例えば、m = 5, n = 3 のとき、以下の13パターンがあります。
パターン     1台目     2台目     3台目     4台目     5台目
(1)     1人     1人     1人     1人     1人
(2)     1人     1人     1人     2人     -
(3)     1人     1人     2人     1人     -
(4)     1人     2人     1人     1人     -
(5)     2人     1人     1人     1人     -
(6)     1人     1人     3人     -     -
(7)     1人     3人     1人     -     -
(8)     3人     1人     1人     -     -
(9)     1人     2人     2人     -     -
(10)     2人     1人     2人     -     -
(11)     2人     2人     1人     -     -
(12)     2人     3人     -     -     -
(13)     3人     2人     -     -     -

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

標準出力
13

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

下図のような規則性を持った二次元数列になる

各列のオレンジの部分以降の桝目の数値は，それ以前の n 個の桝目の和（広義のフィボナッチ数列） n = 2（C 列）を見ればわかる

f = function(m, n) {
    a = integer(m+1)
    a[1] = 1
    a[2:n] = 2^(0:(n-2))
    for (i in n:m+1) {
        a[i] = sum(a[i-n:1])
    }
    cat(a[m+1],"\n")
}
if (0) {
    mn = scan(file("stdin", "r"))
    f(mn[1], mn[2])
} else {
    f(5, 3) # 13
    f(6, 4) # 29
    f(10, 2) # 89
    f(25, 10) # 16646200
    f(32, 16) # 2147205120
}

ぎゅうぎゅうシーケンス

ぎゅうぎゅうシーケンス

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

【問題】

整数値の並びがあります。
この並びの中で"1", "2", "3"をすべて含む区間のうち、最も小さい区間サイズを調べてください。
たとえば、{3, 4, 2, 6, 5, 1, 3, 3, 2}のような並びの場合、最後の4要素分{1, 3, 3, 2}は、"1", "2", "3"のすべてを含み、かつサイズが最小(4)になっています。

【入力】

1行目に正の整数値の数N(最大5000)、2行目に正の整数値(100より小さい)がN個、半角スペース区切りで書かれています。
また、2行目には"1", "2", "3"のすべてが少なくとも1つずつは含まれています（つまり、区間が必ず見つかるデータになっています）。

【出力】

最小の区間サイズのみ出力してください。

【入出力サンプル】
Input

9
3 4 2 6 5 1 3 3 2

Output

4

===================
 
逐次探索していっても，計算時間は問題ない

f = function(x) {
    seq = 1:3 # 探索対象数値
    Min = n = length(x)
    for (i in 1:n) { # 区間開始数値の探索
        match = seq %in% x[i] # 1, 2, 3 のいずれか
        if (any(match)) { # 1, 2, 3 のいずれかである
            delm = seq[!match] # 区間終了はその数値以外
            for (j in (i+1):n) { # 区間終了数値の探索
                match2 = delm %in% x[j] # 終了数値に含まれるか
                if (any(match2)) { # 終了数値である
                    delm = delm[!match2] # 終了数値から取り除く
                    if (length(delm) == 0) { # 1，2，3 すべてが出ていたら
                        Min = min(Min, j-i+1) # 最小値を更新して
                        break # 次の区間開始を探索
                    }
                }
            }
        }
    }
    cat(Min)
}
if (0) {
    f(c(3,4,2,6,5,1,3,3,2)) # 4
} else {
    f(scan(file("stdin", "r"))[-1])
}