Official

C - 01 Game Editorial by leaf1415


マス目全体を、空白のマスが連続する(極大な)区間(以下、成分と呼ぶ)に分けて考えます。ゲーム全体は、各成分に関するゲームの和であるため、各成分に関するゲームの Grundy 数が分かれば、ゲーム全体の Grundy 数(特に、勝敗)もそれらの排他的論理和を求めることでわかります。

各成分に関するゲームの Grundy 数は、その成分の長さ(すなわち、構成する空白マスの個数)を \(n\) とすると下記の通りであることが数学的帰納法で証明できます。

  • 両端から異なる数字で挟まれている場合、Grundy 数は \(0\)
  • 両端から同じ数字で挟まれている場合、Grundy 数は \(1\)
  • 一方の端のみが数字と接している場合、Grundy 数は \(n\)
  • どちらの端も数字と接していない場合、Grundy 数は \(n \bmod 2\)

posted:
last update: