ユニークビジョンプログラミングコンテスト2025 春（AtCoder Beginner Contest 398）に出場したので振り返り。
今回もA,B,Cの3完。Dは方針思い浮かばず、解説AC。 どんどん成績が下がっていっている。。。
A - Doors in the Center
\(N\) が奇数のときは '=' が文字列の中央に1個、偶数のときは2個となることに注意すれば、それほど迷わずに解けた。
main :: IO ()
main = do
n <- readLn @Int
putStrLn $ if odd n
then replicate (n `div` 2) '-' <> "=" <> replicate (n `div` 2) '-'
else replicate (n `div` 2 - 1) '-' <> "==" <> replicate (n `div` 2 - 1) '-'B - Full House 3
最初、 \((x,y) = (3,2)\) 以外のパターンを考慮しておらずWA。 サンプル問題で正解していたのに安心して、他のパターンが無いか探していなかった・・・ 次の提出も、 \((x,y) = (5,2)\) のパターンを見逃していてWAで、結局3回目でAC。
main :: IO ()
main = do
as <- L.sortBy (flip compare) . map length . L.group . L.sort <$> list1 ucInt
putStrLn $ case as of
(5:2:_) -> "Yes"
(4:3:_) -> "Yes"
(4:2:_) -> "Yes"
(3:3:_) -> "Yes"
(3:2:_) -> "Yes"
_ -> "No"C - Uniqueness
リスト操作関数を利用して、
- リストに要素番号を付与する
- リストをソートする1
- 同じ値の要素同士でグルーピングする
- グループ毎の要素数を数える
として、グループの要素数が1個のものを選ぶことで、「他の人が同じ数を持っていない人」を探すことができる。
このように、要素を1つずつ処理するのではなく、リストに対する操作に分割して計算すると、見通しがよくなる（と思う）。
この問題に限らず、リストをソートしてグルーピングして長さを数えて・・・というのは割とよく見る気がする。
main :: IO ()
main = do
n <- readLn @Int
as <- map snd . takeWhile ((==1) . fst) . L.sortOn fst . map (\xs -> (length xs, head xs)) . L.groupBy (\(_,x) (_,y) -> x == y) . L.sortBy (\(_,x) (_,y) -> compare x y) . zip [1..n] <$> list1 ucInt
print $ if null as then -1 else fst $ L.maximumBy (\(_,x) (_,y) -> compare x y) asD - Bonfire
コンテスト中は方針思いつかず・・・。 相対位置に着目すれば、「煙が移動すること」と「高橋くん・たき火が逆方向に移動すること」は同値。 この点に気づければ、素直に実装できる。
今回は、
- 移動後の高橋くんの座標
- 移動後のたき火の座標
- 各時間に生成された煙の座標
- 高橋くんの位置に煙が有るか無いかの履歴（これが回答すべきもの）
を状態として保持し、順番に計算すれば良い。
main :: IO ()
main = do
[n,r,c] <- list1 ucInt
ss <- reverse <$> list1 ucChar
let (_,_,_,result) = foldr (\s ((tx,ty), (bx,by), smoke, trace) ->
let (t_next, b_next) = case s of
'N' -> ((tx+1,ty),(bx+1,by))
'W' -> ((tx,ty+1),(bx,by+1))
'S' -> ((tx-1,ty),(bx-1,by))
'E' -> ((tx,ty-1),(bx,by-1))
in if S.member t_next smoke
then (t_next, b_next, S.insert b_next smoke, '1':trace)
else (t_next, b_next, S.insert b_next smoke, '0':trace))
((r,c),(0,0),S.singleton (0,0),[]) ss
putStrLn $ reverse result他の人の回答を見てみると、 Data.Traversable の mapAccumL を使っているものもあった。
あまり Traversable をちゃんと使ったことがないので、使い方を勉強してみよう。
感想
B問題でWA（しかも2回！）を出してしまったのはとても残念、できるだけ早く提出しようと焦ってたのかな。 今は、簡単な問題を早く正解しようとがんばるよりも、考慮漏れが無いよう慎重になったほうがいいね。 （考慮漏れが出てしまうのはしょうがないけど、WAが出た瞬間に考慮できていなかったパターンが思い浮かぶ、みたいなのは無くしたい）
C問題は、「持っている数の最大値」を出力するものだと読み間違えて、バグが取れずに時間を消費してしまった。 問題文をしっかり読んでなかったため、時間がかかってしまったと思う。 こういうのも、問題文（とサンプル問題）をよく読めばすぐに解決できるので、焦らず行きたいね。
D問題は解けたり解けなかったりで、なかなか安定しない。 D問題解けないとなかなかパフォーマンスも上がらない（というより、めっちゃ低くなる）ので、まずはD問題ちゃんと解けるように練習していこう。
Data.ListのsortByは、4-way マージソートとして実装されている。そのため、全体としては \(O (N \log N)\) の計算量になる。↩︎