ひたすらゲームの性質を観察する。
S = 1
先手の手の列を$x_1, ..., x_N$, 後手の手の列を$y_1, ..., y_N$とする。
まず、先手は一手目より小さいカードを出せない。つまり、先手の一手目は必ず最小のカードでなければならない。
後手も先手の一手目以下のカードは出せない。
先手の有効な手の列で$x_i > x_{i+1} (i \ge 2)$となっている部分があったら、入れ替えが可能であることを示す。後手は$x_{i+1}$と等しいカードを$i$ターン目までに出したはずだが、ちょうど$i$ターン目には出せないので、$i$ターン目より前に出しているはず。したがって、$x_i, x_{i+1}$の入れ替えと同時に$y_i$と$y_{i+1}$も入れ替えれば有効な列のままである。
以上より、先手の手の列としてはカードを昇順にソートしたものだけ調べればよい。これに対する後手の手の列$y_1, ..., y_N$も昇順としてよいことを示す。$y_i > y_{i+1}$となる$i$があるとき、入れ替えてもそれぞれの$x_i, x_{i+1}$との大小関係は維持される。あとは$y_{i+1}$を先に出すことによって$x_{i+1}$が出せなくなる場合があるか検討する必要があるが、その場合は$x_{i+1} = y_{i}$が成り立つので、$x_{i+1} = y_{i} > y_{i+1} > x_{i+1}$となって矛盾。
したがって、先手、後手のカードをそれぞれ昇順にソートして、有効な手の列になっているかどうか確かめればよい。
S = 2
盤面から消えたカードはbeatしたorされたものだけなので、同じ数字が書かれたカードが$N$枚より多くあると引き分けることはできない。
いっぽう、以下のテクニックを使えば先手と後手のカードをだいたい任意に入れ替えることが可能なので、同じカードが$N$枚以下の場合はだいたいYesということになる。
- 先手提出 → 後手giveup → ... → 先手提出 → 後手giveupを繰り返したあと、
- 先手提出 → 後手提出 → 先手giveup で攻守を交代して
- 後手提出 → 先手giveup → ... → 後手提出→ 先手giveup
先手と後手は1と3で出したカードを交換したことになる。このあとは後手提出 → 先手提出 → 後手giveup→先手提出 → 後手提出 → 先手giveup→……を繰り返しながら、カードを2枚ずつ捨てていけばよい。
しかし、コーナーケースがいくつかある:
- $N=1, 2$の場合、上のテクニックを使おうとすると途中で先手のカードが尽きてしまうので、特別に処理する必要がある。
- 先手の初期手札の最小値$\ge$後手の初期手札の最大値がなりたっていて、先手または後手のカードがすべて同じ数の場合、上のテクニックがうまくいかない。
初手giveupができないルールと、カードがなくなった瞬間に終了するルールのおかげでだいぶ面倒になっている。
