IOI 2018 Day2 - Highway Tolls
概要
Author : KoD
解法
全ての辺の重みを$ Aとしたグラフを G とおき、G における S,T 間の最短距離を$ Dとおく。
G における S,T 間の最短経路（の一つ）に含まれる頂点を一つ見つける。これは、頂点 $ 0, 1, \dots, k-1に接続する辺のみ重みを$ Bにしても最短距離が$ Dのままであるような$ kのうち最大のものを二分探索で求めればよい。この点を P とおく。
G における P からの距離の昇順に頂点を並べ替え、$ u_0, \dots, u_{N-1}とおく。
頂点$ u_{k+1}, u_{k+2}, \dots, u_{N-1}に接続する辺のみ重みを$ Bにしても最短距離が$ Dのままであるような$ kのうち最小のものを二分探索で求めると、$ u_kは S,T のいずれかに一致する。
この点からの距離の昇順に再度並べ替え、同様の二分探索を行うと、S,T のうちまだ見つかっていない方を求めることができる。
以上の解法をそのまま実装するとクエリは$ 3 \lceil \log_2N \rceil + 1回となり、$ N = 90000のとき$ 52回なので$ 90点が得られる。
満点を取るにはクエリをあと$ 2回減らす必要がある。そこで$ N < 1.5 \times 2^{16}であることに注目する。
P を求める段階で求めた$ kに対し、頂点$ 0, 1, \dots, k-1に接続する辺は必ず重み$ Bであるとしてもよく、また S, T の候補となる$ u_0, \dots, u_{N-1}にこれらの頂点を含める必要はない。
よって、二分探索の最初の段階で$ k = \left\lfloor\frac{N}{2}\right\rfloorではなく$ k = \left\lfloor\frac{N}{3}\right\rfloorを用いると次のようになる。
求める$ kの最大値が $ \frac{N}{3}以上のとき、この段階では$ 17回のクエリが必要だが、S,T を求める段階では高々$ \frac{2N}{3}頂点程度しか考えなくてよいため、それぞれ$ 16回のクエリで済む。
求める$ kの最大値が$ \frac{N}{3}未満のときは、この段階のクエリは$ 16回で済む。
S,T を求める段階でも同様の改善を行うことで、$ 17回のクエリが必要となるのが高々一度だけになるので、クエリを$ 1 + 17 + 16 + 16 = 50回で抑えられ満点を獲得することができる。
感想
木の場合にこだわりすぎたり、二辺連結成分分解などを考え出したりすると沼にハマる。
BFS木の気持ちになると思いつきやすいはず。
$ A,Bの値を一切使わなくてよかったのが意外。