# Panasonic Programming Contest 2020

Updated:

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

# Solutions

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.

Tags:

Categories: