2020年3月16日月曜日

CodeChef March Challenge 2020 - Break

CodeChef March Challenge 2020 - Break

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

S = 1

先手の手の列をx1,...,xNx_1, ..., x_N, 後手の手の列をy1,...,yNy_1, ..., y_Nとする。

まず、先手は一手目より小さいカードを出せない。つまり、先手の一手目は必ず最小のカードでなければならない。

後手も先手の一手目以下のカードは出せない。

先手の有効な手の列でxi>xi+1(i2)x_i > x_{i+1} (i \ge 2)となっている部分があったら、入れ替えが可能であることを示す。後手はxi+1x_{i+1}と等しいカードをiiターン目までに出したはずだが、ちょうどiiターン目には出せないので、iiターン目より前に出しているはず。したがって、xi,xi+1x_i, x_{i+1}の入れ替えと同時にyiy_iyi+1y_{i+1}も入れ替えれば有効な列のままである。

以上より、先手の手の列としてはカードを昇順にソートしたものだけ調べればよい。これに対する後手の手の列y1,...,yNy_1, ..., y_Nも昇順としてよいことを示す。yi>yi+1y_i > y_{i+1}となるiiがあるとき、入れ替えてもそれぞれのxi,xi+1x_i, x_{i+1}との大小関係は維持される。あとはyi+1y_{i+1}を先に出すことによってxi+1x_{i+1}が出せなくなる場合があるか検討する必要があるが、その場合はxi+1=yix_{i+1} = y_{i}が成り立つので、xi+1=yi>yi+1>xi+1x_{i+1} = y_{i} > y_{i+1} > x_{i+1}となって矛盾。

したがって、先手、後手のカードをそれぞれ昇順にソートして、有効な手の列になっているかどうか確かめればよい。

S = 2

盤面から消えたカードはbeatしたorされたものだけなので、同じ数字が書かれたカードがNN枚より多くあると引き分けることはできない。

いっぽう、以下のテクニックを使えば先手と後手のカードをだいたい任意に入れ替えることが可能なので、同じカードがNN枚以下の場合はだいたいYesということになる。

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

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

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

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

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