結果

問題 No.3114 0→1
コンテスト
ユーザー Alph(その辺の大学生A)
提出日時 2025-04-20 17:44:02
言語 Haskell
(9.10.1)
結果
TLE  
実行時間 -
コード長 863 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,531 ms
コンパイル使用メモリ 190,760 KB
実行使用メモリ 35,392 KB
最終ジャッジ日時 2025-04-20 17:44:21
合計ジャッジ時間 8,415 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.10.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff #
raw source code 

toBitarray :: String -> Int -> Int -> [Bool]
toBitarray s k fullN = replicate (k - 1) True ++ [c == '1' | i <- [k - 1 .. fullN - 1], let c = s !! (i - k + 1)]

min_find :: String -> Int -> Int -> Int
min_find s n len = changes
  where
    weightMin = (len + 1) `div` 2
    fullLen = n + weightMin - 1
    bits = toBitarray s weightMin fullLen
    initialHWeight = length . filter id $ take len bits
    (_, _, changes) = foldl (update weightMin len) (bits, initialHWeight, if initialHWeight < weightMin then 1 else 0) [1 .. fullLen - len]
    update wm l (xs, hw, ch) i =
      let hw' = hw - fromEnum (xs !! (i - 1)) + fromEnum (xs !! (i + l - 1))
      in if hw' < wm
           then (take (i + l - 1) xs ++ [True] ++ drop (i + l) xs, hw' + 1, ch + 1)
           else (xs, hw', ch)

main :: IO ()
main = do
  n <- readLn
  s <- getLine
  print $ min_find s n 3
0