AOJ埋め8
某イベント1日目だったらしいですね．クーラー掛けながらリビングで2002年のセット+α埋めていました．
1232 Calling Extraterrestrial Intelligence Again
答えはp*q<=100000を満たすものに限るので，あらかじめ2つの素数の積に分解される数を全部列挙しておいて条件を満たすものを大きいほうから見ていけばいい．
1235 Life Line
dfsするだけだけど実装がちょっと面倒．
1236 Map of Ninja House
グラフを実際に構築しながらやっていくといい．
辺を付け加えるたびに次数を減らし，もし現在見ているノードの残り次数が0になったら1つ前のノードに戻る，ということをやっていく．
スタックを使ってごにょごにょとか考えたけど，それだとグラフが入り組んでる場合がちょっと怖かったので控えた．
1237 Shredding Company
6桁しかないので，全部試して 存在するか | 最大のものが一意的か を見てやればいい．
1238 True Liars
実装が厄介な問題．
x y yes
が来た場合はxとyは同じ族で，
x y no
が来た場合はxとyは違う族であることが分かる．
そこで，まず x y yes のクエリに対してx,yを同じ集合に属するものとしてマージしてやる．これはUnionFindを使って union_set してやればよい．
次に，noのものに対して，上で作った集合でグラフを作る．具体的には， x y no に対し， root(x) と root(y) の間に辺を張る．（root(z)はzの属する集合の代表元）
さらに，このグラフに対して2彩色を行う．これは適当にdfsしてやればいい．もしここで2彩色ができないのなら，クエリに矛盾があるということであるので，"no"を出力して終了する．(この時点で下図みたいになっている)
で，ここからが面倒臭い…
2彩色してグラフの頂点が黒|白に分かれたとしよう．すると，各連結成分については 白=devine,黒=devil | 白=devil,黒=devine のどちらか2通りしかないことが分かっている．
しかし，各連結成分についてまだ2通りずつの自由度があるので，このままではどれがdevineなのかが一意に決定されない．
ここで決定するにあたって，devineは全体でp1人いるという制約を使う．
適当にDPっぽくやった(dp[今何番目の連結成分を見ているか][和を幾らにしたいか] で 存在しない or 一意的に存在 or 複数通り存在 のどれかの値をとる，みたいな)んだけど結構実装が入り組んでとても時間がかかったし，もっといい方法があるような気がせんでもない．
で，ここからアジア地区ではなく去年の夏合宿の問題．当時のまとめみたいなのはこのへんにも．
2158 Double Sorting
oxyさんがお作りになられた問題．難解な探索で，合宿でのコンテスト中に解いた人はいなかった．
前日にぼけーっとこの問題の解説スライドを読んでいたのでその通りに実装した．
最初微妙にheuristic関数の実装をゆるくしていたのでMLEとか喰らって焦ったけどそこを修正したら速度が一気に上がってAC．
具体的には，heuristic(2)で，転倒数を数える際に2組の数字が同じだったときをカウントしていなかった．
なんで一気に挙動が変わるのかあまり分からなかったけどそういうもんなのかなぁと思って放置．
解説どおりに実装するだけならあまり難しくないので暇な人はやってみるといいんじゃないでしょうか．解説どおりに実装するだけなら．
2163 Tatami
昔書いた記事にもあるけど制約が超強いので普通に探索して間に合っちゃう．
上からおいていけばよい．置く際，↓みたいにタタミの位置によって書き込む数字を変えると角かどうかの判定が楽にできる．
2164 Revenge of the Round Table
昔書いた記事にもあるけど，段階を踏んだDP．
dp1a[n] := Aからスタート | k個より多く連続して並ばない | 縦にn個並べる (円の繋ぎの部分は気にしない) | 最後Aで終わる
dp1b[n] := Aからスタート | k個より多く連続して並ばない | 縦にn個並べる (円の繋ぎの部分は気にしない) | 最後Bで終わる
dp2[n] := Aからスタート | k個より多く連続して並ばない | 円状ににn個並べる (円の繋ぎの部分を気にする)
dp3[n] := Aからスタート | k個より多く連続して並ばない | 原始的な解(nより小さい個数の順列の繰り返しで表せない)である
とすると解は
Σ_{ d|N, 1
で求まる．
