AIで解説 AtCoder攻略　グリッド走査

グリッド走査ページの位置づけ

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

各マスから毎回四方向へ歩かず、行や列を先に走査して見える長さを保存します。二次元配列の境界処理が中心です。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

最初の一問として、ABC280 A Pawn on a Grid（公式解説）を解きます。グリッドを上から1行ずつ読み、各行の#の個数を足します。盤面を保持しなくても答えを出せます。

H, W = map(int, input().split())
answer = 0
for _ in range(H):
    answer += input().strip().count('#')
print(answer)

全マスを1回見るのでO(HW)時間、行をその場で処理すればO(1)追加メモリです。

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

問題	公式解説	出題意図	difficulty
ABC280 A Pawn on a Grid	公式解説	Count all ‘#’ cells in the grid.	-1011
ABC309 A Nine	公式解説	Check whether adjacent cells are all inside the 3×3 neighborhood.	-756
ABC296 B Chessboard	公式解説	チェス盤から特定文字を探し、列文字と行番号へ変換して出力する。	-622
ABC274 B Line Sensor	公式解説	Count black sensor cells in each column.	-449
ABC377 B Avoid Rook Attack	公式解説	各マスについて同じ行と列に障害物がない条件を走査する。	-432

問題	公式解説	出題意図	difficulty
ABC264 B Nice Grid	公式解説	中心からの距離の偶奇で格子の色を判定する。	-391
ABC458 B Count Adjacent Cells	公式解説	Count adjacent cells for each grid position.	-391
ABC416 B 1D Akari	公式解説	公式Editorialの方針を one dimensional lighting として整理する。	-390
ABC197 B Visibility	公式解説	Scan in four directions from the start cell until a wall and count visible cells.	-170
ABC157 B Bingo	公式解説	当選番号が付いたマスを管理し、3行・3列・2対角線のいずれかが全てマーク済みか調べる。	-128

問題	公式解説	出題意図	difficulty
ABC305 C Snuke the Cookie Picker	公式解説	Locate the unique missing wall cell by checking local boundary patterns.	30
ABC267 B Split?	公式解説	ピン配置を列のビットに写像し、中央が分割されているか判定する。	61
ABC302 B Find snuke	公式解説	Try each cell and eight directions to match the word snuke.	349
ABC300 C Cross	公式解説	各#を中心に上下左右へ伸びる連続長の最小値を調べ、最大の十字サイズを求める。	534
ABC269 D G. Do use hexagon grid	公式解説	六方向隣接する点をグラフとして連結成分数を数える。	612