ABC195Eの解答

E - Lucky 7 Battle (1609)

問題文

0, … ,9 からなる長さ N の文字列 S と、A,T からなる長さN の文字列 X が与えられます。また、空文字列で初期化された文字列 T があります。
高橋君と青木君がこれらを使ってゲームをします。ゲームは N ラウンドからなり、i 回目 (1 ≤ i ≤ N )のラウンドでは次の操作が行われます。
・X_i が A なら青木君が、T なら高橋君が以下の操作を行うが A なら青木君が、T なら高橋君が以下の操作を行う
・操作：T の末尾に S_i か 0 のどちらか一方を加える
N 回の操作が終了したあと、Tは 0, … ,9 からなる長さ N の文字列となります。 T を (先頭の余計な 0 を取り除いた上で) 10進法で表された数と解釈したとき、 7 の倍数であれば高橋君の勝ちであり、そうでなければ青木君の勝ちです。
2 人が最適に行動する時、どちらが勝つか判定してください。

制約

1 ≤ N ≤ 2×10^5
S, X の長さは N
S は 0, … ,9 のみからなる
X は A,T のみからなる

考察

初めに一般化したものの説明をして全体像を眺めたのちに、入力例を用いて具体的な遷移に関して説明をします。

ゲームの問題は後ろから考えるのが定石のようですので、後ろから考えましょう。

まずは N 回操作した後に高橋くんが勝てるかどうかを判定します。問題文の条件より、N 回操作した後の数字(文字列)が7の倍数であれば高橋くんの勝利です。これは 7 で割った余りが 0 であれば良さそうです。逆に余りが 1~6 であれば青木くんの勝利です。

こんな感じで、余りに注目をしていけば状態を考えられそうです。

次に一つ前に戻り、N-1回操作した時に高橋くんに勝ち目があるかを考えます。ここで N-1 回操作したときの数字を7で割った余りが r とします。このとき N 回目の操作で作れる余りは、modの性質から次の2つになります。

(10 * r + S_N)%7
(10 * r) % 7

N回目の操作で、S_Nを選択すれば上、0を書き込むと下になります。先程述べたようにこの値が0となればN-1時点において高橋くんは勝てます。

ただし、「この値が0となれば」と書きましたがどちらが0となれば良いのでしょうか、片方？両方？

この疑問はどちらの手番かを考えると解決できます。ポイントは高橋くんと青木くんはどちらも勝つために最適な行動を選択することです。

高橋くんの手番の場合、もしどちらか一方でも勝つことのできるならそちらを選択します。もう片方の状態に依りません。一方、青木くんの手番の場合、片方でも高橋くんの負け(青木くんの勝ち)があればそちらを選択できます。しかし、両方の値が高橋くんの勝ちとなる場合、しょうがないので高橋くんの勝ちとなるものを選択します。

したがって、手番が高橋くんのときは

(10 * r + S_N)%7の値が勝利
または
(10 * r )%7の値が勝利

手番が青木くんのときは

(10 * r + S_N)%7の値が勝利
かつ
(10 * r)%7の値が勝利

でN-1、余りがrのときに高橋くんが勝利できるわけです。

この操作をどんどん戻していきましょう。なのですが、これ以降は 0 となれば良いわけではないです。勝てる状態になれば良いです。これに関しては後述の具体例にて説明します。0回操作後の余りが0(初期状態の数は0)で高橋くんが勝利できれば、そのゲームは高橋くんの勝ちとなります。

こちらは

dp[i][j] : i 操作終了後の余りが j のときに高橋くんが勝てるかどうか（勝てるなら 1 ）。

というdpを N から 0 まで戻ることにより解くことが可能です。

ここまで N など一般化したものについて考えてきました。次に、一つ具体例を見てみます。

入力例 1
3 5
A T

まず、2回の操作終了後にはその余りが 0 のときのみ高橋君は勝利できます。一つ戻ります。1 回目の操作終了後です。この場合における遷移を全部書き出して見ましょう。

余り r からr1、r2の２つに遷移します。2回目の操作は高橋君の手番ですので、dp[2][r1]とdp[2][r2]のどちらかが 1 となっていればdp[1][r]も1となります。今回、dp[2][0]のみ1ですので、r1もしくはr2が0となる、r=0、3において高橋くんは勝利できます。ですので、dp[1][0]とdp[1][3]が 1 となります。少しだけ一般化しますと高橋くんの手番の時には

dp[i][r] = dp[i+1][r1] | dp[i+1][r2]

と遷移します。

次に1回目の操作を考えます。つまり、0回操作したあと（開始直後）です。この場合の遷移も全部書き出しましょう。

今回の手番は青木くんですね。ですので、余りqの遷移先のq1、q2ともに高橋くんが勝てなければ、高橋くんの勝利はありません。遷移を見ますとq = 0のときに、q1=0、q2=3となってます。dp[1][0]とdp[1][3]はどちらも 1 となってますので、dp[0][0]は1となります。このように青木くんの遷移も一般化しますと

dp[i][q] = dp[i+1][q1] & dp[i+1][q2]

となります。dp[0][0]が1となりましたので、これで晴れて高橋くんが勝利できるわけです。おつかれさまでした。

遷移の図を下に示します。上の遷移情報の図と合わせてご覧いただけると理解が深まるかと思います。

以上の遷移を実装すれば答えが求まります。配列の添字が少々ややこしいですが落ち着いて実装しましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int N = 2e5;
int dp[N+5][7];

int main()
{
   int n;
   string s,x;
   cin >> n >> s >> x;

   dp[n][0] = 1;
   for(int i = n-1;i>=0;--i)
   {
       rep(j,7)
       {
           int r1 = (10*j)%7;
           int r2 = (10*j+(s[i]-'0'))%7;
           if(x[i] == 'T') dp[i][j] = dp[i+1][r1] | dp[i+1][r2];
           else dp[i][j] = dp[i+1][r1] & dp[i+1][r2];
       }
   }
   if(dp[0][0] == 1) cout << "Takahashi"<< endl;
   else cout << "Aoki" << endl;
   return 0;
}

あとがき

ゲームの問題はいくつか見ましたが、どれも難しかったため見なかったことにしてました。ですので、本問題にて初めて真面目に考察をしました。

難しいです。後ろから前方向にdpを行うという操作を理解するのに時間がかかりました。具体的な遷移を書き出してみて、ようやくしっくりときました。こればかりは慣れの問題もあると思いますので、これから類題に触れるにつれて少しずつその違和感を減らしていきたいなと思います。