たすのーと - ABC397振り返り

オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）に出場したので振り返り。

ABCの3完、Dは方針思い浮かばず。終了後に解説読んでAC。

A - Thermometer

問題文に従って条件分岐するだけ。入力の値は整数や文字であることが多い（気がする）ので、 Double や Float が来るとちょっとドキッとする。

main :: IO ()
main = do
    x <- readLn @Double

    print $ if x >= 38.0 then 1
            else if x < 37.5 then 3
                 else 2

B - Ticket Gate Log

「前から順に 'i' 、 'o' を詰めていけばいいかな」と方針はすぐ立ったが、さくっと実装できずに時間がかかってしまった。。。（このくらいであれば、Aと合わせて10分くらいで片付けたい）

方針としては、以下の通り。

今の位置が奇数番目か偶数番目か（奇数番目なら False 、偶数番目なら True ）
今の文字が 'i' か 'o' か

の2つを状態として持っておく。文字を順番に見ていって「奇数番目で 'o' 」「偶数番目で 'i' 」の場合に挿入文字数をカウントアップするとともに、適切な文字を挿入して再度見る。すべての文字を見終わったとき、これまでに見た文字数が奇数個の場合には、最後に 'o' が必要なので挿入文字数に1を追加する。

提出 #63792316

main :: IO ()
main = do
    s <- list1 ucChar

    print $ solve s

    return ()

solve :: [Char] -> Int
solve = go 0 False
    where go n f [] = if f then n+1 else n
          go n f (t:ts) = case (f, t) of
              (True, 'o') -> go n (not f) ts
              (True, 'i') -> go (n+1) (not f) (t:ts)
              (False, 'o') -> go (n+1) (not f) (t:ts)
              (False, 'i') -> go n (not f) ts

がんばって再帰処理を書いているけど、もう少し簡単にかけそう。まず、

(True, 'i') -> go (n+1) (not f) (t:ts)
(False, 'o') -> go (n+1) (not f) (t:ts)

の箇所。 (not f, t) は (True, 'o') もしくは (False, 'i') となるので、以下のように書き直せる。

(True, 'i') -> go (n+1) f ts
(False, 'o') -> go (n+1) f ts

こうすると、 go 内の処理は、単に1文字見て状態を更新しているだけなので、左からの畳み込み foldl' で書き直せる。

main :: IO ()
main = do
    s <- list1 ucChar

    print
        . (\(f, n) -> if f then n+1 else n)
        . foldl' (\(f, n) t -> if (f, t) `elem` [(True,'i'), (False,'o')]
                               then (f, n+1)
                               else (not f, n)) (False, 0) $ s

状態が1つだと、「あ、これは畳み込みで書けるな」と思いつくことも多いけど、状態が複数になるとゴリッと再帰関数を書いてしまいがち（あとは State モナドで書こうとしてみたり）。こういうパターンもスッと書けるようになりたい。

C - Variety Split Easy

最初、累積和っぽい問題だなーと感じた。数列の左と右からそれぞれ種類数を数え、 \(i\) 毎の種類数の和の最大値を求めればよい。

これも、種類数を数え上げる箇所の実装に手間取り、時間がかかってしまった。

提出 #63829898

main :: IO ()
main = do
    n <- readLn @Int
    as <- listArray (1,n) <$> list1 ucInt :: IO (UArray Int Int)

    cuml <- ascanl1 as :: IO (IOArray Int Int)
    cumr <- ascanr1 as :: IO (IOArray Int Int)

    cum <- forM [1..n-1] $ \i -> do
        l <- readArray cuml i
        r <- readArray cumr (i+1)
        return $ l+r

    print $ maximum cum

    return ()

ascanl1 :: (Ref r m, MArray ma Int m, IArray ia Int) =>ia Int Int -> m (ma Int Int)
ascanl1 arr = do
    let b@(l,h) = bounds arr
    sRef <- newRef $ S.singleton (arr ! l)

    result <- newArray_ b

    writeArray result l 1

    for_ (range (l+1,h)) $ \i -> do
        x <- readArray result (i-1)
        s <- readRef sRef
        let y = arr ! i

        if S.notMember y s
            then do writeArray result i (x+1)
                    modifyRef' sRef (S.insert y)
            else writeArray result i x

    return result

