今日解いた競プロの問題。

ABC250-F: 適当な頂点を1つとって、その頂点から各頂点に線を伸ばすとN-2個の三角形に分割できる。二次元平面上の三角形の面積はたすき掛けの式で求めることができる。これを使えば全体の面積を求めることができるし、また任意の頂点ペアの間に線を引いて切り取った図形(任意の切り方におけるピース)の面積も求めることができる。

適当な頂点Aを選び、端から順に三角形を足していって全体の面積の1/4以上になったら打ち止め、ということをやる。最後の三角形を足す前後をそれぞれ見れば、頂点Aを「軸」にしたときの最適な切り方が求まる。これを任意の頂点についてやればいいのだが、これでは$O(N^2)$になってしまうので、尺取り法をやる。軸となる頂点A、最後に採用した頂点、そして頂点Aの1つ隣の頂点の成す三角形の面積を引く。この状態から同じ操作をやることで、頂点Aの1つ隣の頂点を軸としたときの最適な切り方を素早く求められる。どの頂点も1回ずつ軸となりまた1回ずつ採用されることになるので$O(N)$になる。パイの周りをぐるっと順に回るイメージ。

---

ICPCの国内予選に参加した。Bの考察・実装とCの実装を担当。Bは制約が小さいので愚直にシミュレーションを回すだけだったのだが、上がったプレイヤーを考慮したターン遷移が地味に面倒だった。

結果はまあ見えていたが予選落ち。しかしもうちょっと解きたかったなー。