今日の分

PKU Algorithm

これは嘘で実際は解いていません、みたいなことはないので安心してね！

  1. PKU 2470 Ambiguous permutations
  2. PKU 2031 Building a Space Station
  3. PKU 2524 Ubiquitous Religions
  4. PKU 2251 Dungeon Master

累計26問。

PKU 2470 Ambiguous permutations

やるだけ。アホなやり方でO(N2)とか書くと死ぬ。

PKU 2031 Building a Space Station

セルを頂点とし、セルの各組の距離を重みにもつ辺を持たせたグラフを考える。2セル (x0,y0,z0),(x1,y1,z1) 半径それぞれ r0, r1 間の距離は max(sqrt( (x0-x1)2+(y0-y1)2+(z0-z1)2)) - (r0+r1), 0.0) で計算する。

後は頂点がすべて連結になり、かつ重みの和が最小になるような辺の残し方を求める。これは最小全域木を求める問題であり、クラスカル法を用いればグラフ G=(V,E) に対して O(|E|log|E|) で答えがでる。|V| = Nであり、|E| = |V|2 = N2になるので計算量をNで表せば O(N2logN) である。

PKU 2524 Ubiquitous Religions

Union Findで集合が何個あるか数える。M回のUnionを必要とするので時間はO(NM) = O(N^3)で間に合わないように見えるが、経路圧縮したUnion Findのならし解析による時間で考えると5000MSの時間制限には余裕で間に合う。

PKU 2251 Dungeon Master

よくある迷路の経路探索問題が3次元化しただけ。BFSでおｋ。