# ABC303 振り返り
- [日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303） - AtCoder](https://atcoder.jp/contests/abc303)
- [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc303) (ABCD 4完)
- 前回 [[ABC302 振り返り]]
以下、キーワードリンクはローカルの内部リンクになっていて辿れません。
----
## [A - Similar String](https://atcoder.jp/contests/abc303/tasks/abc303_a)
素直なA問題、実装するだけ。いつも A の実装中はガチガチに緊張しているので、おかしなミスをしてしまわぬよう型注釈までつけつつパターンマッチで丁寧に...
```haskell
{-# LANGUAGE TypeApplications #-}
f :: Char -> Char -> Bool
f '1' 'l' = True
f 'l' '1' = True
f '0' 'o' = True
f 'o' '0' = True
f a b = a == b
main :: IO ()
main = do
n <- readLn @Int
s <- getLine
t <- getLine
putStrLn $ if and $ zipWith f s t then "Yes" else "No"
```
---
## [B - Discord](https://atcoder.jp/contests/abc303/tasks/abc303_b)
- $M$ 回すべてに対して、隣の人が誰だったかを見ていくと、隣にならなかったペアが見つかる
- タプルでペアを集めていって、見つからなかったペアの数を数える。$(a, b)$ と $(b, a)$ は同一視する必要があるので大小関係を揃えるようにした
- 「見つからなかったペアの集合」は「全てのペアの集合」から「見つかったペアの集合」の差を取ることで発見できる
```haskell
import Control.Monad (replicateM)
import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import Data.List (tails, unfoldr)
import qualified Data.Set as Set
getInts :: IO [Int]
getInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <
gt; BS.getLine
main :: IO ()
main = do
[n, m] <- getInts
xs <- replicateM m getInts
let s1 = foldl f Set.empty xs
s2 = Set.fromList [(a, b) | a : as <- tails [1 .. n], b <- as]
diff = Set.difference s2 s1
print $ Set.size diff
where
f set as = do
let as' = zipWith (\a b -> if a < b then (a, b) else (b, a)) as (tail as)
foldl (flip Set.insert) set as'
```
----
## [C - Dash](https://atcoder.jp/contests/abc303/tasks/abc303_c)
実装問題だった。実装はやっつけ...
- `(現在の座標、現在の残りHP数、消費したアイテム)` の3つの値をコンテキストにして、畳み込みで `RLRURUR....` の指示に従って状態遷移を繰り返す
- 状態の履歴を `scanl` で全て記録しておく。その履歴の中の残りHP に着目し、負になることがあったら NG。そうでなければ OK
- Haskell の `Data.Set` には $O(\log n)$ の `delete` 関数があるので消費したアイテムは元のアイテム集合から削除することも考えたが、アイテム集合が書き換わるとコンテキストの把握がめんどくさいので、別途管理した。
```haskell
import Control.Monad (replicateM)
import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import Data.List (unfoldr)
import qualified Data.Set as Set
getInts :: IO [Int]
getInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <gt; BS.getLine
type Context = ((Int, Int), Int, Set.Set (Int, Int))
main :: IO ()
main = do
[_, m, h, k] <- getInts
s <- getLine
xys <- replicateM m $ do
[x, y] <- getInts
return (x, y)
let items = Set.fromList xys
context = ((0, 0), h, Set.empty)
cs = scanl (f k items) context s
hs = map (\(_, hp, _) -> hp) cs
putStrLn $ if all (>= 0) hs then "Yes" else "No"
where
f :: Int -> Set.Set (Int, Int) -> Context -> Char -> Context
f k items ((x, y), h, used) si = do
let ti = next si (x, y)
h' = updateH k items used ti (h - 1)
used' = if Set.member ti items && (h - 1) < k then Set.insert ti used else used
(ti, h', used')
where
next 'R' (x, y) = (x + 1, y)
next 'L' (x, y) = (x - 1, y)
next 'U' (x, y) = (x, y + 1)
next 'D' (x, y) = (x, y - 1)
next _ _ = error "unknown"
updateH k is ud xy hp
| hp < 0 = hp
| hp >= k = hp
| Set.notMember xy is = hp
| Set.member xy ud = hp
| otherwise = k
```
----
## [D - Shift vs. CapsLock](https://atcoder.jp/contests/abc303/tasks/abc303_d)
DPでした。もてる力を全て注ぎ込んだため、解けた頃にはもう E を解く気力が残っていなかった。いや、時間が残っていなかったんだけどね。
- Caps Lock を押したほうがいいのか、押さずにそのまま入力し続けたほうがいいのかを都度最適な方を選ぶ... という問題
- Caps Lock を押すか、押さないかを考える場面は `AAAAaaaAAaa` と続く文字の大文字と小文字が切り替わる場面
- それ以降 Caps Lock を押したほうが、押さないときよりもコストが小さくなるなら、押す
Caps Lock を押す / 押さないの判断は連続する文字の切り替わりのタイミングなので連長圧縮をする。その上で、区間ごとに Caps Lock を押した場合、押さなかった場合のコストを計算する。
最初は DP をしないで進めていた。つまり、前後区間の文脈を考慮せずに特定区間でどっちが最適かだけを比較してコスト計算を行なった。が、これが WA になった。
https://atcoder.jp/contests/abc303/submissions/41764510
コメントに書いてるとおり、対象区間のコストが同じなったケースを考慮できていないし、直感的にも、目の前のことだけでなく先々のことを考えると Caps Lock の状態を維持すべきかしないべきかは目の前のことだけでは定まらないことはわかる。
というわけで前後の文脈を考慮する、ということは DP だなと思い直し、それまでの実装をベースに DP に切り替えた。
DP は、先日から Twitter 上でもぶつくさ言いながら試していた Immutable かつ遅延評価DP ではない、DP で実装してうまくいった。これは自分的にグッジョブ。
反省としては、直感的に文脈の考慮がいるのは最初からわかっていたのに、希望的観測に身を委ねて非DPでやってしまったところ。DP にいくとはまってしまうことが多く、それを避けたいがために、DP でなければいいな...と考えてしまった。
DP かどうかは
- 部分構造最適性
- 部分問題重複性
の2点が成立しているときだというのは頭でわかっている。一旦立ち止まってちゃんとそれを考えて、余計な回り道をせずに DP を選択する、ということが必要。もっというと、そういうことを直感で判断できるレベルまで訓練しないといけない
```haskell
{-# LANGUAGE TypeApplications #-}
import Data.Array.IArray (accumArray, assocs, listArray)
import Data.Array.Unboxed (UArray, elems)
import qualified Data.ByteString.Char8 as BS
import Data.List (foldl')
rle :: BS.ByteString -> [(Char, Int)]
rle = map (\x -> (BS.head x, BS.length x)) . BS.group
cost :: Int -> Int -> Bool -> (Char, Int) -> Int
cost x _ False ('a', k) = x * k
cost _ y False ('A', k) = y * k
cost _ y True ('a', k) = y * k
cost x _ True ('A', k) = x * k
cost _ _ _ _ = error "Invalid input"
solve :: Int -> Int -> Int -> [(Char, Int)] -> UArray Bool Int
solve x y z xs = do
let dp = listArray (False, True) [0, z]
foldl' transition dp xs
where
transition :: UArray Bool Int -> (Char, Int) -> UArray Bool Int
transition dp (c, k) = do
-- 空間を取りうる状態全てに拡げて...
let expand = concatMap (\(caps, v) -> f (caps, v) (c, k)) $ assocs dp
-- 元の空間に畳み込んで写像する (最適な状態を選択する)
accumArray min maxBound (False, True) expand
f (caps, v) (c, k) = [(caps, v + cost1), (not caps, v + cost2)]
where
cost1 = cost x y caps (c, k)
cost2 = cost x y (not caps) (c, k) + z
main :: IO ()
main = do
[x, y, z] <- map (read @Int) . words <gt; getLine
s <- BS.getLine
let dp = solve x y z (rle s)
print $ minimum $ elems dp
```
----
## [E - A Gift From the Stars](https://atcoder.jp/contests/abc303/tasks/abc303_e) (コンテスト後にAC)
コンテストが終わって、今朝解いた。感覚的には D よりも E の方が簡単だった。
ただし、問題文がややこしかったが、入力例3つのグラフを実際に手で書いてみたらすぐ構造は理解できた。
星の中心になっている頂点を探して、その頂点の次数を調べる。
星の中心は図を見ても割と簡単に気づける。適当な葉から出発したとき、必ず決まった距離周期で繰り返し登場する。具体的には最初は葉の $1$ 個先。以降は $2$ 個とんで次にでてくる。`[1, 4, 7, 10, ...]` なので `mod 3` をとって `1` になるところが中心。
![[IMG_2627 2.jpeg]]
中心が分かれば、あとは次数がわかればレベル $k$ が判定できるので、隣接リストから次数を数えるだけ。
```haskell
import Control.Monad (filterM, forM_, replicateM)
import Data.Array.IArray (Array, accumArray, (!))
import Data.Array.ST (MArray (newArray), readArray, runSTUArray, writeArray)
import Data.Array.Unboxed (UArray, assocs)
import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import Data.Ix (Ix)
import Data.List (foldl', sort, unfoldr)
import Data.Sequence (Seq (Empty, (:<|)), (|>))
import qualified Data.Sequence as Seq
getInts :: IO [Int]
getInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <gt; BS.getLine
getTuple :: IO (Int, Int)
getTuple = do
[a, b] <- getInts
return (a, b)
graph2 :: Ix i => (i, i) -> [(i, i)] -> Array i [i]
graph2 (s, e) uvs = accumArray (flip (:)) [] (s, e) uvs'
where
uvs' = concatMap (\(u, v) -> [(u, v), (v, u)]) uvs
bfs :: Ix a => (a, a) -> (a -> [a]) -> [a] -> UArray a Int
bfs (s, e) edges v0s = runSTUArray $ do
dist <- newArray (s, e) (-1) -- -1 は未訪問
forM_ v0s $ \v0 -> do
writeArray dist v0 0
bfs_aux (Seq.fromList v0s) dist
return dist
where
bfs_aux Empty _ = return ()
bfs_aux (v :<| q) dist = do
us <- filterM (fmap (== -1) . readArray dist) (edges v)
d <- succ <gt; readArray dist v
forM_ us $ \u -> do
writeArray dist u d
bfs_aux (foldl' (|>) q us) dist
main :: IO ()
main = do
n <- readLn
uvs <- replicateM (n - 1) getTuple
let g = graph2 (1, n) uvs
-- 適当な葉を見つけてそこから BFS
let (leaf, _) = head $ filter (\(u, vs) -> length vs == 1) $ assocs g
dist = bfs (1, n) (g !) [leaf]
-- 「星」の中心は必ず葉から `mod 3` == 1 の距離にある
vs = map fst $ filter (\(_, d) -> d `mod` 3 == 1) $ assocs dist
-- レベル (次数) に変換して出力
putStrLn . unwords . map show $ sort $ map (\v -> length (g ! v)) vs
```
----
## 感想・反省など
Rated での本戦参加は 4回目。今回も 4問解くことができた、自分としては及第点。
ただ、Twitter でフォローしている人たちは5完以上の人が多かった。強そうな人たちが多いので当然なんだけれども。4完と5完の間に高い壁を感じる。難易度というよりは時間的な壁かなあ。前回も今回も、山場の D 問題でほぼ時間を使い切ってしまっているので、D 問題ぐらいまで「はいはい〜」と鼻歌歌いながら解けるぐらいにならないと、E まで到達できなそう...
今回の問題を考えると E 到達時点で残り40分ぐらいあれば解けそうな感じがするので、D までを 60 分以内で済ませる、というのが 5 完達成のためのだいたいの目算ということになるかなあ。すると、今回の D の時のように、途中で戦略を大きく転換するみたいな時間のロスは許されないなあと思うなど。
とはいえ、そんなに一気に次のレベルに到達しようと焦っても良くないので地道に続けていく。何にせよ焦りは禁物であーる。一足飛びに、自分がすごくなるなんていう妄想を抱いてはいけないのだ。
## 緊張対策
- 今回も X Japan の Prologue (World Anthem) で入場曲をかけて願掛け
- A, B, C を解いてるあたりで呼吸がうまくできていないことに気づき、深呼吸をなん度もした
- C が解けたところで一旦落ち着いて、トイレにいった
- D で WA を出したところで、一度机を離れて家の中をうろうろしたが、これでバイアスが取れたのはある
本線はメンタルとの戦いだなあ。
## そのほか実践していること
- atcoder-cli と online-judge-tools は必須。テストは普段は VSCode のターミナルで走らせているが、ややこしくなってきた時は出力をより広く見たいので、iTerm2 を隣にスタンバイさせている
![[スクリーンショット 2023-05-28 8.56.03.png]]
- 関数がややこしい時は haddock で動作確認。print デバッグせずに済む
- 問題を提出している間に git commit してチェックポイントを作っておく (WA が続いて戻すときなどに混乱しないよう)
- Dash で Haskell のドキュメントをすぐ引けるようにする。とても便利で、日常的に使っている。`Data.Set` の `delete` は $O(n)$ だっけ $O(\log n)$ だっけ? みたいな、日頃は頭に入っているようなことも本番の緊張で自信がなくなったりするので、すぐ正しい情報が参照できるよう。
![[スクリーンショット 2023-05-28 8.56.45.png]]
そのほかブラウザ拡張なども必要なものは入れている。本番中は些細なことが気になったりするので、そういう原因になりそうなものは、なるべく事前準備で取り除いておきたい。こういう作法もおすすめ、というのがあったら教えてください。