AtCoder Beginner Contest 144

Source codesPermalink

• My submissions (AtCoder)
• My source codes (GitHub)

SolutionsPermalink

A - 9x9Permalink

If $A \leq 9$ and $B \leq 9$, flush $AB$. Otherwise, $-1$.

B - 81Permalink

Try all possibilities.

C - Walk on Multiplication TablePermalink

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 BottlePermalink

SolutionPermalink

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.

ImplementPermalink

To count times, we use a variable which will not appear inside {}, e.g. for (auto q{0}; q < 100; ++q).

E - GluttonyPermalink

ObservationPermalink

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.

SolutionPermalink

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 RoadPermalink

Assume $0$-indexed. Note that this graph is a DAG since it is guaranteed that $s _ i < t _ i$.

ObservationPermalink

Focusing on the differencePermalink

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?Permalink

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 partPermalink

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$Permalink

Initial statePermalink

$\alpha[0] = 1$, otherwise $0$.

TransitionPermalink

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].$$

ImplementPermalink

  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$Permalink

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$Permalink

Initial statePermalink

$S[u] = 0$ for all $u$.

TransitionPermalink

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]$.

ImplementPermalink

  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$Permalink

Initial statePermalink

$T[v] = 0$ for all $v$.

TransitionPermalink

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]).$$

ImplementPermalink

  void calc_T()
  {
    for (auto i = N - 2; i >= 0; --i)
    {
      for (auto j : V[i])
      {
        T[i] += prob(i) * (1.0 + T[j]);
      }
    }
  }

OthersPermalink