[topic] 情報オリンピック2007年度国内本選問題2
Posted feedbacks - Haskell
[1..100]>>=pen
#5978()
[
Haskell
]
「最長共通（連続）部分列」 i-1 とか j-1 とかのインデックスを使わずに。
1 2 3 4 5 6 7 8 9 10 | import List
solve s1 s2 = fst $ foldl f (0, 0: map (const 0) s1) s2 where
f (m, xs) c = (m', 0:xs') where
(m', xs') = mapAccumL g m $ zip s1 xs
g n (d, x) = if (d == c) then (max n (x+1), x+1) else (n, 0)
{-
> solve "ABRACADABRA" "ECADADABRBCRDARA"
5
-}
|
[1..100]>>=pen
#5979()
[
Haskell
]
「最長共通（連続）部分列」 #5978 は yukobaさんの #5969 とほとんど同じでした。 いつも書いた直後に気づく。orz #5969 と同じ書き方にしました。
1 2 3 4 5 | import List
solve s1 s2 = fst $ foldl f (0, 0: map (const 0) s1) s2 where
f (m, xs) c = (maximum (m:xs'), 0:xs') where
xs' = zipWith (\d x -> if (d == c) then x+1 else 0) s1 xs
|
yukoba #5778() Rating0/0=0.00
中高生向けの情報オリンピック国内本選2007年度問題2です。
「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。本問では、制限時間1秒、メモリ制限64MBとなっています。
出題時はサンプルデータのみが公開され、採点は、採点データによる、自動採点にて行われます。
実際のコンテストでは、予選通過者48名が対象となっていて、100点満点中38点以上とった、16名が本選通過です。
[ reply ]