AtCoder Beginner Contest 402 D - Line Crossing
問題文は👆を確認してください
導入
atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。
使用しているアルゴリズム
- 数学的アルゴリズム
解法のポイント
ここでは、まず全ての直線ペアが交わると仮定して得られる最大交点数を M*(M-1)//2 で計算します。
次に、平行な直線同士は交わらないため、同じグループに属する直線数 i 本に対して生じる交わらないペア数 i*(i-1)//2 を差し引きます。
平行グループのキーとして (a + b) % N を使うと、「同じ余りに属する直線」がすべて平行になることが数学的に示せるので、これを defaultdict(int) でカウントします。
最終的に、全組合せからグループごとの組合せを引いた値が答えになります。
ACサンプル
from collections import defaultdict
N, M = map(int, input().split())
G = defaultdict(int)
for _ in range(M):
a, b = map(int, input().split())
cat = (a + b) % N
G[cat] += 1
# 総交点数
r = M * (M - 1) // 2
# 平行な直線同士の交点数を差し引く
for i in G.values():
if i >= 2:
r -= i * (i - 1) // 2
print(r)