[AtCoder - ABC195 E] Lucky 7 Battle

난이도: 1609

 

태그

• Game Theory
• Dynamic Programming (with Game Theory)
• Modular Arithmetic

 

풀이

1. 게임의 시작, 중간, 끝 과정을 어떻게 나타낼 수 있을까?

어차피 종료 시점에서 필요한 건 7의 배수 여부입니다.

 

그러므로, 중간 과정은 현재까지 계산된 수 mod 7을 가지고 있으면 되겠죠.

물론 몇 턴을 진행했는가 역시 과정에 저장하고 있어야 합니다.

 

그러므로, 실제 상태는 "\( (i, x) \) = \( i \)번의 턴을 진행했고, 현재 쓰인 값 mod 7은 \( x \)"로 나타낼 수 있습니다.

 

2. [1]에서 정의한 상태를 두고 볼 때, 그 상태에서 누가 승리하는지 알아내보자.

\( dp_{i, x} \) = 상태 \( (i, x) \)에서 승리하게 될 사람을 정의해보면,

게임이 끝난 상태인 \( dp_{N, x} \)에 대해서는 간단히 계산할 수 있습니다.

// \( dp_{N, 0} = \text{Takahashi} \), \( dp_{N, x} = \text{Aoki} \)

 

\( (i, x) \)에서 플레이어가 할 수 있는 행동은 2가지가 있습니다.

\( (i, x) \rightarrow (i+1, 10x) \)와 \( (i, x) \rightarrow (i+1, 10x + X_{i+1}) \)죠.

그리고, 각 플레이어는 자신이 승리하는 상태로 만들기를 원합니다.

 

즉, 만약 도달 가능한 상태 중 자신이 승리하는 것이 있다면, 그 상태로 갈 수 있기 때문에 자신이 승리한다고 체크하면 됩니다.

만약 불가능하다면, 상대의 승리가 되겠죠.

 

이를 \( dp_{0, *} \)까지 전파해주면 됩니다.

 

3. 그럼, 결국 승리하는 사람은?

게임의 초기 상태, 즉 \( (0, 0) \)에서 이기는 사람이 됩니다.

즉, \( dp_{0, 0} \)이죠.

 

4. 코드

Takahashi를 1, Aoki를 0으로 잡았습니다.

bool dp[200020][7];
 
void Main(){
    int sl; string s, t; cin >> sl >> s >> t;
    dp[sl][0] = 1;
    for (int i = sl-1; i >= 0; i--){
        for (int x = 0; x < 7; x++){
            int y0 = 10*x % 7, y1 = (10*x + s[i]-'0') % 7;
            if (t[i] == 'T'){ dp[i][x] = dp[i+1][y0] || dp[i+1][y1]; }
            else{ dp[i][x] = dp[i+1][y0] && dp[i+1][y1]; }
        }
    }
    /*for (int i = 0; i <= sl; i++){
        for (int x = 0; x < 7; x++){ cout << dp[i][x] << ' '; }
        cout << endl;
    }*/
    int x = (s[0]-'0') % 7;
    cout << (dp[0][0] ? "Takahashi" : "Aoki");
}