AtCoder Beginner Contest 144

Updated:

AtCoder Beginner Contest 144

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,

  1. For $(p, l) \in P _ u$, $p$ is the original probability in which we choose this path starting from $0$.
  2. 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]);
      }
    }
  }

Others