12/15-16

PKU

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)で出せる。