読者です 読者をやめる 読者になる 読者になる

SRM710

Programming SRM

難しすぎる. 0完で-100くらいくらって黄色になった.

easy:
AとBは逆操作.なのである標準形みたいなのを設定してそこに持っていけばいい.標準形としてはぜんぶおなじとこに集まってるのとかを選べば良くて、これに持っていくにはAを選びまくれば良い.

操作が二種類ある時は、それを組み合わせて一般的で簡単な操作を作れないか(石を1つ動かすとか), 実は実質一種類の操作に落とせないか(ex.f(x) = 4x+3, g(x) = 8x+7), 逆操作になってないか などを疑いましょう。


med:
こんなの実験しないと絶対に解けません。
考えると、magicを無視した状態で、「xorが0 もしくは全ての山が1」の盤面にしたら負け というのがbase stepとしてわかる.
あとは頑張って実験をすると、
その状態で次に動かすプレイヤーの敗北条件は,
{ \displaystyle
\begin{cases}
  \text{ if } \exists i , x_i>=4 & \bigoplus_{i=0}^{n-1}x_i=1 \\ 
  \text{ otherwise } & \bigoplus_{i=0}^{n-1}x_i=2
\end{cases}
}
であることがわかるので、これを計算して終わり。
証明:
ifの方を①,otherwiseの方を②とする.
勝ち状態で回ってきたときに①→①,②→②,①→② のどれかを使って負け状態を回せることと、
負け状態で回ってきたときに①→①,②→②,①→② のどれを使っても勝ち状態を回すことになることを示せば良い.
①→①はxorを0にすると負けなので1→2以上→1→2以上→・・・と遷移することからわかる
②→②は,
xor=1のとき, 全1でないことから2,3があり、しかも2以上は2個以上ある.なので3→0か2→1をしてよい
xor=3のとき,同様に2か3がある, 3があるときは3->2, ないときは2があり、かつ1もあるので1→0 でよい
xor=2のとき(負け), 1か3にしか遷移できないのはそう.
①→②は
勝つ側:4以上がひとつ→なしとなるので、事前状態はxor4以上.なのでこれを使ってxorを2にして渡せる.
負ける側:xor=1で回ってきているので4以上がひとつであることはありえない.

いや示せって言われたら示せるけどこんな場合分け実験せずに出来るわけないよね.

hard:
包除パートが見えるので、簡単やんけ!って思ったら前半の列挙パートが本質だった(座標の値が一致しても良いことに注意)
長さが正のintervalの端点の順序としてあり得るものは、A055203 - OEISで、N=6で既にデカいので全列挙は不可能.
なので左から頑張っておいていくDPをすごく頑張って書くと通る.
はじめどうせ求めるものは座標の値が一致しないものなんだからこの前提で包除すればええやん!って思ったけどそうではありませんね?
包除するときどういう形で求めているかちゃんと考えましょう