ぎゅうぎゅうシーケンス
締め切りが 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])
}
最新の画像[もっと見る]
-
算額(その2059) 2時間前
-
算額(その2057) 5時間前
-
算額(その2056) 20時間前
-
算額(その2055) 20時間前
-
算額(その2054) 1日前
-
算額(その2053) 1日前
-
算額(その2052) 1日前
-
算額(その2051) 1日前
-
算額(その2051) 1日前
-
算額(その2050) 2日前
※コメント投稿者のブログIDはブログ作成者のみに通知されます