# ABC317 振り返り
- [ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317） - AtCoder](https://atcoder.jp/contests/abc317)
- 成績 ABCD 4完 (1065) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc317)
- 前回 [[ABC315 振り返り]]
ABCD 4完のパフォーマンス 1065 でレートが 🟢 緑色になりました。
ここ数回、緑にリーチがかかっているにもかかわらず足踏みしていましたが、ようやく突破できました。
先日 [AtCoder Jobs に会社の求人がいつの間にか出てた](https://jobs.atcoder.jp/offers/798) のですが、要求ランクが緑に設定されていて戦慄していました。これでなんとか弊社に入社できそうです。
緑になったら入緑記事を書くかなーと思ってましたが、そんな大袈裟なものでもないのでこの振り返りの末尾にでも軽く振り返りする程度に留めます。その辺は後ほど。
もとい、ABC317 です。4完ではあったのですが、今回も少し悔しかったですね。
というのは 5問目の E 問題、解法は合っていたのですが細かいところの実装を詰めきれずに TLE。あと 100ms だけどうしても縮めることができずに終わってしまいました。前回に続き、解けるはずの問題に対する詰めの甘さが残りました。
とはいえ、ABCD まではスムーズに 40分程度で解くことができました。その時点では水色パフォーマンスぐらいを発揮できていて、そこそこ戦えたかなと思います。ラスト 1マイルをしっかり取り切ることを意識していきたいです。
ところで今回はポケモンの開発会社さんが主催だったこともあり問題に色々ポケモンネタが散りばめられていたようですね。Twitter をみているとそのことで方々盛り上がっていたようですが、ポケモン世代ではないので話題に混ざることができませんでした 😇 スクエニさんスポンサードのドラクエ回をぜひお願いしたいです。
----
## [A - Potions](https://atcoder.jp/contests/abc317/tasks/abc317_a)
- [提出 #44939286 - ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）](https://atcoder.jp/contests/abc317/submissions/44939286)
モンスターの体力を $X$ 以上に回復させたい、どのポーションを使うのがもっともリソースマネジメント的に合理的か。
ポーションの値を出力するのではなく、索引を出力する必要があるのに気づかず「あれ、テスト通らんな?」と1、2分考え込んでしまいました。
```haskell
main :: IO ()
main = do
[_, h, x] <- getInts
ps <- getInts
let x' = minimumOn snd . filterOnSnd (>= x) $ zip [1 ..] (map (+ h) ps)
print (fst x')
```
----
## [B - MissingNo.](https://atcoder.jp/contests/abc317/tasks/abc317_b)
- [提出 #44943666 - ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）](https://atcoder.jp/contests/abc317/submissions/44943666)
連続する整数列の中で歯抜けになっている数が一つあるのでそれを特定せよ。
両端の数字いずれかがなくなってるケースは「なくした整数が一意に定まる」という制約で考える必要がないというのにすぐに気づけたのは良かったです。$N$ や $A_i$ は十分に小さいので補集合でガッとやってしまいます。
```haskell
main :: IO ()
main = do
_ <- readLn @Int
as <- getInts
let l = minimum as
r = maximum as
let s1 = IS.fromList as
s2 = IS.fromList [l .. r]
print $ IS.findMin $ IS.difference s2 s1
```
----
## [C - Remembering the Days](https://atcoder.jp/contests/abc317/tasks/abc317_c)
- [提出 #44955097 - ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）](https://atcoder.jp/contests/abc317/submissions/44955097)
重みつきグラフが与えられる。任意の頂点から出発して同じ頂点を二度は通らないという制約で移動したとき最大距離はいくつか?
任意の二頂点間距離、同じ頂点は二度通れない。DFS や BFS などの探索で解こうとすると少しはまりそうな問題です。
ここでよく見ると頂点数が $N \leq 10$ と小さい。これは全部試しなさい、ということですね。
スタート $s$ とゴール $t$ の組み合わせ $(s, t)$ を全部生成して... というのでもいいのですが、$N \leq 10$ ならそもそも経路を全て順列で生成して間に合います。経路が生成できるなら DFS は必要ありません。
途中で辺が途切れてるケースを考慮せずに 1WA 出してしまいましたが、落ち着いて考えてリカバリーして AC しました。
けんちょんさんもツイートしていましたが ABC054 の [C - One-stroke Path](https://atcoder.jp/contests/abc054/tasks/abc054_c) の類題ですね。
One-stroke Path はけんちょんさんの鹿本に載っていたこともあって何度か解いてました。おかげで上記の発想につながりました。
当時は水色の問題なんですね。今回結構この C で難儀していた人も多かったようで、それも頷けます。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvw <- replicateM m $ do
[u, v, w] <- getInts
return [((u, v), w), ((v, u), w)]
let es = accumArray @UArray (+) 0 ((1, 1), (n, n)) $ concat uvw
xs = permutations [1 .. n]
ds = map f xs
where
f path = do
let edges = zipWith (curry (es !)) path (tail path)
sum $ takeWhile (> 0) edges
print $ maximum ds
```
----
## [D - President](https://atcoder.jp/contests/abc317/tasks/abc317_d)
- [提出 #44962213 - ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）](https://atcoder.jp/contests/abc317/submissions/44962213)
DP です。拙作の畳み込み DP フレームワーク `accumDP` が火を吹きました🔥
各選挙区で多数派になるだけを考えると議席が過半数に至らない可能性があるし、議席のことだけを考えると多数派になるために必要以上のコストを支払うことになる。貪欲法は難しそう。どの選挙区で勝つのが最適か、つまり、一つ一つの選挙区を「選ぶか、選ばないか」という分岐です。選ぶ、選ばないの分岐と言えば DP ですね。
過半数の議席を獲得するためには状態としては $Z_i$ の総計の $1/2 + 1$ 議席が必要です。それを $M$ としたとき、選挙区を選ぶ・選ばないを決めて行って $M$ 以上の数を作ることができるか? を DP します。
$Z_i$ の総計は最大で $10^5$ とやや大きめですが $N \leq 100$ しかないので十分に DP できるサイズです。
ABC204 [D - Cooking](https://atcoder.jp/contests/abc204/tasks/abc204_d) に少し似ています。目指したい数は総計の半分 (この問題では過半数) であり、その値を部分和で作ることができるかどうか。
[[ABC312 振り返り]] で括弧数の DP の問題が解けなかったことを反省に、ここ最近は DP を訓練してました。
その成果を発揮できて良かったです。
```haskell
-- >>> cost 3 8
-- >>> cost 7 2
-- 3
-- 0
cost x y = do
let z = ((x + y) `div` 2) + 1
max 0 (z - x)
main :: IO ()
main = do
n <- getInt
xyz <- replicateM n $ do
[xi, yi, zi] <- getInts
return (xi, yi, zi)
let total = sum $ map (\(_, _, z) -> z) xyz
m = (total `div` 2) + 1
xs = map (\(x, y, z) -> (cost x y, z)) xyz
let dp = accumDP @UArray f min maxBound (0, m) [(0, 0)] xs
where
f (w, v) (ci, zi)
| v == maxBound = []
| otherwise = [(min m (w + zi), v + ci)]
print $ dp ! m
```
----
## [E - Avoid Eye Contact](https://atcoder.jp/contests/abc317/tasks/abc317_e) (コンテスト後にAC)
- [提出 #44987691 - ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）](https://atcoder.jp/contests/abc317/submissions/44987691)
うってかわって悔しみの E 問題。
人間の視線が届くマスにあらかじめチェックを入れて、BFS する。
解法だけでいえば、そこまで難しい問題ではないです。が、この問題は $H, W \leq 2000$ とややグリッドが大きめなので、実装をちゃんとやらないと間に合わない、そんな雰囲気がしました。
そして案の定、テストケース一つだけ TLE して取れない...!
![[スクリーンショット 2023-08-26 22.40.38.png]]
60分近く残り時間があり、22:10 には実装は出来上がっていましたがそこから 30分悪戦苦闘するも、時間切れとなりました。
以下、うだうだと言い訳です。
何が悪かったかといえば、視線チェックのマーキングをする際に `#` や `>` などもうそれ以上は視線が届かないよ、というところまで見たら処理を切り上げる、これをサボったのが原因でした。障害物に当たったら視線を伸ばすのを打ち切る、という処理を入れたら 600ms で AC しました。
なぜそんな程度のことが 30分も時間があって、できなかったのか。
そうです、 Haskell は早期 return が気軽にできないんです。私だってそりゃあ、return して大域脱出したかったわけですよ!
Haskeller、こういうときに沼りがち。
そしてコンテスト中は、グリッドを更新する必要があるということで MArray (更新可能な配列) を選択しました。これを使うとモナドを意識した実装が必要になります。UArray (イミュータブルな配列) であれば `iterate` と `takeWhile` を使って再帰を途中で打ち切る、という実装は比較的シュッと書けます。しかし Haskell にはこの `takeWhile` のモナディックバージョンが、ないのです!
いやー、コンテスト中は頭が凝り固まってますね。ないなら自分で実装すればいいのに「`takeWhile` がない、簡単に処理が打ちきれない」となって、それ以外の箇所で速度をあげようと躍起になってしまいました。今朝起きて「ん、別に `takeWhileM` を自分で実装すればいいんジャマイカ?」と気づきやってみたところ、あっさり AC しました ＼(^o^)／
「~~甲子園~~ ABC には───
魔物が住んでいる──」
ザ・ファブル風に言ってみたところで、もうスコアは上がりません。
涙で枕を濡らしながら `takeWhileM` を自作ライブラリ集に入れました。これで二度と同じ過ちは繰り返さないでしょう。
## グリッドを MArray で更新
```haskell
around :: (Int, Int) -> [(Int, Int)]
around v = map (v `to`) [(1, 0), (0, 1), (-1, 0), (0, -1)]
where
to (x, y) (x', y') = (x + x', y + y')
reachable :: Ix v => UArray v Char -> v -> Bool
reachable grid v
| (not . inRange (bounds grid)) v = False
| grid ! v == '.' = True
| grid ! v == 'G' = True
| otherwise = False
main :: IO ()
main = do
[h, w] <- getInts
ss <- replicateM h BS.getLine
g <- newListArray @IOUArray ((1, 1), (h, w)) $ BS.unpack (BS.concat ss)
b <- getBounds g
let updateGrid (dx, dy) (i0, j0) = do
us <-
takeWhileM
( \u -> do
c <- readArray g u
return $ c `elem` ['.', '!']
)
$ takeWhile (inRange b) $
iterate (\(i, j) -> (i + dx, j + dy)) (i0 + dx, j0 + dy)
forM_ us $ \u -> do
writeArray g u '!'
forM_ (range b) $ \v -> do
!c <- readArray g v
case c of
'v' -> updateGrid (1, 0) v
'>' -> updateGrid (0, 1) v
'<' -> updateGrid (0, -1) v
'^' -> updateGrid (-1, 0) v
_ -> return ()
g' <- freeze g :: IO (UArray (Int, Int) Char)
let es = filter (\(_, c) -> c == 'S' || c == 'G') $ assocs g'
s = fst . head $ filter (\(_, c) -> c == 'S') es
t = fst . head $ filter (\(_, c) -> c == 'G') es
let dist = bfs (filter (reachable g') . around) (-1) ((1, 1), (h, w)) [s]
print $ dist ! t
```
## グリッドを UArray + accum で更新
```haskell
around :: (Int, Int) -> [(Int, Int)]
around v = map (v `to`) [(1, 0), (0, 1), (-1, 0), (0, -1)]
where
to (x, y) (x', y') = (x + x', y + y')
reachable :: Ix v => UArray v Char -> v -> Bool
reachable grid v
| (not . inRange (bounds grid)) v = False
| grid ! v == '.' = True
| grid ! v == 'G' = True
| otherwise = False
main :: IO ()
main = do
[h, w] <- getInts
ss <- replicateM h BS.getLine
let grid = listArray @UArray ((1, 1), (h, w)) $ BS.unpack (BS.concat ss)
updates = concatMap f $ range (bounds grid)
where
f v = do
case grid ! v of
'v' -> g (1, 0) v
'>' -> g (0, 1) v
'<' -> g (0, -1) v
'^' -> g (-1, 0) v
_ -> []
g (dx, dy) v@(i0, j0) = do
let us =
takeWhile (\u -> inRange (bounds grid) u && grid ! u `elem` ['.', '!']) $
iterate (\(i, j) -> (i + dx, j + dy)) (i0 + dx, j0 + dy)
map (\u -> (u, '!')) us
grid' = accum (flip const) grid updates
let es = filter (\(_, c) -> c == 'S' || c == 'G') $ assocs grid'
!s = fst . head $ filter (\(_, c) -> c == 'S') es
!t = fst . head $ filter (\(_, c) -> c == 'G') es
let dist = bfs (filter (reachable grid') . around) (-1) ((1, 1), (h, w)) [s]
print $ dist ! t
```
----
## 感想・反省など
ABC317 の感想と、緑色になったことへの簡単な振り返りです。
## ABC317
前回の ABC315 は時間がなくてコンテスト前の有酸素運動をしなかったら、過度な緊張が発生してしまいました。
今回も運動はできなかったのですが、昼にストレッチ屋さんに行き本戦前に熱い風呂に入って汗を流しました。
結果、やはり緊張は適度なところで抑えられました。
本戦前にメンタルを整えるのは重要ですね。有酸素運動や温浴によって副交感神経優位になり、本戦が始まって交感神経優位になっても適当なところで抑え込むことができるのでしょう。次回以降も、ここはしっかり実践していきたいと思います。
今回は D を解いた時点で順位表を見てみたところ 1454 位となかなか良いペースで問題を解くことができました。もしかしたら水色パフォーマンスいけるかなと思いましたが冒頭の通り E で転んでしまいました。ここが今の実力だと思います。
![[スクリーンショット 2023-08-27 8.36.36.png]]
## 緑色になった
元はといえば Haskell をちゃんと書けるようになりたいと思って始めた AtCoder でしたが、今年の 5月に力試しと思い、Haskell でコンテストに出て (緊張のあまり初回は A 1完で終わるという洗礼を浴びつつ) 数ヶ月かけてここまで来ました。
まだレートは 803 でギリギリなので、次回もちゃんとスコアを出さないといけません。安心はできません。
次の目標は水色といきたいところですが、そもそもまだ水色パフォーマンスを出せたこともないですし、まずは緑半分ぐらいを目指したいと思います。千里の道も一歩から。地道にやっていくのが自分の性にはあってます。
![[スクリーンショット 2023-08-27 8.42.10.png]]
こうしてみてみると順調に見えますが、実際には本戦に初めて出る5月よりも前に助走期間があり、コンテストに出るために本格的に練習し始めたのは年が明けての 2月くらいからだったと思います。
緑色になってみて思ったのは「当初思っていたよりも難しかった」というのが正直な感想です。自分でやってみて認識を改めました。
最近方々でよく見かけますが、以前に比較すると緑色になる難易度が上がっていそうですね。
方々のブログを読んだりする限り要求されるアルゴリズムの種類自体は以前からあまり変わっておらず基礎的なものに限定されているように思いますが、相対的には、一つ一つのアルゴリズムの基礎や原理・実装に対する理解度が高くないと、他の同レート帯にいる人たちに遅れをとってしまう実感があります。少し昔の問題をやると「この問題で緑色かあ、今の茶色の方が難しいかもな」と思うようなこともよくあります。
ここまでの自分なりの練習方法というと、特徴めいたものもそれほどないような気がしますが、この振り返りも含めて記録をまめにつけているというのはあります。私の場合何かを書くというのは、記憶のためではなく自分自身と対話して対象をより深く考察するための手段です。
- [「書く」のは特別な道具 - naoyaのはてなダイアリー](https://naoya-2.hatenadiary.org/entry/20131107/1383792634)
あとは Longest Streak を繋げることよりも、過去に解いた問題を時間を置いてから解き直すことを重視しています。自力で解けなかった問題はスプレッドシートにまとめておいて、時々そのストックから問題を取り出して解くとか、DP が弱いな、と思ったら過去に解いた DP の問題を一覧化してもう一度全部解くとか。これが結構、力になっていると思います。元々記憶力が良い方ではないので、一度解いただけでは、ほぼ忘れてしまいます。繰り返し問題を解くことで各問題やアルゴリズムの奥にある抽象構造を見つけて、他の類似したそれと結びつけることによってより深く記憶に刻んでいく、ということを意識してやってます。
実は、ここ最近は以下の大学受験の問題集をやってます。
- [合格る確率+場合の数 (大学受験 合格る) | 広瀬 和之 |本 | 通販 | Amazon](https://www.amazon.co.jp/dp/4578240835/)
競技プログラミングをやっていると「数え上げ」の問題がときどきでますが、解けてもなんだか「ふわふわ」としか理解できてない感があって何かおかしいとずっと思っていました。あるとき他のプログラマーの方のブログを読んでいて、どうもこの辺の分野は最近の人たちは中学・高校受験や大学受験のときにやっていて、一定層の人たちにとっては身体に染みついた感覚のものであるということを知ります。
一方の私はと言いますと、当時は「場合の数」や数論、確率統計などの分野は受験の必須分野ではなかったこともあり重点的に学ぶことがありませんでした。もちろん「組み合わせ」や「順列」程度は知っていたのですが、たとえば「仕切りを入れて数える」とかそういう計算の対処法みたいなものはほぼ訓練されていないに等しい。計算が身体化されてない感があります。微分積分や三角関数、ベクトル、行列計算なんかは忘れていたものを問題を解きながら思い出すことによって身体感覚としてそれを取り戻すことができてる感があるのですが、そもそも一度も身体化できてない分野なので、そう言う感覚がなかったのが、ふわふわしていることの正体でした。
そしてこの分野に対する解像度が低いことが、実は数え上げの問題に限らず、競技プログラミング全般至る所に影響していることに最近になって気がつきました。
まだ問題集は半分も終わらせていませんが、その程度でも明らかに自分の実力が底上げされている感覚がわかります。やはり基礎は大事だなと思いました。
この歳になって必死こいて受験勉強みたいなことをしてるのも、なんだか恥ずかしいなと思うのですが、こういう時に決まって読んでいる記事が一つあります。これは、ちょっと貼っておこう。
- [僕は自分が思っていたほどは頭がよくなかった - しのごの録](https://b.log456.com/entry/20120110/p1)
> うまくやる学生はそういう困難にぶつかったとき、自分の力不足と馬鹿さ加減に滅入る気持ちと闘い、山のふもとで小さな歩みを始めます。彼らは、プライドに傷がつくことは、山頂からの景色を眺めるためであれば取るに足らないということを知っているのです。
いい話です。
···と言いつつ、本戦に出れば力がつくのは早い段階からわかっていたのに「まだ早い」となかなか踏ん切りがつかず5月になるまで出てなかった自分がいたわけですが。コンテストに出る準備が整ってなかったわけではなく、単に、コンテストに出て、自分の力の無さ加減を自分自身で知ることが怖くて一歩を踏み出せなかっただけです。
本戦でメンタルを整えることもそうですし、こういう自分の凝り固まった余計なプライドとの戦いもそうですが、競技プログラミングは結構自分の内面との戦いの連続、と言う感じがします。歳をとるとこう言う機会はなかなかないので、自分を謙虚に保つという意味でも、とても良いことだと思っています。
## Haskell
コンテストのための訓練を始めたのは年が明けてからですが、AtCoder の問題を Haskell で解くのを始めたのは去年の 7月もう一年前です。最初は問題を解くというより Haskell を書くこと自体に四苦八苦していました。
今となっては「Haskell の文法が出てこない」ということはさすがになくなり、仕事で使っている TypeScript や Python などよりも Haskell の方が、おそらく基本的な計算に関しては早く書けると思います。
ただ、やはり暦1年程度なので、今回の E 問題のように `takeWhileM` の実装を手元に持っていないみたいな経験不足からニッチなケースに対応できないということはたまにあります。この辺は AtCoder を続けていきながら、経験を通じて一つ一つ潰していくしかないでしょう。
Haksell という言語はとても奥が深くて、緑色コーダーになる頃には「チョットデキル」ぐらい言えるかなあと思ってたんですが、いやあ、全然です。もちろん、奥深くて、とても面白いです。元々は Rust や TypeScript を書くための腰掛けとして始めた Haskell トレーニングだったのですが、すっかり Haskell の虜になってしまいました。
Haskell で AtCoder をやっている人は多くありませんが、他の Haskeller の皆さんは gksato さん、cojna さん、unnohideyuki さん、toyboot4e さん、joetheshootingst さんをはじめすごい人たちばかりでとても刺激になります。
Haskell をやってると計算の深淵がふと垣間見える、不思議なプログラミング言語です。