kwm_t

kwm_tのメモ

ABC199.5

■A - UFO襲来
全て探す

■B - 友好の印
UFOをビルを結んだ傾きが一番緩やかなものが答え。
地中からは見えないことに注意

■C - MAD TEAM
二分探索

■D - 宇宙人からのメッセージ
反転はフラグで管理する
dequeで管理しつつ、最後にやる処理は途中にやっても問題ないので
途中にする。

■E - 潜入
愚直でも通るらしい。(は?)
それぞれの頂点にサブ頂点を用意しておき
下がるときは、サブ頂点にコスト1で移動してから
下マスのサブ頂点にコスト1で移動する。
サブ頂点から、メイン頂点にはコスト0で戻れるようにする。

■F - 出会いと別れ
線形代数
頂点0から頂点xに移動できるかどうかは
0 xor bi xor bj xor bk.... = xとできればいい。
任意のxをb0,b1.....の部分集合のxorで作成するためには
bのrankがnになれば良い。
構築はここまでの処理で基底として採用するbを使って
非連結なら結んでいけば良い。
n*2^nをすべて試してもたかが知れているので問題なし。