Edit

【pythonでABC195を解説】E - Lucky 7 Battle

問題概要

問題ページ

E - Lucky 7 Battle
E - Lucky 7 Battle

問題ページへ移動する

問題文

0,\(\ldots\),9 からなる長さ \(N\) の文字列 \(S\) と、A,T からなる長さ \(N\) の文字列 \(X\) が与えられます。また、空文字列で初期化された文字列 \(T\) があります。

高橋君と青木君がこれらを使ってゲームをします。ゲームは \(N\) ラウンドからなり、\(i\) 回目 \((1\leq i \leq N)\) のラウンドでは次の操作が行われます。

  • \(X_i\) が A なら青木君が、T なら高橋君が以下の操作を行う
  • 操作：\(T\) の末尾に \(S_i\) か 0 のどちらか一方を加える

\(N\) 回の操作が終了したあと、\(T\) は 0,\(\ldots\),9 からなる長さ \(N\) の文字列となります。
\(T\) を (先頭の余計な \(0\) を取り除いた上で) \(10\) 進法で表された数と解釈したとき、\(7\) の倍数であれば高橋君の勝ちであり、そうでなければ青木君の勝ちです。

\(2\) 人が最適に行動する時、どちらが勝つか判定してください。

制約

  • \(1 \leq N \leq 2\times 10^5\)
  • \(S,X\) の長さは \(N\)
  • \(S\) は 0,\(\ldots\),9 のみからなる
  • \(X\) は A,T のみからなる

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    x = str(input().rstrip('\n'))
    dp = [[0] * 7 for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        p = pow(10, i + 1, 7)
        for j in range(7):
            if dp[i][j] == 1:
                dp[i + 1][j] += 1
                dp[i + 1][(j + p * int(s[-i - 1])) % 7] += 1
        for j in range(7):
            if x[-i-1] == "T":
                if dp[i + 1][j] != 0:
                    dp[i + 1][j] = 1
            else:
                if dp[i + 1][j] == 2:
                    dp[i + 1][j] = 1
                else:
                    dp[i + 1][j] = 0
    print("Takahashi" if dp[-1][0] != 0 else "Aoki")


if __name__ == '__main__':
    solve()

-Edit
-