12/15-16
12月15日
16. PKU 1217
DP。
dp[r][a][b]を、「rラウンド後にAの得点がa、Bの得点がbである確率」としてやる。
17. PKU 1226
全探索。
12月16日
18. PKU 2914
無向グラフの全域最小カット。
19. PKU 2920
やるだけ。
20. PKU 2922
経路中最も低い部分の高さを決めつけて、最も高い部分の高さでダイクストラ。これを200回繰り返す。
21. PKU 2926
5次元の点が複数与えられるので、その最遠点対の距離を求める問題になる。ただし距離はマンハッタン距離。
簡単のため2次元の場合を考えると、 (x1, y1), (x2, y2)の距離は max{(x1+y1)-(x2+y2), (x1-y1)+(x2-y2), (-x1+y1)-(-x2+y2), (-x1-y1)-(-x2-y2)} で表される。
すると、任意のn点の中の最遠点対の距離は max{(x+yが最大になる点) - (x+yが最小になる点), (x-yが最大になる点) - (x-yが最小になる点) ...以下略} で求められる。x+yが最大になる点とかは普通にO(N)で求められるので、最遠点対の距離はO(N)で出せる。
これを高次元に拡張しても同じで、k次元の点集合の最遠点対の距離はO(N * 2^k)で出せる。