ABC460 参加記 ― Dが時間内に通せなくて悔しかった話

📊 今回の結果

Cまでは悪くなかった

A（2:41）、B（12:36）とサクサク進んで、CのTwo Pointersも33分で通せた。

コンテスト後に確認すると、Cを 16:39 で通した人が 1100 パフォ、10分 で通した人が 1143 パフォ。自分の 33:18（887 パフォ）との差がそのままパフォーマンスに直結していた。速解きの練習が必要だと痛感した。

Cは最初「シャリとネタを複数回使えるのでは」と誤読して、二分探索アプローチを試みてしまった。問題文を読み直して1対1マッチングと気づき、Two Pointersに切り替え。ここで少し時間をロスしたのが悔やまれる。

😤 Dが悔しすぎた

Dは時間内に通せず、コンテスト後に20分でAC。これが一番悔しかった。

問題の概要

H×W グリッドに操作を $10^{100}$ 回繰り返す。

• 白マス：8近傍に黒マスがあれば → 黒に変わる
• 黒マス：→ 白に変わる

収束後の状態を求める。

どこで詰まったか

コンテスト中、「各内部セルから最近傍の境界セルまでの距離を測ろう」と内部セル起点で考えていた。この方向だと各セルごとに探索が必要になって複雑化する一方だった。

正しい発想

起点は境界セル（8近傍に異なる色があるセル）の側だった。

1. 境界セルを元の色のまま確定、BFSキューに追加
2. 内部セル（全隣接が同色）は未確定として管理
3. 確定済みの境界セルから多点BFSで内部に交互色を伝播

「外→内にスキャン」 という方向性に気づければシンプルに解けた。BFSの起点と方向は慎重に考えないといけないと痛感。

🔍 振り返り

今回の反省点はざっくり2つ。

• 問題文の誤読（C問題）：サンプルを先に見て条件を確認する癖をつける
• BFSの方向性（D問題）：「どこから広げるか」を最初に固めてから実装に入る

レートは +11 で地味に伸びたが、Dを通せていれば +40〜50 はあったはず。現在 781 で、緑（800） まであと19。Dが通せていれば今頃入緑していた。次回リベンジ。