perarduaadastra

競技プログラミングとかをしています

ABC172 F - Unfair Nim 解法

atcoder.jp

 

本番ではDとEで事故ったのでF見てる余裕ありませんでした。なかなか面白い問題でしたね。

ABCでNim出たの超久しぶりじゃない?

 

解法:

まず、Nimは山の石の数の累積xorが0以外のとき先手必勝、0のとき後手必勝です。そういうわけなので、3番目以降の山の累積xorを X として計算しておきます。

 

(1番目の山) xor (2番目の山) = X

 

となれば良いということがわかります。

ところで、(1番目の山) + (2番目の山) = Sとすると、Sは不変です。

したがって、

 

(1番目の山) & (2番目の山) = S - X

 

であることがわかります。これは、(1番目の山) xor (2番目の山)をしたときに、(1番目の山) & (2番目の山)となる部分の寄与は0となることからわかります。(同じ数字同士のxorは打ち消し合うから)

 

ところで、この問題は「a0 以下で、S - Xの立っているbitを包含するもののうち(S - X)、X以外に立っているbitがない」もののうち最大のものを構築することになります。

S - Xのbitは1番目の山、2番目の山共に含むので、ここから先に構築していきましょう。

 

S - Xのbitを全部立てた時にa0を超えてしまったら構築不能なので-1を出力します。

あとは「最大のものを構築する」という条件から、大きい方のbitから「Xでも同じbitが立っているか」「これを立てたらa0を超えたりしないか」をチェックしながら貪欲にbitを立てることで1番目の山の理想的な形が構築できます。

 

最後に、得られた1番目の山の値を元の1番目の山から引けばいくら移動させたかがわかるのでこれを処理して答えを得ます。

 

計算量はO(N + log(a_0 + a_1))かと思います。構築パートのO(log(a_0 + a_1))を計算量として評価するのってどうなんだろう 冗長でしょうか。

 

atcoder.jp