アジア地区予選の復習

一度解法聞いてるのに，まだ解けてない問題がある…．

問題とサンプル入出力は公式サイトで公開されてます．

以下ネタバレのため省略されました．続きを読むには(ry

おおよそ復習に手を付けた順に．

slimな全域木は，解説の通り．全域木を構成する辺のうち最軽辺をループ毎に重くして，全域木を作れなくなるまで繰り返す．

バックギャモンの問題は，メモ探のテーブルをゼロ初期化してたために確率ゼロと見分けがつかずTLE状態だった．安易にmemsetしたのが間違いのもと…．なんで気付かないかなー． -1で初期化して普通の速さに．

構文解析してバグを見つけるという問題は，10分パーザのおかげで書けた．Syntax errorは無いということで気が楽．配列名→サイズのmap，(配列名とインデックス)→値のmapが大域にあれば良い．

海から最も遠い点の問題は，ライブラリの重要さが身にしみた．人のライブラリを使うなら，最低でも使い方を把握しろ>自分． 使った解法は，凸多角形を縮小する（クリッピングというのか）長さについて二分探索．

幽霊の問題．両側探索するのにpriority_queueを使っていたせいで無駄に悩んだ．queueに直してあっさり終了．問題文のサンプルで3秒弱，公開されたサンプル入出力で23秒程度だった．さすが両側探索．

折り紙の体積（違）を求める問題は，とりあえず展開図の頂点を列挙するとこまで書いた（ここまで書いて思い出したけど，頂点を一つ決めた後，残りの頂点が格子上に乗ってるかチェックしていない気がする）．これで展開図がかけるので，あとは展開図から高さを求めれば良いんだけど…．

最短路の問題と最後の問題はまだ手付かず．最短路のは，グラフに落とすのが面倒そう．