AtCoder Regular Contest 132

Posted on 2021-12-29 Edited on 2022-02-24 In ARC

D - Between Two Binary Strings

notice the position of $n$-th '1' in a valid string should always between that in both s and t.

Yet this conclusion can be written in a more compact form: $\forall i, \#s[1,i]=\#t[1,i]$.

The problem can be solved greedily as long as the restrictions are meet.

Proof:

Consider a string to be a 2D path, where '0' means go forward and '1' means go up.

Thus we need to minimize the turns we made.

It's sufficient that we never make a turn unless we collide with the border.

Key: the resulting string always looks like this: <<<<<xxxxxxx>>>>>>, where x stands for the original character.

The key observation yields to a straight-forward DP solution.

Let's find the probability distribution of all possible situations.

Let $\sigma:[0,2]^k\times[0,2]^k\rightarrow [0,3]^k$ be the mappings from the strategy of 2 players to situations.

Suppose $s=\sigma(u,v)$, then

$$ s_i= \[\begin{cases} 3,u_i\neq v_i\\ u_i,u_i=v_i \end{cases}\]

We can calculate the probability distribution by convolution:

\[ Pr_s=\sum_{s=\sigma(u,v)}Aoki_uSnuke_v \]

To implement that, we simply derive a new transform from FWT, which will work in $O(k4^k)$ time.

Formally, Let $F_s=\sum_{s=\sigma'(u)}Aoki_u$, and $G_s=\sum_{s=\sigma'(u)}Snuke_u$.

Notice in mapping $\sigma'$, every $c\in[0,2]$ points to both $c$ and $3$.

Then $Pr_s=F_s \cdot G_s$ yields naturally.

To calculate the probability of Takahashi winning over all scenarios, we just need to perform a similar process.