AtCoder Beginner Contest 149


AtCoder Beginner Contest 149

Explanation in YouTube Live

Source codes


A - Strings

Execute cout << T << S << endl;.

B - Greedy Takahashi

Do as following, not to make silly mistakes.

  ll x{min(A, K)};
  A -= x;
  K -= x;
  ll y{min(B, K)};
  B -= y;
  K -= y;

C - Next Prime

Use your library.

D - Prediction and Restriction

The greedy algorithm works. We should win as many times as possible. If we skip the win of $i$-th duel when we can win, the reward after that will be at most $1$ winning, the $i + K$-th duel. Thus we should win $i$-th duel.

E - Handshake

The binary search works. We sort $\{ A _ i \}$ in the descending order. Fix $X$ as the minimum score we gain by shaking hands. For $i = 0, \dots, N - 1$, we determine the maximum $j$ so that $A _ i + A _ j \geq X$. We sum up these $j$’s and we see whether this is less than or equal to $M$. Then we again apply the binary search for $X$.

The answer is the sum of the scores greater than or equal to $X$ plus $X - 1$ to fill up to $M$.

F - Surrounded Nodes


We calculate the sum of the holeyness instead of the expectation of it. It will be the sum of the holeyness of each vertex. Fix one vertex $v$. How many possibilities are there which cause $v$ to be a hole?

This is calculated as follows. We once regard $v$ as the root of $T$. Each subtree of the children of $v$ will be considered. The white-colored $v$ will be a hole if and only if all the subtrees contains at least one black vertex. This will be calculated as follows. \[ 2 ^ {N - 1} - \prod _ {w \in children[v]} \left( 2 ^ {cnt[w]} - 1 \right) \tag{F.1} \]


We have to compute the sum of those in $O(N)$-time or so. This is done by tree-DP. The problem is that we cannot hold $children[v]$ unless $v$ is the root. But we can do the same manipulation. The missing “child” and its subtree is actually the parent and theirs. We need its size, which we can compute by $N - 1 - \sum cnt[w]$. Then, (F.1) works.


A - sample: 2, tle: 2.000, time: 00:27, from_submit: 97:20
B - sample: 2, tle: 2.000, time: 01:42, from_submit: 95:38
C - sample: 3, tle: 2.000, time: 02:22, from_submit: 93:16
D - sample: 3, tle: 2.000, time: 12:59, from_submit: 80:16
E - sample: 3, tle: 2.000, time: 54:26, from_submit: 25:50
F - sample: 4, tle: 2.000, time: 25:51, from_submit: 00:00

I’m sad to hear that this contest was unrated.