Panasonic Programming Contest 2020

Updated:

パナソニックプログラミングコンテスト2020

Source codes

Solutions

A - Kth Term

Use array.

B - Bishop

Solution

Lemma B.1: The points $(i, j)$ with $i + j = 1$ in $\mathbb{Z}/2\mathbb{Z}$ are never reached.

Proof: By argument on equivalence class.

Lemma B.2: If $H, W \geq 2$, the points $(i, j)$ with $i + j = 0$ in $\mathbb{Z}/2\mathbb{Z}$ are reached.

Proof: By mathematical induction for the column number.

Obviously, if $H = 1$ or $W = 1$, the answer is $1$.

C - Sqrt Inequality

Solution

Since $a, b, c \approx 10 ^ 9$, we should avoid double.

\[ \begin{align} \sqrt{a} + \sqrt{b} < \sqrt{c} &\Longleftrightarrow (\sqrt{a} + \sqrt{b}) ^ 2 < c \\\ &\Longleftrightarrow a + b + 2 \sqrt{ab} < c \\\ &\Longleftrightarrow 2 \sqrt{ab} < c - a - b \\\ &\Longleftrightarrow c - a - b > 0 \land 4ab < (c - a - b) ^ 2. \end{align} \]

D - String Equivalence

Solution

A string $S$ is in normal form if and only if the followings hold.

  • $S[0] =$ 'a',
  • For any $i \in \lvert S \rvert$, $S[i] \leq \max _ {k \in i} S[k] + 1$.

Thus all the strings in normal form will be flushed by DFS.

E - Three Substrings

F - Fractal Shortest Path

Others