どの走査を選ぶかは、答えがどこに集まるかで決めます。全マスや列ごとの集計なら行と列を一度ずつ走査し、1つの始点から境界や壁までを見るなら上下左右へ進みます。同じ壁区間を多くのマスで使うなら区間長を前計算します。到達可能性や最短距離を求めるときは、訪問状態を管理するBFSを選びます。
この判断を、ABC280 Aの問題ページ、ABC274 Bの問題ページ、ABC197 Bの問題ページ、ABC129 Dの問題ページの順に確かめます。各問題では公式サンプルを手で追い、問題の条件に対応するPythonコードへつなげます。
H行W列とgrid[row][column]を固定する
入力のHは上から下へ並ぶ行の数、Wは左から右へ並ぶ列の数です。コードでは行を0 <= row < H、列を0 <= column < Wとして、1つのマスをgrid[row][column]の順で指定します。
| 名前 | 表すもの | ループの範囲 |
|---|---|---|
row |
上から何行目か | range(H) |
column |
左から何列目か | range(W) |
外側のループをrange(H)、内側をrange(W)にすると、全マスを一度ずつ見る処理はH * W回です。この計算量はO(HW)と書けます。HとWを取り違えると、列ごとの答えの個数や添字がずれるので、問題文の行と列をコードの変数へそのまま対応させます。
ABC280 Aで全マスの#を数える
ABC280 A「Pawn on a Grid」の問題ページでは、H本の長さWの文字列で表される盤面から、#のマスの総数を求めます。解法は、行を読んだ時点でその行の#を数え、1つの答えへ加える走査です。公式の問題をまとめたABC280の公式Editorial案内も、問題の位置を確認する資料として参照できます。
公式サンプルを行ごとに追う
公式サンプル1の盤面は#....、.....、.##..の3行です。1行目から1、2行目から0、3行目から2を加えるので、合計は1 + 0 + 2 = 3になります。
正解Pythonコード
H, W = map(int, input().split())
answer = 0
for _ in range(H):
row = input().strip()
answer += row.count('#')
print(answer)正しさ、計算量、境界条件
各行を読み終えたとき、answerはそれまでに読んだ行に含まれる#の総数です。次の行の個数を加えるたびにこの関係が保たれるため、H行を読み終えた値が盤面全体の答えになります。各行の文字を合わせて各マスを高々一度判定するので時間計算量はO(HW)、現在の行を保持する追加メモリはO(W)です。盤面全体をO(HW)のメモリで保持することはありません。H = 1やW = 1、全てが.、全てが#の盤面も同じループで処理できます。
ABC274 Bで列ごとの個数を集計する
ABC274 B「Line Sensor」の問題ページでは、各列にある#の個数を、左の列から順にW個出力します。全マスを見る点はABC280 Aと同じですが、答えを1個へまとめず、列ごとの配列へ加える必要があります。問題ページからABC274 Bの公式Editorialへも移動できます。
公式サンプルを列ごとに追う
公式サンプル1の3行4列の盤面は#..#、.#.#、.#.#です。1列目の#は1個、2列目は2個、3列目は0個、4列目は3個なので、出力は1 2 0 3になります。3列目のように#が一つもない列も、最初の0を残して出力します。
正解Pythonコード
H, W = map(int, input().split())
count = [0] * W
for _ in range(H):
row = input().strip()
for c in range(W):
if row[c] == '#':
count[c] += 1
print(*count)正しさ、計算量、境界条件
count[c]は、そこまでに読んだ行の列cにある#の個数を表します。各行の列cを見て、#のときだけ1を加えるため、H行を読み終えたときのcount[c]は列c全体の個数です。出力する要素数はWで、全マスを一度見る時間計算量はO(HW)、列カウント配列の追加メモリはO(W)です。H = 1やW = 1でも、外側と内側の範囲がそのまま境界になります。
ABC197 Bで始点から上下左右へ進む
ABC197 B「Visibility」の問題ページでは、始点(X, Y)と同じ行または列にあり、始点との間に障害物がないマスの数を求めます。始点を固定するため、全マスを集計する二重ループではなく、上下左右の4方向を順に走査します。問題ページからABC197 Bの公式Editorialも確認できます。
公式サンプルを4方向に追う
公式サンプル1では、入力の始点(X, Y) = (2, 2)（1始まり）を0始まりの(1, 1)へ変換します。始点を1マスとして数え、コードが見る右隣は0始まりの(1, 2)、左隣は0始まりの(1, 0)、下隣は0始まりの(2, 1)です。入力表記に戻すと、これらは順に1始まりの(2, 3)、(2, 1)、(3, 2)です。上は隣のマスが障害物で、各方向は境界または#で止まるため、合計は1 + 1 + 1 + 1 = 4です。
正解Pythonコード
H, W, X, Y = map(int, input().split())
X -= 1
Y -= 1
grid = [input().strip() for _ in range(H)]
answer = 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
r, c = X + dr, Y + dc
while 0 <= r < H and 0 <= c < W and grid[r][c] == '.':
answer += 1
r += dr
c += dc
print(answer)正しさ、計算量、境界条件
始点は問題の条件で.なので、answer = 1で始点を一度だけ数えます。各方向は始点の隣から出発し、盤面内で.が続く間だけ1マスずつ加えます。盤面の外へ出るか#に当たった時点でその方向を終えるため、壁の向こう側を数えません。上下の移動は高々Hマス、左右の移動は高々Wマスなので、4方向の走査部分の時間計算量はO(H + W)です。掲載コードはH行W列の入力を読み、盤面をgridへ保持してから走査するため、コード全体の時間計算量はO(HW)、メモリはO(HW)です。走査中の4方向の変数に必要な追加メモリはO(1)です。始点が端にある場合やH = 1、W = 1の場合も、最初の境界判定でその方向を終えます。
ABC129 Dで横区間と縦区間を再利用する
ABC129 D「Lamp」の問題ページでは、空きマスに置いたランプが上下左右へ照らせるマス数の最大値を求めます。光は壁または盤面端で止まります。問題ページからABC129 Dの公式Editorialも確認できます。
公式サンプルを区間として追う
HとWが最大2000なので、各空きマスから毎回4方向へ歩くと、同じ横区間と縦区間を別のマスから何度も調べることになります。そこで、各行の壁で区切られた連続した.区間を見つけ、その長さを区間内の全マスへhorizontalとして配ります。各列でも同じ処理をして、verticalを作ります。
公式サンプル1の2行2列の空きマスを見ると、横方向は同じ行の5マス、縦方向は同じ列の4マスがつながっています。中心のマスは横にも縦にも含まれるため、照らせる数は5 + 4 - 1 = 8です。
正解Pythonコード
H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]
horizontal = [[0] * W for _ in range(H)]
for r in range(H):
c = 0
while c < W:
if grid[r][c] == '#':
c += 1
continue
start = c
while c < W and grid[r][c] == '.':
c += 1
length = c - start
for k in range(start, c):
horizontal[r][k] = length
vertical = [[0] * W for _ in range(H)]
for c in range(W):
r = 0
while r < H:
if grid[r][c] == '#':
r += 1
continue
start = r
while r < H and grid[r][c] == '.':
r += 1
length = r - start
for k in range(start, r):
vertical[k][c] = length
answer = 0
for r in range(H):
for c in range(W):
if grid[r][c] == '.':
answer = max(answer, horizontal[r][c] + vertical[r][c] - 1)
print(answer)正しさ、計算量、境界条件
横走査で見つけた1つの.区間では、区間内のどのマスから見ても横方向に届くマス数が同じです。その長さを区間内の各マスへ保存するので、horizontal[r][c]はマス(r, c)の横方向の範囲になります。縦走査も同じ理由でvertical[r][c]を正しく作ります。
空きマス(r, c)から見えるマスは横区間と縦区間の和集合です。両方に含まれるのは中心のマスだけなので、個数はhorizontal[r][c] + vertical[r][c] - 1です。コードはこの値の最大値を空きマスだけで比較し、壁を候補にしません。行と列の区間を見つけて各マスへ配る処理を含めても、各行と各列のマスを定数回扱うため時間計算量はO(HW)、horizontalとverticalの追加メモリはO(HW)です。壁が行や列の端にある場合、区間の探索は境界で止まり、区間が1マスだけでも長さ1として扱えます。
固定方向の走査とBFSを使い分ける
4問の違いは、同じグリッドを見ても、答えに必要な情報の単位が異なることです。次の表で、問題文を読んだ時点の判断を整理します。
固定方向の集計や可視範囲は走査で処理し、壁を越えずに到達できるか、最短距離はいくつかのように状態の広がりを答える問題ではBFSを使います。H、W、始点の添字、壁で止まる条件を先に固定すると、4問のコードを同じ見方で読み比べられます。
| 求めるもの | 選ぶ方法 | 条件の見分け方 |
|---|---|---|
| 全マスの合計 | 行と列の二重走査 | 各マスを一度判定すれば答えが作れる |
| 行または列ごとの集計 | 対応する配列へ加える走査 | 答えの個数がH個またはW個になる |
| 1つの始点から見える範囲 | 上下左右の走査 | 境界または壁に当たるまで同じ方向へ進む |
| 壁で区切られた範囲を多数のマスで共有 | 区間長の前計算 | 同じ横区間や縦区間を何度も使う |
| 到達可能性や最短距離 | BFS | 訪問済みか、始点から何手かという状態を広げる |
