AIで解説 AtCoder攻略　格子構成

格子構成ページの位置づけ

項目	内容
必修度	発展
学習目安	発展
前提	GCD・座標
対象問題	1問（推定値あり1問、未算出0問）

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

学習目安	difficulty推定値	問題数
入門	difficulty < 0	0
標準	0〜799	0
標準〜発展	800〜1199	0
発展	1200以上	1
未算出	—	0

移動距離、GCD、偶奇の条件を確認し、整数格子上の経路を直接構成します。

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

格子構成の見分け方

1回の移動距離が固定されている
到達可能性が距離や偶奇で決まる
答えとして座標列を出力する

格子構成の実装前チェック

到達不能条件を先に分ける
GCDで方向を正規化する
出力する移動回数と座標の差を検算する

先に確認する文法・ライブラリ

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

代表問題で実装を確認する

最初の一問として、ABC135 E Golf（公式解説）を解きます。移動距離Kの点列を構成する問題です。まず偶奇で不可能判定をし、座標を第一象限へ移してから、K歩ずつ進み、最後を2〜3歩で調整します。

def two_moves(dx, dy, k):
    """(dx, dy)を2回のマンハッタン距離Kの移動で作る。"""
    sx = 1 if dx >= 0 else -1
    sy = 1 if dy >= 0 else -1
    ax, ay = abs(dx), abs(dy)
    distance = ax + ay
    half = distance // 2
    extra = k - half
    if ax >= ay:
        first = (half, -extra)
    else:
        first = (-extra, half)
    first = (sx * first[0], sy * first[1])
    second = (dx - first[0], dy - first[1])
    return first, second

K = int(input())
X, Y = map(int, input().split())
sign_x = 1 if X >= 0 else -1
sign_y = 1 if Y >= 0 else -1
target_x, target_y = abs(X), abs(Y)
distance = target_x + target_y

if K % 2 == 0 and distance % 2 == 1:
    print(-1)
else:
    if distance == K:
        answer = [(target_x, target_y)]
    else:
        strokes = (distance + K - 1) // K
        if strokes == 1:
            strokes = 2 if distance % 2 == 0 else 3
        elif (strokes * K - distance) % 2 == 1:
            strokes += 1

        answer = []
        current_x = current_y = 0
        for _ in range(strokes - 2):
            if current_x + K <= target_x:
                current_x += K
            else:
                current_y += K
            answer.append((current_x, current_y))

        first, second = two_moves(target_x - current_x, target_y - current_y, K)
        current_x += first[0]
        current_y += first[1]
        answer.append((current_x, current_y))
        answer.append((target_x, target_y))

    print(len(answer))
    for x, y in answer:
        print(sign_x * x, sign_y * y)

出力する点数をLとするとO(L)時間・O(L)メモリです。出力そのものが必要なので、点を一度保存します。