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.
Submission
#28217621 - AtCoder Regular Contest 132
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.
Submission
#28219119 - AtCoder Regular Contest 132
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.
Submission
#28266429 - AtCoder Regular Contest 132