Official
C - 01 Game Editorial by leaf1415
マス目全体を、空白のマスが連続する(極大な)区間(以下、成分と呼ぶ)に分けて考えます。ゲーム全体は、各成分に関するゲームの和であるため、各成分に関するゲームの Grundy 数が分かれば、ゲーム全体の Grundy 数(特に、勝敗)もそれらの排他的論理和を求めることでわかります。
各成分に関するゲームの Grundy 数は、その成分の長さ(すなわち、構成する空白マスの個数)を \(n\) とすると下記の通りであることが数学的帰納法で証明できます。
- 両端から異なる数字で挟まれている場合、Grundy 数は \(0\) 。
- 両端から同じ数字で挟まれている場合、Grundy 数は \(1\) 。
- 一方の端のみが数字と接している場合、Grundy 数は \(n\) 。
- どちらの端も数字と接していない場合、Grundy 数は \(n \bmod 2\) 。
posted:
last update: