naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉ARC 072 D - Alice&Brown (500)

「二人とも最適にプレイすると仮定した」系のゲームが苦手すぎるのでじっくり考えた回。

こういうのが考えられるようになったら色1つぐらい上がる気がすると思うぐらい苦手だ……なんでみんな自明なことみたいに考えられるんだろう。

考察フェーズ

二次元の座標空間で考えてみる
2x+y=k、あるいはx+2y=kに沿って原点方向に(というかx+yを減らす方向に)進んで行って、x+y=1になったところでこれ以上打てなくなる*1
で、どう打つのが必勝解か、とか考えた(≒休むに似たり)辺りで寝落ち

解説読むフェーズ

1ポモドーロルールに従って解説を読む

結論としては、|X-Y|\le1のときBrown、そうでなければAliceが勝ちます。

なんだってー?
帰納法で説明してるけど、なにこの天下り的な解説…これをどう思いつけと?

  • X+Y\le1のとき(※|X-Y|=1しかありえない):これ以上打てないしBの勝ち
  • X+Y\gt1のとき
    • |X-Y|\le1のとき:何をしようが|X-Y|\gt1で相手に手番を渡してしまって相手が勝つ
    • |X-Y|\gt1のとき:多いほうの山から適切に取ることで|X-Y|\le1で相手に回せる

ぐぐってみた

みんな実験してみてる
ronly.hatenablog.com

必勝手、最善手という概念をちゃんと持ててないからシミュレーションが(手動だろうがプログラムだろうが)出来てないんだよね。

改めて考えてみた

  • もう動かせない状態(s_0):(0,1)or(1,0)or(1,1)が回ってきた=負け
  • s_0に1手で到達できる状態(s_1)が回ってきた=勝ち

そこまでは分かるんだ

s_1からは必ずしもs_0に繋がる手だけでなく、s_1などに繋がる手も打てる。王手だけど王を取る以外の動きをしたら勝てない。(だから勝てる時には必ず勝つ手を打つ的な縛りがあって、s_1に到達したプレイヤーは必ずs_0に繋がる手を打つ)

s_1に1手で到達できる状態(s_2)が回ってきた、じゃ定まらなくて

  • なにをどうしてもs_1にしかならない状態(s_2)が回ってきた=負け

だよね

そのs_2に持ち込める状態(s_3)が回ってきた=勝ち
...

というわけで

  • s_0が回ってきた=負け
  • s_{2k}に持ち込める状態(s_{2k+1})が回ってきた=勝ち
  • なにをどうしてもs_{2k+1}にしかならない状態(s_{2k})が回ってきた=負け

というのを今回のゲームにあてはめてみると。

// A-B対称なので片方だけ書くけど
s_0: (0,1),(1,1); (0,0)は除外してよいかと - これが回ってきたら必敗
s_1: (2k,-k)+(0 or 1,1) なのでk=1しかなくて (2,0)(3,0) - これが回ってきたら必勝
s_2: (2k,-k)+(0,2): k=1,2(2,1)(4,0)
  (2k,-k)+(0,3): k=1,2,3(2,2)(4,1)(6,0)
それぞれ最初のやつ(2,1)(2,2)が回ってきたら必敗だけど、2番目以降(4,0)(4,1)(6,0)が回ってきても最初のやつに持っていけるから必勝

ここまでで

  • 必勝: (2,0),(3,0),(4,0),(4,1),(6,0)
  • 必敗: (1,0),(1,1),(2,1),(2,2)

  • 必敗位置に(2k,-k) or (-k,2k)で行けるすべての位置は必勝
  • 動ける先 (+2,-1), (-1,+2)が必勝位置しかないすべての位置は(相手に必勝を譲る手しか打てないので)必敗。その延長線上にあるすべての位置は(前条件を満たすので)必勝。

この要領でシミュレーションコードを書いてみるか

シミュレーション書いてみた

  • キューに入れて幅優先探索→2方向から来るから勝ち負け判定がうまくいかない。直近の勝ち負けだけでは駄目。
  • x+y=k のkを1つずつ増やしていく形で、2方向をまっすぐ見て1つでもLOSEがあればWIN、さもなければLOSE、
$ ./sim 20
XXoooooooooooooooooo
XXXooooooooooooooooo
oXXXoooooooooooooooo
ooXXXooooooooooooooo
oooXXXoooooooooooooo
ooooXXXooooooooooooo
oooooXXXoooooooooooo
ooooooXXXooooooooooo
oooooooXXXoooooooooo
ooooooooXXXooooooooo
oooooooooXXXoooooooo
ooooooooooXXXooooooo
oooooooooooXXXoooooo
ooooooooooooXXXooooo
oooooooooooooXXXoooo
ooooooooooooooXXXooo
oooooooooooooooXXXoo
ooooooooooooooooXXXo
oooooooooooooooooXXX
ooooooooooooooooooXX

↑こういう(期待どおりの)結果になるまでの試行錯誤が長かった

提出

とても短い。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ll X,Y; cin >> X >> Y;
    bool alice = (llabs(X-Y) >= 2);
    cout << (alice ? "Alice" : "Brown") << endl;
    return 0;
}

→AC
https://beta.atcoder.jp/contests/arc072/submissions/2698344

*1:x=y=1でも動けなくなるのを考慮してなかった