ごりちゃんがゆく

競プロをするゴリラの精進記録

ARC173-B Make Many Triangles の解法の思いつき方

ARC Python スニペット

コンテスト中解けるべきだったのに解けなかったので自戒を込めて記事にします

atcoder.jp

問題概要

二次元平面上に相異なるN個の点があるので、各点を1回まで使って、三角形をできるだけ多く作ってください。何個作れますか？
N \le 300 ぐらいです

こう考えればよい！

まず、すべてが一直線上にある場合、三角形は作れないので、答えは0です

つぎに、ほとんどが一直線上にあるけど1個だけその直線上にない場合、1個だけ作れます

2個の場合は2個作れます

3個の場合は3個作れます

こうしていって、 何個まで作れるんだっけ？と考えていくことにしたいが、もともとどんなケースでも \lfloor \frac{N}{3} \rfloor 個より多く作ることはできません (上界)

実は、通る点が一番多い直線を考えて、その直線を通らない点の個数をxとすると、答えは \min(x, \lfloor \frac{N}{3} \rfloor ) です！
これだけ！！！！！
最悪ケース (一番なにも作れないケース) から順に考えていくと、自然に解くことができました！！

ちなみに、「通る点が一番多い直線」だけを考える、で本当に良いの？2番目や3番目を意識しなくていいの？
と思うかもしれません　(自分も、それが頭をよぎって、こんな単純な方針が見えなかった)

(点がランダムに散らばってる場合など) たいていの場合答えは \lfloor \frac{N}{3} \rfloor になるので、答えが \lfloor \frac{N}{3} \rfloorにならなくなるギリギリを考えてみます
N=10のとき、 \lfloor \frac{N}{3} \rfloor = 3 です
つまり、通常3個作ることができます
このとき、7個までは一直線上にあって大丈夫です

8個めが一直線上にある場合にはじめて、答えが減少します

答えに影響するのは、 N - \lfloor \frac{N}{3} \rfloor より多い点が一直線上にあるときに限るとわかります
N - \lfloor \frac{N}{3} \rfloor より多い点が一直線上にあるとき、別の直線上に N - \lfloor \frac{N}{3} \rfloor より多い点があることはどう頑張ってもありませんよね。

これが2番目3番目...に通る点が多い直線を考えなくて良い理由です！

教訓

最悪ケースを考えるべし！！！！

ACコード (コンテスト後)

lines[(i,j)] に、点iと点jを通る直線に何個の点が含まれますか？を管理しています
is_line() は3点が同一直線上にあるかの判定 (傾きの比較を変形して割り算を回避してます) このスニペット持ってると役立ちそう

N = int(input())
XY = [tuple(map(int,input().split())) for _ in range(N)]

def is_line(x1,y1,x2,y2,x3,y3):
    return (x2-x1)*(y3-y1) == (y2-y1)*(x3-x1)

lines = {(0,1): 2}
for k in range(2,N):
    xk,yk = XY[k]
    add = []
    for (i,j) in lines.keys():
        xi,yi = XY[i]
        xj,yj = XY[j]
        if is_line(xi,yi,xj,yj,xk,yk):
            lines[(i,j)] += 1
        else:
            add.append((i,k))
            add.append((j,k))
    for i,j in add:
        lines[(i,j)] = 2

line_max = max(lines.values())
other = N - line_max
ans = min(N//3, other)
print(ans)