3本溜まっててヤバ
A or...or B Problem
まずAとBのcommon prefixを消す（2敗）
A == B なら答えは1
Bで立っていてAで立っていないbitの中で一番上のbitに注目する
それをMbit目として [A, 2^M ) と [2^M, B) のグループに分割する
x ≤ x or y であることに注意すると、[A, 2^M ) から作れる集合は [A, 2^M ) 自身になる
[2^M, B) から作れる集合は、BのMより下のbitの中で一番高いbitをSとすると、
[2^M, 2^M + 2^S ) みたいになる なぜなら10..01, 10..10, みたいなのが[2^M, B) にあるため
グループを跨ぐ組み合わせを考える
x ≤ x or y であることに注意すると、[(2^M) | A, 2^(M+1) ) 以外は作れず、またこれは全て作れる
したがって高々三つの区間のunionが求められればよく、これはできる
Mirrored
桁数を決め打って上下から中心に向かって決めていく
このときそのあとどう選んでも0にならない状態になったらすぐDFSを打ち切ることにする
10^k > sum_{a < k) 9 * 10^a であるから、打ち切られないのは高々2通り
同様の考察で決めうつ桁数の上界がlog_10 D * 2 程度であることもわかる
したがって 2 * log_10 D * 2^log_10 D 程度でこの問題が解けた
+/- Rectangle
まず-1の場合を考える
HがhでわりきれてWがwで割り切れたらだめ
そうでないなら全部できそう 実際に構築してみる
まず対称性から (i %h ,j % w) = (h - 1, w - 1) に負の数をおくべきだとわかる
そうでないマスに0, 1, 500, 501, 10^9 を書いたときの挙動を観察すると、負のマスが-10^9未満にならないうちはなるべく大きくした方がいいことがわかる
制約から、501を書いておけば必ずできることがわかる
感想
この辺は本番解けるか解けないかラインにいたので解き直してるとエモくなっちゃうな
