AtCoder Beginner Contest 144
Updated:
Source codes
Solutions
A - 9x9
If $A \leq 9$ and $B \leq 9$, flush $AB$. Otherwise, $-1$.
B - 81
Try all possibilities.
C - Walk on Multiplication Table
We can try all possibilities. Since the distance between $(1, 1)$ and $(i, j)$ is equal to that between $(1, 1)$ and $(j , i)$, we can assume that $i \leq j$ without loss of generality. Therefore, it suffice to try $i \leq 10 ^ 6 + 10$.
D - Water Bottle
Solution
This is a elementary trigonometric function problem.
First of all, we use $y = x / a$ to convert this problem into $2$-dimensional problem.
Let $\theta$ be the resulting angle. We consider the limit of $\theta$.
If $y \geq ab / 2$, we have \[ y = S(\theta) = ab - \frac{1}{2} a ^ 2 \tan \theta. \tag{D.1} \]
If $y \leq ab / 2$, we have \[ y = S(\theta) = \frac{b ^ 2}{2 \tan \theta}. \tag{D.2} \]
Whether we use (D.1) or (D.2), we can determine $\theta$ by binary search since the greater $\theta$ is, the smaller $S(\theta)$ is. At first we set $lb = \epsilon$ and $ub = \pi / 2 - \epsilon$ for some fixed small $\epsilon$ and it suffice to try $100$ times.
Implement
To count times, we use a variable which will not appear inside {}, e.g. for (auto q{0}; q < 100; ++q).
E - Gluttony
Observation
Let $x _ i$ be the consumption coefficient of Member $i$ and $y _ i$ be the difficulty of the food Member $i$ eats. Then, the total score is \[ S = \max _ {i \in N} x _ i y _ i \] We want to minimize $S$. How should we assign foods to each Member $i$? This is obvious: we sort $\{ x _ i \}$ in ascending order and $\{ y _ i \}$ in descending order.
Then, we count the trainings into account. The less score we aim, the more training we need. Thus, this can be solved by binary search.
Solution
Let $ng = -1$ and $ok = 10 ^ {12} + 10$. We prepare
$f(k) = $ how many trainings we need to achieve the score $k$.
This is calculated as follows. \[ f(k) = \sum _ {i \in N} \left( x _ i - \frac{k}{y _ i} \right). \]
Here is an example of the implement.
auto f = [&](ll k) {
ll cnt{0};
for (auto i = 0; i < N; ++i)
{
cnt += max(0LL, A[i] - k / F[i]);
}
return cnt <= K;
};
Then, Meguru’s binary search works as follows.
ll ok{1'000'000'000'010LL};
ll ng{-1LL};
while (abs(ok - ng) > 1)
{
ll t{(ok + ng) / 2};
if (f(t))
{
ok = t;
}
else
{
ng = t;
}
}
cout << ok << endl;
F - Fork in the Road
Assume $0$-indexed. Note that this graph is a DAG since it is guaranteed that $s _ i < t _ i$.
Observation
Focusing on the difference
Let $P _ u$ be the set of the paths from $0$ to $u$. Let $Q _ v$ be the set of the paths from $u$ to $N - 1$. We regard $P _ u$ and $Q _ v$ as the set such as $(p, l) \in P _ u$, where $p$ is the probability in which we take the path and $l$ be the length of the path. Later, it will be critical to distinguish original probability and conditional probability. Thus here we write down the strict definitions.
Notation F.1: We regard $(p, l) \in P _ u$ or $(p’, l’) \in Q _ v$ as the set of the probability and the length of the path. More precisely,
- For $(p, l) \in P _ u$, $p$ is the original probability in which we choose this path starting from $0$.
- For $(p’, l’) \in Q _ v$, $p$ is the conditional probability in which we choose this path starting from $v$.
Here, we consider the path from $u$ to $v$. We want to change the probability in which we choose this path. How much it affects the total expectation of the whole length in which Takahashi-kun will take?
Let $\delta$ be the difference of the probability and $\Delta$ be the difference of the whole expectation. Then we have
\[
\Delta = \sum _ {(p, l) \in P _ u} \sum _ {(p’, l’) \in Q _ v} p \delta p’ (l + 1 + l’).
\]
Here, we define
\[
\begin{align}
\alpha _ u &= \sum _ {(p, l) \in P _ u} p, \\
\beta _ v &= \sum _ {(p’, l’) \in Q _ v} p’, \\
S _ u &= \sum _ {(p, l) \in P _ u} pl, \\
T _ v &= \sum _ {(p’, l’) \in Q _ v} p’l’.
\end{align} \tag{F.1}
\]
Then, we have
\[
\Delta = \delta \left( \beta _ v S _ u + \alpha _ u T _ v + \alpha _ u \beta _ v \right). \tag{F.2}
\]
How to obtain the answer?
The expectation of the total length is $total = S[N - 1]$. We can measure the efficiency blocking the passages $(u, v)$ as follows.
Let $V[u]$ be the set of the passages from $u$. Suppose that we have reached $u$. Then, the probability Takahashi-kun chooses each passage will be $1 / \lvert V[u] \rvert$. If $\lvert V[u] \rvert = 1$, Aoki-kun cannot block it. Hereinafter we assume $\lvert V[u] \rvert \geq 2$. Assume that Aoki-kun has blocked the passage $(u, v)$. We can regard this move as follows. The probability in which Takahashi-kun chooses $(u, v)$ will be $0$. And those related to other passages will be $1 / (\lvert V[u] \rvert - 1)$. Both of these effects are measured by (F.2), since these manipulations will not affect each other.
To simplify the implement of the solution, first we sum up the effects of $1 / (\lvert V[u] \rvert) \mapsto 1 / (\lvert V[u] \rvert - 1)$. Then we add to it the effect $1 / (\lvert V[u] \rvert - 1) \mapsto 0$.
DP part
We have to calculate the four DP tables. The definitions are written in (F.1). The “answers” are the DP tables themselves. So we have to determine the initial state and the transition of each table.
$\alpha$
Initial state
$\alpha[0] = 1$, otherwise $0$.
Transition
For $i = 0, \dots, N - 2$, for $j \in V[i]$, we execute the following. \[ \alpha[j] \mathbin{ {+} {=} } \frac{1}{\lvert V[i] \rvert} \alpha[i]. \]
Implement
void calc_alpha()
{
alpha[0] = 1.0;
for (auto i = 0; i < N - 1; ++i)
{
for (auto j : V[i])
{
alpha[j] += prob(i) * alpha[i];
}
}
}
$\beta$
By definition of $p’$ and $\beta$. $\beta[v]$ is the probability in which we reach $N - 1$ starting from $v$ when we have reached $v$. This is obviously $1$ thank to the constraints. The result is $\beta[v] = 1$ for all $v$.
$S _ u$
Initial state
$S[u] = 0$ for all $u$.
Transition
For $i = 0, \dots, N - 2$, for $j \in V[i]$, we execute the following. \[ S[j] \mathbin{ {+} {=} } \alpha[i] \frac{1}{\lvert V[i] \rvert} \times 1 + \frac{1}{\lvert V[i] \rvert} \times S[i]. \] This is because, for the former part, we choose $(i, j)$ in the probability $\alpha[i] \times 1 / \lvert V[i] \rvert$ and, for the latter part, we add the expectation of the length through $0 \to i$ to $S[j]$.
Implement
void calc_S()
{
for (auto i = 0; i < N - 1; ++i)
{
for (auto j : V[i])
{
S[j] += alpha[i] * prob(i) * 1.0 + prob(i) * S[i];
}
}
}
$T _ v$
Initial state
$T[v] = 0$ for all $v$.
Transition
For $i = N - 2, \dots, 0$, we can calculate $T[i]$ as follows. \[ T[i] = \sum _ {j \in V[i]} \frac{1}{\lvert V[i] \rvert} (1 + T[j]). \]
Implement
void calc_T()
{
for (auto i = N - 2; i >= 0; --i)
{
for (auto j : V[i])
{
T[i] += prob(i) * (1.0 + T[j]);
}
}
}