【AtCoder】PythonでABC187のB問題を解説

この記事では2021年1月2日に行われたAtCoder Beginner Contest 187のB問題について、Python3における解法をお伝えします。

なるべく分かりやすく解説できるよう心がけますが、競プロ初心者のため改善点・問題点がありましたらコメントまたはTwitterでご指摘ください。

Twitter：@soh_1121_

B：Gentle Pairs

問題文
xy 平面上に1, 2, …, N の番号が付けられたN 個の点があります。点i は( x_i, y_i )にあり、N 個の点のx 座標は互いに異なります。
以下の条件を満たす整数の組(i, j ) (i < j ) の個数を求めてください。
　・点i と点j を通る直線の傾きが -1 以上1 以下である。

制約
　・入力は全て整数
　・1 ≦ N ≦ 10³
　・|xi |, |yi | ≦ 10³
　・i ≠ j ならば x_i ≠ x_j

入力
入力は以下の形式で標準入力から与えられる。
N
x1 y1
︙
xN yN

出力
答えを出力せよ。

AtCoder Beginner Contest 187 B – Gentle Pairs

2点(a₁, b₁)、(a₂, b₂)のを通る傾きは (b₁ – b₂) / (a₁ – a₂ )で求められます。
自分を除く全ての点の組み合わせについて直線の傾きを調べ、-1以上1以下のものの個数を数えます。

def main():
    N = int(input())
    a = []
    for _ in range(N):
        a.append(list(map(int, input().split())))
    count = 0
    for i in range(N):
        for b in a[i + 1:]:
            grad = (b[1] - a[i][1]) / (b[0] - a[i][0])
            if -1 <= grad <= 1:
                count += 1
    print(count)


main()

標準入力のうち、まずN をintで受け取ります。
続いて各点をa というリストに標準入力をintに変換したリストで追加していきます。
答えとなる個数を0で初期化し、2点のうち1点をN 回ループすることで指定。
リストa に含まれる先に指定した点以降の点のうち1点をループで取り出し、2点の傾きを算出します。
傾きが-1以上1以下だった場合、個数の変数に1を追加していきます。

最後に結果の個数をprint()で出力してACとなります。

まとめ：総当りで可能かどうか見極めよう

この記事では2021年1月2日に行われたAtCoder Beginner Contest 187のB問題について、Python3における解法をお伝えしました。

与えられる点の数は最大10³個。2点の選び方は約10⁶通りなので、10⁹に満たず、総当たりでも十分実行可能です。

まだまだ判断は甘いですが、実行可能かどうかの見極めがしっかりできるよう精進していきたいです。