CodeChef March Challenge 2020 - Break

• 問題
• AC

ひたすらゲームの性質を観察する。

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ということになる。

1. 先手提出 → 後手giveup → ... → 先手提出 → 後手giveupを繰り返したあと、
2. 先手提出 → 後手提出 → 先手giveup で攻守を交代して
3. 後手提出 → 先手giveup → ... → 後手提出→ 先手giveup

先手と後手は1と3で出したカードを交換したことになる。このあとは後手提出 → 先手提出 → 後手giveup→先手提出 → 後手提出 → 先手giveup→……を繰り返しながら、カードを2枚ずつ捨てていけばよい。

しかし、コーナーケースがいくつかある:

• $N=1, 2$の場合、上のテクニックを使おうとすると途中で先手のカードが尽きてしまうので、特別に処理する必要がある。
• 先手の初期手札の最小値$\ge$後手の初期手札の最大値がなりたっていて、先手または後手のカードがすべて同じ数の場合、上のテクニックがうまくいかない。

---

初手giveupができないルールと、カードがなくなった瞬間に終了するルールのおかげでだいぶ面倒になっている。