AIで解説 AtCoder攻略　幾何 – 経理のAI仕訳帳

幾何ページの位置づけ

項目	内容
必修度	標準
学習目安	標準〜発展
前提	座標・浮動小数
対象問題	79問（推定値あり78問、未算出1問）

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

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

図形を座標とベクトルに置き換え、距離・内積・外積・交点を式で判定します。境界上を含むかを先に決めることが重要です。

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

幾何の見分け方

点や線分の位置関係を判定する
距離や角度の最大・最小を求める
図形の対称性を数式へ置き換えられる

幾何の実装前チェック

座標系と向きを固定する
平方根を避けられる比較は二乗で行う
同一直線・接触・端点を別ケースで確認する

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

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

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

最初の一問として、ABC174 B Distance （公式解説）を解きます。円の中にあるかは、平方根を取らずにx^2+y^2とD^2を比較できます。浮動小数点の誤差を避けて判定します。

N, D = map(int, input().split())
answer = 0
for _ in range(N):
    x, y = map(int, input().split())
    if x * x + y * y <= D * D:
        answer += 1
print(answer)

各点を1回判定するだけなのでO(N)時間、追加メモリO(1)です。

幾何の学ぶ順番

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

まず解く

問題	公式解説	出題意図	difficulty
ABC398 A Doors in the Center	公式解説	Place one or two central equals signs according to the parity of N and fill the remainder with hyphens.	-1093
ABC383 A Humidifier 1	公式解説	基準セルからのマンハッタン距離が範囲内のマスを数える。	-827
ABC407 A Approximation	公式解説	公式Editorialの方針を approximation rounding として整理する。	-698
ABC434 B Bird Watching	公式解説	公式Editorialの方針を bird watching geometry として整理する。	-657
ABC411 B Distance Table	公式解説	公式Editorialの方針を distance table として整理する。	-606

次に解く

問題	公式解説	出題意図	difficulty
ABC174 B Distance	公式解説	平方根を使わずx^2+y^2<=D^2を判定し、円内の点の個数を数える。	-495
ABC254 B Practical Computing	公式解説	両端1と直上2値の和の漸化式でパスカルの三角形を構成する。	-476
ABC373 B 1D Keyboard	公式解説	キーボード上の各文字位置を調べ、隣り合う入力文字間の距離を合計する。	-403
ABC253 B Distance Between Tokens	公式解説	グリッド上の2つの記号位置を探し、マンハッタン距離を計算する。	-378
ABC375 B Traveling Takahashi Problem	公式解説	点列を順に結んだユークリッド距離を累積する。	-325

挑戦問題

問題	公式解説	出題意図	difficulty
ABC269 B Rectangle Detection	公式解説	#セルの最小最大行列を走査し、矩形の境界を出力する。	-308
ABC348 B Farthest Point	公式解説	Official editorial intent is classified as farthest point.	-251
ABC246 B Get Closer	公式解説	ベクトル(A,B)をユークリッド長で割り、単位ベクトルの座標を出力する。	-250
ABC333 B Pentagon	公式解説	Compare the two possible chord lengths of a regular pentagon.	-202
ABC318 B Overlapping sheets	公式解説	Mark every unit square covered by at least one sheet and count marked cells.	-152