部活休んだので個人的に復習その２
リンク
部活の方
not-522.appspot.com
個人練
not-522.appspot.com
Pair Cards
二つ条件があるが、mod M で考えたときに0とM/2は同じ条件になるのでこの2つは除く
そうすると1とM-1、2とM-2、...みたいなのに分解される
分解後のペアの作り方を考える 最適解を持ってきます（いつもの）
両側にタイプ1があればタイプ2にできる
片側にタイプ1があって、逆側が余っているならそれもタイプ2にできる
したがってとりあえずタイプ2を作れるだけ作って残りでまだ作れるならタイプ1を作ればよい
へんなコンパス / Manhattan Compass
初手思考停止マンハッタン距離は回す！（素振り）
ペアをそのまま状態には持てない よく考えると、端点になりうるかだけわかればよい
答えは端点になりうる点全てに対し、その点とペアになれる点の数の総和（わる２）
これは長方形領域2つの差で表現できる
端点になりうるかどうかはBFSで探す
setに座標を突っ込んでおいて削除しながら適当にやると、ならしでO(N polylog N)になる（はず）
シャッフル / Shuffling
lが非現象なので、左から決めていく気分になる
各位置について、シャッフルでそこにもってこれる範囲というのは適当に前計算できる
ある位置まで見たときに必要な情報は左に0,1がそれぞれ何個あるか
これは片方覚えておけばもう片方は位置から引けば求められる
したがって、O(N^2)のDPができる
感想
変なコンパス、記憶よりは重くなかった RangeTreeサイコー！
