AtCoder Beginner Contest 428

2025-10-18

abc3完
パフォーマンス819、レーティング808(+1)

1月半ぶり&Haskellに乗り換えて2回目のABC参加。前回は400台のパフォーマンスだったので、それと比べるとHaskellに慣れてきた気がする。当面の目標として安定して緑パフォを出せるようにしたい。

A - Grandma’s Footsteps

走り始めてから停止するまでのセットを繰り返せる回数はx ` div` (a+b)回
上記の後の残り時間がa秒より短い場合は残り時間 * sメートル走る。a秒以上の場合はa * sメートル走る

type I = [Int]
type O = Int

solve :: I -> O
solve [s,a,b,x] = n * s * a + d
    where
        n = x `div` (a + b)
        r = x `mod` (a + b)
        d | r <= a = r * s
          | otherwise = a * s

B - Most Frequent Substrings

文字列Sから長さKの部分文字列のリストを計算する関数をf定義して解いた。fの出力を、出現頻度を求める関数freqに適用して出現頻度を計算し、最大頻度の要素をフィルタして答えを求めた。freqの出力の型はMap String IntでkeyがStringになっており、これをtoListするとStringの昇順すなわち辞書順に並んだリストを得られるので、フィルタ後に辞書順に並び替える必要はない。

type I = ([Int], String)
type O = (Int, [String])
input :: B.ByteString -> I
input b = (readBList l1, B.unpack l2)
    where
        [l1, l2] = B.lines b
output :: O -> B.ByteString
output (n, xs) = B.pack $ show n ++ "\n" ++ unwords xs

solve :: I -> O
solve ([n,k],s) = (mx,ans)
    where
       xs = f k s []
       mp = freq xs
       mx = maximum mp
       ans = map fst . filter (\p -> snd p == mx) . Map.toList $ mp

f :: Int -> String -> [String] -> [String]
f k s xs
    | length s < k = xs
    | otherwise = f k (tail s) xs'
    where
        xs' = take k s : xs

C - Brackets Stack Query

入力では"("を0、")"を1に読み替えることで[[Int]]として読み込む。solveは[Bool]を出力して、その後段でTrue/Falseを"Yes"/"No"に変換する。

type I = [[Int]]
type O = [Bool]
input :: B.ByteString -> I
input = readBGrid
readBInt :: B.ByteString -> Int
readBInt = readBInt' (\b-> if B.unpack b == "(" then 0 else 1)
readBInt' :: (B.ByteString -> Int) -> B.ByteString -> Int
readBInt' f b | isJust x = fst . fromJust $ x
              | otherwise = f b
    where
        x = B.readInt b
readBList :: B.ByteString -> [Int]
readBList = map readBInt . B.words
readBGrid :: B.ByteString -> [[Int]]
readBGrid = map readBList . B.lines

output :: O -> B.ByteString
output = B.unlines . map (B.pack . s)
    where
        s b | b = "Yes"
            | otherwise = "No"

良い括弧は、"("を+1、")"を-1として左側から和を計算したとき

文字列の終わりでちょうど0なり
途中一度も和が負にならない

と表すことができる。

クエリで末尾1文字を削除または追加した際に良い括弧であることを高速に判定するため、状態を(和、和が負になる文字列のインデックスの集合、現在の文字列、文字列の長さ)のタプルで定義して、これを更新しながら判定する。文字列はスタック、文字列の長さや文字列のインデックスはスタックの長さとして実装することで、末尾1文字の追加・削除を高速に処理することができる。

type I = [[Int]]
type O = [Bool]

solve :: I -> O
solve ([q]: xs) = snd $ mapAccumL f (0, Set.empty, [], (-1)) xs

type S = (Int, Set.Set Int, [Int], Int)
f :: S -> [Int] -> (S, Bool)
f (s, st, xs, idx) [1, 0] = ((s', st', xs', idx'), False)
    where
        s' = s + 1
        st' = if s' < 0 then Set.insert idx' st else st
        xs' = 0:xs
        idx' = idx + 1
f (s, st, xs, idx) [1, 1] = ((s', st', xs', idx'), s' == 0 && Set.null st')
    where
        s' = s - 1
        st' = if s' < 0 then Set.insert idx' st else st
        xs' = 1:xs
        idx' = idx + 1
f (s, st, x:xs, idx) [2] = ((s', st', xs', idx'), s' == 0 && Set.null st')
    where
        s' = if x == 0 then s - 1 else s + 1
        st' = if Set.member idx st then Set.delete idx st else st
        xs' = xs
        idx' = idx - 1