トヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311)
まとめ
ABCDEの5完。
レーティング相当の振る舞いができた模様で、かろうじてプラス。
よくなかった
C, D と問題の制約を完全に読み解けておらず、過剰な実装をしてしまった。
特にCでは Functional Graph という特性を理解できていなかった。
よかった
前回以前はケアレスミスによるWAが多発していたので、今回はノーペナを意識した。達成できて良かった。
苦手っぽいE問題が解けた。インターネットと過去の記憶によりなんとか解けた。
復習として、2次元累積和の使い方もバッチリ定着させたはず。
問題ごとの感想
A - First ABC
長さ3のbool配列で状態管理しながらループを回した。
B - Vacation Together
縦軸をまとめたものをランレングス圧縮しました。
C - Find it!
DFSによる閉路検出は良く書いているので、今回も同じような実装を用いた。
入力条件によるグラフの特性をよく理解できていなくて、全ての頂点に対して検出してたり、訪問済フラグを「全体に対して」「今回に対して」で2種類管理したりとオーバーキル気味の実装をしてしまっていた。
D - Grid Ice Floor
BFSっぽい実装をベースにして探索。
マスの通過状態は「左右」「上下」の2種類で判定すれば無駄な再探索が発生しないようになる。
ただ、通過マスの状態を持って再探索の効率化を行わなくても十分に間に合う制約だった模様。
E - Defect-free Squares
2次元累積和を使ってナイーブ解を書いていたのだけど、そもそも対象範囲の穴の有無を判定するのが上手く書けずに沼っていた。
そもそも2次元累積和の習熟度がイマイチで、作り方も使い方もおぼついていないので DP っぽく解けないか考えを切り替えた。