AtCoder Regular Contest 061
C Many Formulas
Given a string of digits from 1 to 9, with length at most 10, insert + signs between digits in every possible way and compute the sum of all resulting expressions.
Because the length is at most 10, brute force is sufficient.
D Snuke’s Coloring
Given an $H * W$ grid of black and white cells and the positions of $N$ black cells $(0 \le N \le \min(10^5, H * W))$, count how many $3 * 3$ subgrids contain each possible number of black cells from 0 through 9.
For every black cell, increment every $3 * 3$ subgrid that includes it. Represent a subgrid by its top-left cell and count how often it is covered.
E Snuke’s Subway Trip
There are $N$ stations and $M$ subway lines. Each line is built by a company. Switching to a line operated by a different company costs 1; find the minimum cost from station 1 to station $N$.
Use a priority queue plus BFS. Record both the current minimum cost at a station and the line used to arrive, so that the next move can determine whether its cost increases by 1.
F Card Game for Three
Every card carries one of the letters a, b, or c. A has $N$ cards, B has $M$, and C has $K$.
A starts by revealing the top card in their own deck. If it is a, A reveals again; if it is b, B takes the next turn; and similarly for C.
If it is a player’s turn and their deck is empty, that player wins.
Given $N$, $M$, and $K$, count the ways in which A wins.
Do not think of this as three stacks of cards; consider the sequence when the winner is decided. In the discussion’s example, if $N=5$, $M=4$, and $K=6$, A wins exactly when the sequence contains five as before the end, at most four bs, and at most six cs. If $x$ cards have been revealed, the remaining cards are arbitrary: $3^{N+M+K-x}$ possibilities.
For the revealed cards, the number of possibilities is
$$
ans={\begin{pmatrix}
n+x-1\
n-1
\end{pmatrix}}*fs(x)
\\
fs(x)=\sum_{i+j=x,i<=m,j<=k}{\begin{pmatrix}
x\
i
\end{pmatrix}}
$$
Now compute $fs(x)$ by finding its recurrence.
Draw Pascal’s triangle: $fs(x+1)$ is almost $2 * fs(x)$. If the count grows too large, subtract the earlier $C(x,m)$ or $C(x,k)$ term to obtain the recurrence.