Half Reflector解くの4回目とかですが…
Robot Racing
状況を固定したとき、最初にゴールすることのできるロボットというのは位置に対して単調性がある
最初にゴールすることができるロボットの中で一番右側のロボットをAとする
AとAより左側にあるロボットのことをL側、Aより右側にあるロボットのことをR側と呼ぶことにする
L側にあるロボットは、仮定からどのロボットをゴールさせることもできる
R側にあるロボットはL側にあるロボットが一つ以上ゴールするまでゴールできない
したがって、L側のロボットを一つゴールさせ、新たなAを求め、ゴールさせ、ということを繰り返すことで答えが求まる
Aの求めかたを考える 左から順番にロボットを見ていく
もし今見ているロボットの前のロボットとの間が二つ以上空いていれば詰めてしまってよい
そうすると結局 GOX..OXOOのようになる（Gがゴール、Oがロボット、Xが空きマス）
このとき初めて現れるOOの右側がAになるのは明らかである
（右側をBとして、Bは最初にゴール可能、Bより右側は最初にゴール不可能）
L側のどのロボットをゴールさせたとしても、適切な操作でGOX..OXOXの形に変形できる
これを最後のロボットまで続ければよい
Squared Graph
サンプル2を手でお絵描きする 孤立点は適当に求まるので除いておく
連結成分ごとに並び替えると、奇数長の閉路があるかどうかが重要なことがわかる
二部グラフ判定は頂点倍加したUnionFindをつかえばよい
Half Reflector
先頭がAのときははい
先頭がBのときは実験して眺めると
先頭を外す
全体をflip
末尾にAを追加
なのでこれをdequeでシミュレーションする
K < 10^9 なので愚直にやると間に合わないが実験の結果を眺めると
偶数長のとき BA...BA の形に収束して
奇数長のとき ABA..BA と BBA..BAで振動する
したがってN << K のときはmod 2で一致していればよく、適当なところで打ち切ればよい
感想
覚えてたら1問10分とかで終わるし6問くらいに増やしてもいいかもなあ
