AtCoder Beginner Contest 149
Updated:
Source codes
Solutions
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, that is, that of the $i + K$-th duel. Thus we should win $i$-th duel.
E - Handshake
Solution
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$.
Caution Points
The answer is the sum of the scores greater than or equal to $X$ plus $X - 1$ to fill up to $M$.
Use ll for $N$ and $M$.
Tips
We can use partial_sum as follows.
vector<ll> V(N);
for (auto i{0}; i < N; ++i)
{
cin >> V[i];
}
vector<ll> sum(N + 1); // + 1.
partial_sum(V.begin(), V.end(), sum.begin() + 1); // + 1.
F - Surrounded Nodes
Observation
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} - 1 - \prod _ {w \in children[v]} \left( 2 ^ {cnt[w]} - 1 \right) \tag{F.1} \]
Solution
We have to compute the sum of those in $O(N)$-time or so. This is done by tree-DP (or just DFS). 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 its parent and ancestors. We need its size, which we can compute by $N - 1 - \sum cnt[w]$. Then, (F.1) works.
Others
Actual contest:
Assignments:
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.
Review 2020-06-10:
Assignments:
A - sample: 2, tle: 2.000, time: 01:25, from_submit: 65:15
B - sample: 2, tle: 2.000, time: 02:01, from_submit: 63:14
C - sample: 3, tle: 2.000, time: 01:42, from_submit: 61:32
D - sample: 3, tle: 2.000, time: 05:15, from_submit: 56:17
E - sample: 3, tle: 2.000, time: 38:52, from_submit: 17:25
F - sample: 4, tle: 2.000, time: 17:25, from_submit: 00:00