AtCoder Beginner Contest 148

Updated:

AtCoder Beginner Contest 148

Source codes

Solutions

A - Round One

Flush $6 - A - B$.

B - Strings with the Same Length

Just do as they indicate us to.

C - Snack

Flush $\mathrm{lcm}(A, B)$.

D - Brick Break

We can compute the maximum of the remaining bricks by greedy algorithm.

E - Double Factorial

Solution

Let

$g(n, p) = $ how many times $n$ can be divided by $p$.

The answer is \[ g(n!!, 10) = \min(g(n!!, 2), g(n!!, 5)). \] If $n$ is odd, it immediately follows that $g(n!!, 2) = 0$. Hence the answer is zero. Hereinafter we assume that $n$ is even. We see that \[ \begin{align} n!! &= n \cdot (n - 2) \cdot \dots \cdot 4 \cdot 2, \\\ \frac{n}{2}! &= \frac{n}{2} \cdot \left( \frac{n}{2} - 1 \right) \cdot \dots \cdot 2 \cdot 1. \end{align} \] Therefore we see that \[ \begin{align} g(n!!, 2) &= g\left( \frac{n}{2}!, 2 \right) + \frac{n}{2}, \\\ g(n!!, 5) &= g\left( \frac{n}{2}!, 5 \right). \end{align} \] In addition, it follows that \[ g(n!, p) = \frac{n}{p} + g\left( \frac{n}{p}!, p \right) + \frac{n}{p}. \] And it stops by $g(0, p) = 0$.

F - Playing Tag on Tree

Solution

First of all, Takahashi-kun and Aoki-kun can’t pass each other. Takahashi-kun cannot reach the vertex $x$ where $\mathrm{dist} _ T(x) \geq \mathrm{dist} _ A (x)$. Of course the vertexes on Aoki-kun’s side won’t be reached by Takahashi-kun. Otherwise, let $y$ be the intersection point of Takahashi and Aoki on the pass from the initial vertexes. We have $\mathrm{dist} _ T(y) \geq \mathrm{dist} _ A (y)$, which means Aoki-kun can capture Takahashi-kun as long as he wants to reach $x$. On the contrary, Takahashi-kun can reach $x$ where $\mathrm{dist} _ T(x) < \mathrm{dist} _ A (x)$.

And we see that if Takahashi-kun reaches $x$, Aoki-kun will take $\mathrm{dist} _ A (x) - 1$ turns to capture him. Note that $-1$ means that Takahashi-kun will be captured in front of $x$. Therefore we can achieve \[ \max _ {x \colon \mathrm{dist} _ T(x) < \mathrm{dist} _ A (x)} \mathrm{dist} _ A (x) - 1. \] In addition, this is the maximum value since Aoki-kun cannot reach each $x$ by less than $\mathrm{dist} _ A (x)$ times.

Others