Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020

Updated:

日立製作所 社会システム事業部 プログラミングコンテスト 2020

Source codes

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

Answer

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

E - Odd Sum Rectangles

F - Preserve Diameter

Others