Contest Duration: - (local time) (100 minutes) Back to Home

## E - Lucky 7 Battle Editorial by en_translator

Let us consider if Takahashi is possible to win after the $$N-1$$ round. Let us regard $$T$$ as a decimal number and $$r$$ be the remainder by $$7$$. Also, we identify $$S_N$$ with the corresponding digit.

If $$X_N$$ is T, then Takahashi will win if either $$10r$$ or $$10r+S_N$$ is a multiple of $$7$$.
If $$X_N$$ is A, then Takahashi will win if both $$10r$$ and $$10r+S_N$$ are multiples of $$7$$.

As you can see, we can define the following DP, in the reversed order.

dp[i]=The set of integers $$r$$ that satisfies the following condition:
Condition: if the remainder of $$T$$ divided by $$7$$ is $$r$$ after the $$i$$-th round end, Takahashi will win

The initial state is $$dp[N]=\{0\}$$. The transitions are
if $$X_i$$ is T, $$dp[i-1]=\{ r \mid (10r \bmod 7) \in dp[i] \ \text{ or }\ (10r+S_i \bmod 7) \in dp[i]\}$$, and
if $$X_i$$ is A, $$dp[i-1]=\{ r \mid (10r \bmod 7) \in dp[i]\ \text{ and }\ (10r+S_i \bmod 7) \in dp[i]\}$$.

If $$0 \in dp[0]$$ at last, Takahashi wins; otherwise, Aoki wins. The time complexity is $$O(N)$$.

posted:
last update: