問題概要

N個の点が与えられます。これらを全てちょうど1回ずつ使って三角形をN/3個作るとき、面積をなるべく大きくしてください。10⁷回の乱択以上のスコアが出たらACです。

部分点 - 20点

N = 9です。全部で280通りなので乱択でもとても高い確率で最適解が出ると思います。提出を乱択にしても通ると思います。後述する40点の方針がそのまま乗るので、そちらにまとめるのが楽です。

N = 18です。全部で190590400通りです。10⁷回の乱択では95%の確率で上位57個、99%の確率で上位88個が選ばれると期待されます。かなり最適に近いものを構成しないといけないことがわかりますが、こういうときにbitDPが便利です。

状態をbit(0/1の2状態)の連なりとして表すDPです。今回は、「n番目の点が使われている」ことをn番目のbitが1であることとして考えるといい感じに解くことができます。

bitDPを使うと、全状態は2¹⁸=262144通りで、1回の遷移にたかだか18C3=816通りしかかからないので、なんとか間に合いそうです。(全体で2.1×10⁸回信じることが大事です Pythonでは通らないかも)

一気に飛んで満点です。N=300, 3000です。それぞれ5.02×10³⁷⁸通り、7.28×10⁵⁷⁸⁴通りです。べらぼうな数がありますが、冷静になるとその多くは無駄になっている三角形がありそうなことがわかります。(300個も点があったらごく近い3点が選ばれてしまいがちなので)

なので、そこまで悪くない(全部の三角形がそれなりの大きさを持っている)構成をしたら勝てそうな感じがします。実際、点の存在領域をT字型に分割して三角形を端から構成していくと通ります。(この構成では最小の三角形の大きさもそれなりになります)

これで通りますが、果たして想定解はどんな方針なのでしょうか気になります...