018: 「石の上にもニム」のヒント¶

難易度: ☆☆

ヒント1

盤面全体の良し悪しは、各山を個別に見るだけでは決まりません。複数の山の石数を、ビット単位でまとめて考えます。

ヒント2

Pythonでは、排他的論理和を ^ で計算できます。すべての山の石数を ^ で畳み込んだ値を、ニム和と呼びます。

ヒント3

ニム和が0の局面には、必勝手がありません。ニム和が0でない局面では、どれか1つの山を減らして、相手にニム和0の局面を渡せます。

ヒント4

ニム和を s、ある山の石数を pile とします。 target = pile ^ s が pile より小さければ、その山を target 個に減らせます。