文学徒が競プロをするブログ

競技プログラミングの精進を記録していきます

ABC172 Unfair Nim

これも以前写経して通したけどわからなかったやつ。今度こそ理解するぞ。

問題概要

Nimをする。一つ目の山から二つ目の山に0個以上の石を移し替えることで、後手必勝にできるか判定せよ。
また、必勝にできる場合は移し替える最小の石の個数を求めよ

という問題。

解法

Nimの説明は省略します。Nimで後手必勝 = 全部の石の数のXORが0 という有名事実があるので、「一つ目の山から二つ目の山に0個以上の石を移し替えることで、全ての数のXORを0にできるか判定せよ」という問題になります。

以下、各山の石の数を $A$ と置きます。一つ目の山は $A_0$ , 二つ目の山は $A_1$ です。

$A_0$ と $A_1$ 以外の値は不変なので、三番目の山からN番目の山までの排他的論理和も不変であることは明らかです。この不変な排他的論理和を $X$ と置きます。

すると全ての数のXORを0にするには、 $A_0$ と $A_1$ のXORが $X$ にする必要があります。

よって、 $(A_0 - T) \oplus (A_1 + T) = X$ となるような最小の $T (0 \leq T \lt A_0)$ を求める問題に言い換えることが出来ます。

まあここまではNimさえ知っていればすんなり来れますね。問題はここからです。

$T$ をナイーブに全探索して試していけば当然解くことが出来ますが、制約が $A_i \leq {10}^{12}$ なので、まあ2sec以内に解くことは不可能です。

仕方がないので別の方法を考えます。まず、XORなので2進法に変換して桁ごとに見ていくのが典型です。正直こんなの貪欲か桁DPのどっちかしかないんだよねのお気持ちになります。

僕の実力では貪欲の正当性を自力で示すことは難しいので、まずは桁DPを考えます。そのうち貪欲を理解したらそれも書くかも。

色々試行錯誤した結果、繰り上がりが発生して面倒なことがわかるので、下の桁から値を決めていく方針で行きます。

$S = A_0+A_1$ として、 $P = A_0 - T$ , $Q = A_1 + T$ とします。
すると求めたい値は

$P + Q = S$

$P \oplus Q = X$

$1 \leq P \leq A_0$

という条件を満たす最大の $P$ となります。

$dp(i) :=$ $P \oplus Q$ の下からi桁目までと $X$ の下からi桁目までが一致するような $P$ の最大値

と定義します。最初 $T$ をそのまま決めようと思ったら繰り下がりなんかも出てきて嫌になったのでやめました。

自力だとここから先に行けずに躓いてしまったのですが、原因は以下です。

$P$ と $Q$ の二つについて決めていく考え方を持てなかった
下から決めていくとき、未満フラグ(以下フラグ？)をどう管理して遷移していけばいいのかわからなかった

2はほぼ知識で何とか出来るところですし、2さえ分かっていればの試行錯誤もスムーズにいくはずなので、覚えちゃいたいですね。

というわけですぬけさんの解説動画を見ました。

$dp_{ijk} :=$ $P$ と $Q$ をそれぞれ $i$ 桁目まで決めていて、繰り上がりの有無、 $A_0$ 以下か否かをそれぞれ $j$ と $k$ のフラグで持ったときの $P$ の最大値

を考えます。

まず $i$ 桁目の $P$ と $Q$ の値は $[(0, 0), (1, 0), (0, 1), (1, 1)$ ]の四つ考えられるので、四通り全部試します。

そのうえで、その桁まで見たときの $P$ と $Q$ の排他的論理和が $X$ と等しいか、和が $S$ と等しいかをチェックして、両者とも等しいときのみ遷移します。

これはややこしく思えますが、排他的論理和は各桁ごとに完全に独立、和も繰り上がりしているかどうかさえ事前に分かっていれば各桁ごとに独立です。
だから繰り上がりの有無を状態として持っている必要があるんですね。

さて、そこまでの値が $A_0$ 以下か否かを持つフラグの遷移は少し考える必要があります。

各桁ごとに見たときに、その桁の値が $A_0$ のそれよりも「大きいか/小さいか/同じか」の三通りで場合分けを考えます。

大きい時

それまでがどんな状態だろうが、「 $A_0$ 以下ではない」フラグの方に遷移します

小さい時

それまでがどんな状態だろうが、「 $A_0$ 以下」フラグの方に遷移します

同じとき

それまでの状態と同じフラグの方に遷移します

これで遷移が全部わかったので、実装するとACとなります。ちなみにbit演算でバグり散らかしました。今度から (X >> i) & 1ll って書きます.......。

うーん、見るべき条件が多いので、それらをしっかりと満たしながら遷移できるDPを考えるのに参ってしまいました。要訓練ですね。

maspyさんバージョンのDP

maspyさんの解法を見たらすごくて笑っちゃった。桁DPは総じて添え字地獄になりがちとか思ってたんですが、これなら実装が簡単ですね。

詳細は↑です。

DPできる問題は再帰的な構造をしているという事実が頭から抜けていました。こんなにシンプルに考えられるの、魔法みたいですね。

何というか、僕は頭が弱いから、DPを難しく考えてしまうのだなと思いました。