ascanr1 :: (Ref r m, MArray ma Int m, IArray ia Int) => ia Int Int -> m (ma Int Int)
ascanr1 arr = do
    let b@(l,h) = bounds arr
    sRef <- newRef $ S.singleton (arr ! h)

    result <- newArray_ b

    writeArray result h 1

    for_ (reverse $ range (l,h-1)) $ \i -> do
        let x = arr ! i
        y <- readArray result (i+1)
        s <- readRef sRef
        if S.notMember x s
            then do writeArray result i (1+y)
                    modifyRef' sRef (S.insert x)
            else writeArray result i y

    return result

自作の Array 用 scan 系関数を用意していたので、それを改造して種類数を数え上げるということをしたが、そのようなことをしなくても良さそう。

この問題で更新すべき状態は種類数と「その数字がすでに出現したか」の2つなので、B問題と同様に以下のように書き直せる。

main :: IO ()
main = do
    n <- readLn @Int
    as <- list1 ucInt

    let cuml = scanl (\(s, n) a -> if S.notMember a s then (S.insert a s, n+1) else (s, n)) (S.empty, 0) as
        cumr = scanr (\a (s, n) -> if S.notMember a s then (S.insert a s, n+1) else (s, n)) (S.empty, 0) as

    print $ maximum $ zipWith (+) (map snd cuml) (map snd cumr)

すでにその数字が出現したかどうかは Set で管理しているが、 IntSet を使ったほうがだいぶ早くなる。 Set を使った版: 1412ms IntSet を使った版: 782ms

D - Cubes

全く方針立たず、コンテスト後に解説AC。コンテスト中は、 \(x\) と \(y\) の値の範囲が決まらないから全探索もできないよなぁ、と思っていたけど、 \(x-y\) で全探索すればいいのか・・・そんなん思いつかんわ・・・

解説の通り、 \(y\) についての2次方程式を解の公式を使って解く。 \(y > 0\) であることを考慮すると、 \(x-y < \sqrt[3]{N} \sim 10^6\) となるので、全探索で十分間に合う。 \(N < 10^{18}\) の制約なので、オーバーフローしないように Int ではなく Integer を使用する。根号の中身が整数となるように注意して、以下のように実装した。

main :: IO ()
main = do
    n <- readLn @Integer

    let cand = filter (\(x,_) -> isJust x) [(solve n d, d) | d <- takeWhile (\x -> x^3 < n) [1..]]

    putStrLn $ if null cand then "-1"
        else let y = fromJust $ fst $ head cand
                 d = snd $ head cand
             in show (y + d) <> " " <> show y


solve :: Integer -> Integer -> Maybe Integer
solve n d = case sqrtIntegral $ 12 * d * n - 3 * d ^ 4 of
                Nothing -> Nothing
                Just c -> if (c - 3 * d^2) `mod` (6 * d) == 0
                          then Just $ (c - 3 * d^2) `div` (6 * d)
                          else Nothing

sqrtIntegral :: Integral a => a -> Maybe a
sqrtIntegral x = let c0 = sqrt $ fromIntegral x
                     c1 = ceiling c0
                     c2 = floor c0
                 in if | x == c1^2 -> Just c1
                       | x == c2^2 -> Just c2
                       | otherwise -> Nothing

感想

久しぶり（3ヶ月ぶり）にコンテストに出てみたが、あえなく撃沈・・・ BCともに、方針を立てるのは割と早かったが、実装の手が遅いなと反省。これは数をこなしていくのみ。今後はできるだけコンテストに参加するのと、コンテスト外でも勉強を続けよう。

自分の傾向として、気軽に再帰処理を書きがちなので、 fold 系関数などを使って書けないか気にするようにしたい。再帰処理を書いていると、だんだんとぐちゃぐちゃしてきて見通しが悪くなったりする。そのため、問題固有の計算と再帰の構造を分けて考えられるようになると良さげ。