AOJ埋め3
不運にも寝入ってから4時間くらいで目が覚めてしまったのでAOJを埋めることに.
1275 And Then There Was One
入力値が小さいので愚直にやればよい.高速で解きたい問題.
1276 Prime Gap
やるだけ.
1277 Minimal Backgammon
確率のDP.場合分けに気を付ける.
1280 Slim Span
コストが最小となる辺を固定して,その辺より大きいコストの辺を小さい順にUnionFindでくっつけていって試せばよい.
最悪の場合M^2くらいかかるので,N<=100だとM^2ではまずい? と思ったけど,定数項が利いてるのか2乗でも普通に間に合う.
1281 The Morning after Halloween
状態数が256^3程度しかない(壁の配置の条件が結構きついので実際には多分100^3〜150^3程度しか無い)ので普通に幅優先すれば良い…
かと思いきやAOJのタイムリミットがきつくてそれだと間に合わない!! うざい!!
目的地から現在地までの距離の最大値をヒューリスティック関数にしてA*探索をするようにしたがそれでもまだTLE.
探索状況を色々調べてみると,キューに同じ状態がいくつも突っ込まれていたようだったので,状態αへ到達するまでの最小距離をmap<α,int>に保持させ,既にキューにある同じ状態を突っ込む場合は最小距離より小さくないと突っ込めないように変えたが,それでもTLE.
もうしょうがないのでmap<α,int>をunsigned char [256*256*256]とかに変えたらACになった.
なかなか厳しい.
1282 Bug Hunt
構文解析.
今までに宣言された配列のサイズ map
1283 Most Distant Point from the Sea
2分探索+凸カットするだけ.
関数が2変数の凸関数なので,分割統治とか2分探索とかでも出来るかもしれない.