AtCoder diverta 2019 Programming Contest 2 B - Picking Up (Python)

irisruneです。今週もコンテストは出ていませんでした、コンテスト開催日時に合わせて色々調整することも考えないといけませんね。

C問題よりも難しいと感じる人もいたそうです。確かに問題文だけ見るとC問題の方が単純そうには見えました（まだC問題は解いていませんが）。

import sys
import numpy as np


def main():
    n = int(input())
    balls = [[int(e) for e in input().split()] for _ in range(n)]
    if n == 1:
        print(n)
        sys.exit()
    diff = {}
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if ((balls[i][0] - balls[j][0]), (balls[i][1] - balls[j][1])) in diff:
                diff[((balls[i][0] - balls[j][0]), (balls[i][1] - balls[j][1]))] += 1
            else:
                diff[((balls[i][0] - balls[j][0]), (balls[i][1] - balls[j][1]))] = 1
    print(n - max(diff.values()))


main()

割と小難しそうな問題ですが、結論から言えば $(x_i-x_j,y_i-y_j)(i\neq j)$ をすべての $i,j$ の順列について計算し、最も出現回数の多いペアについてその回数を $N$ から引いた数が答えになります。

このように解ける理由としては、問題の条件にある『 $x_i\neq x_j$ または $y_i\neq y_j(i\neq j)$ 』がポイントとなっています。

この条件により、 $i,j,k$ 番目のボールについて（ $i,j,k$ は互いに相異なる）、 $(x_i-x_j,y_i-y_j)=(x_i-x_k,y_i-y_k)$ となることはありません。よって $p,q$ を適当に選んだとして、 $i$ 番目のボールの次に $j,k$ 番目のどちらかのボールを選んだとき、両方のボールについて回収するためのコストが $0$ になるということはありません（少なくとも片方のボールを回収するためにコスト $1$ が必要）。

これにより、任意の $x,y$ 座標の差のペアについて、その出現回数はそれぞれの値を $p,q$ として置いたときにコスト $0$ で回収できるボールの数となります。そのため、 $x,y$ 座標の差のペアそれぞれについて出現回数の最大値を求めればよいということになります。

実装については辞書型を使えばそれほど難しくないはずです。辞書型の要素数の最大値を出す処理の計算量が分からないですがそれ以外の処理の計算量は $O(N^2)$ になります。

雑記

コーナーケースとして $N=1$ の場合、当然ながら座標の差というものはないので（辞書型の）要素数の最大値を求めようとするとREになります。
と条件が非常に緩いので、他の解き方でもなんとかなりそうな気はしますがよい方法が思いつかないです。
- 当初はなんとなくワーシャルフロイド法を使うことなど考えていましたが、を定めないとコストの合計が出せない上に、と座標の取り得る値が非常に広いため、を全通り試すことが不可能でした。
  - $x,y$ 座標の差のペアとして出現する値に絞れば $O(N^5)$ くらいで解けるかもしれませんが、ペアの出現回数から直接答えを求める方法でよいという結論になってしまうので…