AOJ埋め4
2006年のセット.重い探索の問題が多く,全体的に難しい.結果見てもゆったり5問解きで5位とかそういうレベルっぽいし,あまり深くきにせずゆったり埋めていきたい.
1266 How I Wonder What You Are!
3次元幾何だけどベクトルの演算するだけ.
1267 How I Mathematician Wonder What You Are!
多角形の内角に対して見える範囲を凸カット絞っていって,最終的に候補領域が残っているかどうかで判定.
1268 Cubic Eight-Puzzle
探索.
普通にBFSでやったら結構遅かったので途中でA*に切り替えたが,それでもTLE.
困ったので,訪問済みかどうかのフラグをsetを保持するのをやめて,vector
探索の問題はどうも定数倍で重くなってしまうのが怖いなぁ.
1270 Manhattan Wiring
まだ解けてません.
最小費用流か!! と思って書いていたのですが普通に思い違いでした.
探索らしいです.
1271 Power Calculus
まだ解けてません.
一見TopCoderで出てもおかしくない雰囲気なので,N^2のDP? とか思ったのですが,調べてみたところどうやら探索するらしい.
探索といっても愚直にやると当然時間足りなくなるわけで上手い枝狩をしないといけないことになるのだけど,うーん,どうすんのこれ….