ABC402-D を Python で解いた

ABC402 D - Line Crossing
https://atcoder.jp/contests/aBc402/tasks/aBc402_d

公式解説の「実は……」は思いつけなかったのですが、自分なりに考えて本番中に正解することができました。思考の過程を書き連ねてみます。

コンテスト中の自分の動き

紙に円と線を書いてひたすら法則を考えていました。時間はかかりましたが解くことができて良かったです。

考察

2本の直線が交わるのは平行ではないときです。平行な場合にのみ交わりません。ですから、引かれた直線のうち平行になる組み合わせを数え上げ、全体の本数 ${}_MC_2 $ から引くのがいいと思いました。平行になる組み合わせの数は「平行になる直線の中から2本を選ぶ場合の数」と考えれば簡単に求められます。

どんな場合に直線が平行になるのかを考えます。$N=8$の場合について考えてみました。

図のように2つのタイプが考えられます。1つは直線が通る2点 (A, B) の中心にある点が来る場合です。ある点からみて A, B への距離が等しいものが組になります。図でいうと図でいうと点1を中心に (2, 8) (3, 7) (4, 6) の組が該当します。

もう1つは2点 (A, B) の中心に来るのが点ではなくある点とその隣の点の中間地点になる場合です。その中間地点からみて A, B への距離が等しいものが組になります。図でいうと点1・点2の中間地点を中心に (3, 8) (4, 7) (5, 6) が該当します。

タイプ1

ある点からの距離が等しいような2点を同じグループに分類していきます。例えば点3からの距離を考えたとき、(2, 4) (1, 5) などが該当します。ここで、2点の数字を足して2で割ったときに3となるものが該当することに気づきます。というわけでいろんな (A, B) の組について $ \frac{A+B}{2} $ を調べて、それぞれの組をグループ $ \frac{A+B}{2} $ に入れていくことを考えます。

• (2, 8) なら グループ5
• (3, 7) なら グループ5
• (4, 6) なら グループ5
• (1, 5) なら グループ3
• (2, 4) なら グループ3
• (4, 8) なら グループ6
• (1, 3) なら グループ2

という感じです。ここでグループ2とグループ6が同じものを指していることに気づきます（余談ですが、うかつにもこれを見落としていてペナルティを1回食らってしまいました）。というわけで $ \frac{A+B}{2} mod \frac{N}{2} $ をグループ名に使うことにします。

タイプ2

次は2点 (A, B) の中心に来るのがある点とその隣の点の中間地点になる場合を考えます。同じように足して2で割ってみると、

• (1, 2) なら グループ1.5
• (3, 8) なら グループ5.5
• (4, 7) なら グループ5.5
• (5, 6) なら グループ5.5

同じ考え方でいけそうですね。足して2で割ってから $ \frac{N}{2} $ で割った余りをグループ名にしましょう。

N が奇数のとき

さっきはN = 8 で考えました。偶数と奇数でいかにも結果が変わってきそうなので、今度は奇数で見てみます。N = 5 の場合を考えます。

• (1, 2) ならグループ1.5
• (1, 3) ならグループ2
• (1, 4) ならグループ2.5
• (1, 5) ならグループ3
• (2, 3) ならグループ2.5
• (2, 4) ならグループ3
• (2, 5) ならグループ2.5
• (3, 4) ならグループ3.5
• (3, 5) ならグループ4
• (4, 5) ならグループ4.5

今度も観察してみるとグループ2とグループ4.5 が同じであることに気づきます。差が $ \frac{N}{2} $ なら同じグループになります。それなら結局 N が偶数のときと同じように $ \frac{A+B}{2} mod \frac{N}{2} $ をグループ名に使えば大丈夫そうです。

なおコンテスト中はグループ番号が整数の時と小数のときで場合分けをし、整数だったら $ \frac{N}{2} $ を加えて、さらにその後で N で割った余りをとって……ということをしていました。明らかに回りくどいのですがコンテスト中はどうしても焦ってしまうので仕方ないところではあります。

数式をまとめる

以上見てきたように、Nが偶数でも奇数でも $ \frac{A+B}{2} mod \frac{N}{2} $ をグループ名に使えば大丈夫そうです。そしてこれは公式解説にあるように $ A+B mod N $ と同じことをいっています。これが「実は」の正体ですね。いきなりこんな発想は出てきませんでしたが、細かく考えていくことでなんとか答えにたどり着けました。

実装

これは本番で提出したコードです。場合分けが細かいですがACにはなります。

N, M = map(int, input().split())
# N 偶数のとき
if N % 2 == 0:
  groups = dict()
  for i in range(1, M+1):
    a, b = map(int, input().split())
    g = (a+b)/2
    g %= (N//2)
    if g not in groups:
      groups[g] = 1
    else:
      groups[g] += 1
  #print(groups)
  ans = M * (M-1) // 2
  for key, value in groups.items():
    ans -= value * (value - 1) // 2
  print(ans)

# N 奇数のとき
else:
  groups = dict()
  for i in range(1, M+1):
    a, b = map(int, input().split())
    if (a + b) % 2 == 0:
      g = (a+b)//2 + N / 2
      g %= N
    else:
      g = (a+b)/2
    if g not in groups:
      groups[g] = 1
    else:
      groups[g] += 1
  #print(groups)
  ans = M * (M-1) // 2
  for key, value in groups.items():
    ans -= value * (value - 1) // 2
  print(ans)