ICPC2011 World Finals

ICPC2011 World Finals問題をざっと読んで解法予想。
仕事山積みなので、各問題の制限時間は３分で考えてみた。

  • 問題A 最短かつ lexicographically first を求めるのでおそらく iterative deepening。
  • 問題B ３点の対応関係を 2 通り固定してごり押し。
  • 問題C 連結成分毎に穴の数を数えて終わり。
  • 問題D 左上から縦横縦横の順に埋めながらDFS。
  • 問題E マップを45度回転し、良くあるO(n^2)プリプロセスの長方形sumクエリー。
  • 問題F 時間軸でソートして DP っぽく。
  • 問題G うおお。わかんない。円に近づければ良いので短い順に真ん中から左右交互に並べて輪を閉じる。繋げる角度が分からない。
  • 問題H グラフの関節点を求めて終了。
  • 問題I 思いつかない。A*でやりたいけどどう見てもこのサイズだと計算終わらない。距離が縮まらないから逃げる方向別に各ゾンビからの余裕距離を求めてごにょごにょしたらできそうだけどわかんないな。
  • 問題J 素直にDPで下から組み上げれば求まる。
  • 問題K 全通り回転させて終了。

もちろんこれで合っているかどうかは知りません。