Updated:

# Solutions

## A - Hitachi String

There are just $5$ strings.

## B - Nice Shopping

The minimum is achieved either by choosing the cheapest refrigerator and the cheapest oven range or by using the discount coupons.

## C - ThREE

### Solution

The condition $ab = 0$ or $a + b = 0$ is equivalent to $(a, b) \neq (1, 1), (2, 2)$ in $\mathbb{Z} / 3 \mathbb{Z}$.

A tree is a bipartite graph. We color each vertex by red or blue. Then, two vertexes whose distance is $3$ must be colored differently.

Therefore, it is suffice that we assign numbers for vertexes so that there are no pair of red/blue vertex and assigned for $(1, 1)$ or $(2, 2)$. This is done by the following way.

• The case both red and blue $\geq N / 3$: We assign $1$ for red side and $2$ for blue side as much as possible. Then assign $0$ for others.
• The case red $< N / 3$: We assign $0$ for red side. Then any numbers for others.
• The case blue $< N / 3$: Same as red.

## D - Manga Market

### Observation

Let $c _ i = a _ i + 1$ and $d _ i = a _ i + b _ i + 1$. Then, the $i$-th shop is the machine that leaps from the time $t$ to the time $f _ i(t) = c _ i t + d _ i$.

First, we show the following lemma.

Lemma D.1: Fix the indexes $I$ of the shops that Takahashi-kun will visit. Then, the minimum time is achieved in the descending order of $\{ f _ i \} _ {i \in I}$ with the weight $(c _ i - 1) / d _ i$. Here, the division is in $\mathbb{Q}$.

Proof: Assume to the contrary that the minimum time is achieved in another order of $\{ f _ i \} _ {i \in I}$ with the weight $(c _ i - 1) / d _ i$. Then, there is at least one adjacent pair $f _ i$ and $f _ j$ with $(c _ i - 1) / d _ i < (c _ j - 1) / d _ j$. We see that, in the current situation, we reach $i$-th shop at the time $t$ and then go to $j$-th shop. The resulting time is $T = f _ j \circ f _ i (t) = c _ i c _ j t + c _ j d _ i + d _ j.$ Swapping this order, however, we obtain the resulting time as follows. $T’ = f _ i \circ f _ j (t) = c _ j c _ i t + c _ i d _ j + d _ i.$ Then, we have $T - T’ = c _ j d _ i + d _ j - c _ i d _ j - d _ i > 0,$ which contradicts the assumption. This completes the proof.

Therefore, we can solve this problem by DP in $O(N ^ 2)$-time.

### Solution

For speeding-up, we divide the shops into two sets; $c _ i \geq 2$ and $c _ i = 1$. Note that, by Lemma D.1, we always consider visiting the shops with $c _ i = 1$ after the shops with $c _ i \geq 2$.

For the shops with $c _ i \geq 2$, we try the DP above. Thanks to the constraint $c _ i \geq 2$, we just possess the second key up to $C = 32 \approx \log _ 2 T$.

Then, we visit some shops with $c _ i = 1$ for each $j = 0, \dots, C - 1$. Obviously, we try $d _ i$’s ascending order. This part can be done by partial_sum and upper_bound. The time complexity is $O(N \log T + N \log N)$.

#### Definition

$dp[i][j] =$ the minimum time we take to visit $j$ stores considering up to the $i$-th store.

#### Initial State

$dp[0][0] = 0$, otherwise $\infty$.

$dp[M][j]$ for $j = 0, \dots, C - 1$. Then, we try the shops with $c _ i = 1$.

#### Transition

For $i = 0, \dots, M - 1$, for $j = 0, \dots, C - 1$, we execute the following. $dp[i + 1][j] \gets \min\left( dp[i][j], f _ i (dp[i][j - 1]) \right)$ Here, out-of-range will be considered as $\infty$.

Tags:

Categories: