ARC208 | Notion

ARC208 A - Bitwise OR Game

コンテスト中
- N=1,2 から実験
  - N=1: 操作できないのでP局面
  - N=2:
    - どちらも1が立っている bit があれば N局面
      - 1が立っている部分を0にすればよい
    - なければ操作できないので P局面
  - N=3
    - ここから先が分からず
- エスパー
  - P局面エスパーではなく、grundy 数をエスパーする方針にした。
  - N=3 で grundy 数を求める実験コードを書いてエスパーしようとしたが法則性が見つけられず終わり
想定解法
知見
- grundy 数が不要なとき（P局面が分かれば十分なとき）は無理に grundy 数を求めないほうが良さそう。grundy 数が閉じた式で表せない場合、エスパー不可能なので。
  - grundy 数が閉じた式で表せない例: Wythoff の Nim
- 最終局面から考える。特に最終局面を xorで特徴づけられないかを考える
- 2進数で ab1xy と表せて、1 の部分を 0 にする場合、xy の部分は好きに設定できる。
メモ
- もうすこし Nim について理解をすべき？でも、Nim をちゃんと理解できてたとしてもこの問題は解けなかった気がする
- ARC の他のゲーム問題: ARC192 B - Fennec VS. Snuke 2
  - これは実験エスパーが通った回。

決定木学習

平面・立体的な表ではなく真理値表みたいな1次元の表で表すのがよかったかも

(他の問題でもこの反省に至った気がする)

ただの知識じゃなくて、深い理解が求められている