APIO 2010
APIO（アジア太平洋情報オリンピック）を受けてきました。
問題概要は公式サイトにあるので省略。
難易度的には、「ぱない」としか形容のしようがありません。
1. Commando
50点まではO(n^2)のDPで取れる（取れた）。そこから先がわからない。
2. Patrol
非常に面倒。
まず、近道が集落A,Bを結んでいるとき、A,B間での移動距離が、経路の辺1本につき1ずつ短くなる。但し、近道を通る必要があるので距離の減少は1少なくなる。近道2つだと、2つの近道の木の上での経路が交わらなければ同様。交わる場合は交わらない場合に帰着できるので考えない。
K=2のときは、木の上で2つの辺を共有しない別々の経路で、経路の長さの和が最大になるものを考えればよい。
そのようなケースには、
- 2つの経路ともにある頂点を通る場合
- 木からある辺を取り除くと2つの経路が別の木に入る場合
がある。
どちらもDPを使えば求められる。但し、非常に面倒。
隣接リストにvectorを使ったコードを書いた（悪い癖）。手元でN=100000のケースを試してTLEして非常に怖かった。
3. Signaling
幾何。
O(n^4)はやるだけ。でも定数項が大きいので怖い。
O(n^3logn)は思いついたけど、実装が非常に面倒だったのでO(n^4)にしておいた。
n<=1500でTLが2秒だから、O(n^2logn)が限界だと思うけどどうしようもない。
結果
1番50点、2番100点、3番40点。
1、3の部分点は入力の制約的な意味で妥当。
2番で100点取れたのは運が良かった。
感想
1と3で100点を取っている人がいる。こわい。
でも全問満点の人はいないのか。2年前は金のボーダーが満点で、さらに金が銀と銅を合わせたよりいるという大変なことになってたけど。
8月のIOIが少し心配になってきた。
