全国統一プログラミング王決定戦 エキシビジョン
Updated:
一発ネタが多いので、問題自体は難しくないですが、初見で 20 分で通すのはまじで難しいと思います。
Source codes
Solutions
A - Prefix Array
$1$ から $N$ を順に出力する。
B - 二乗
$1$ から $100010$ まで順に $A$ を試していき、 $A^2 > N$ ならば break; する。
C - 11で割った余りの計算方法
$N \% 11$ を出力する。
D - 辞書順最小の数
答えは $1000 \dots 0$ である。ただし $N$ 桁である。
まず $1$ を出力する。 $N {- -}$ とする。あとは $N$ 回 $0$ を出力する。
E - スーパーFizzBuzz
これは指示通りやるだけです。
ポイント
これを高速に実装するところにトップ層のすごさが現れ、エンタメ性が出るというのが出題の趣旨でしょうけども、なんかもう解説しているうちにピューンと過ぎてしまいましたね。
F - コラッツ問題
$P = 1000$ のときの答えが $X = 1789997546303$ と与えられているので、
- $X$ が偶数ならば $X \gets X / 2$ 、
- $X$ が奇数ならば $X \gets 3X + 1$
とするのを $(1000 - P)$ 回すると答えになる。
ポイント
chokudai さんによると一発ネタだそうだ。確かに。
G - 回文スコア
解法
$S$ から生成される最も長い回文の長さを $L$ とし、それで使わなかった文字(つまり $1$ 文字からなる回文)の個数を $n$ とすると、答えは $L^2 + n$ である。
解法の正当化
スコアの最大値を与える回文の集合を $\{ S _ 1, S _ 2, \dots, S _ K \}$ とする。並べ替えることにより $\lvert S _ 1 \rvert \geq \lvert S _ 2 \rvert \geq \dots \geq \lvert S _ K \rvert \geq 1$ と仮定してよい。ここで $K = 1$ または $\lvert S _ 2 \rvert = 1$ であることを示せば上記の解法が正当化される。
$K \geq 2$ と仮定する。 $L _ 1 = \lvert S _ 1 \rvert$, $L _ 2 = \lvert S _ 2 \rvert$ とする。
$L _ 1, L _ 2$ の片方が偶数の場合であると仮定する。 $S _ 1$ と $S _ 2$ を結合して長さ $(L _ 1 + L _ 2)$ の回文が生成される。このとき、 \[ (L _ 1 + L _ 2)^2 = L _ 1 ^ 2 + 2 L _ 1 L _ 2 + L _ 2 ^ 2 > L _ 1 ^ 2 + L _ 2 ^ 2 \] であるから、スコアは必ず大きくなる。これはスコアの最大性に反する。
よって $L _ 1, L _ 2$ の両方とも奇数であることになる。まず $S _ 1, S _ 2$ の「中央の文字」が一致している場合は、長さ $(L _ 1 + L _ 2)$ の新しい回文が生成されるから、上記議論と合流する。したがってこれはありえない。よって中央の文字は異なることになる。この場合、長さ $(L _ 1 + L _ 2 - 1)$ の回文と長さ $1$ の回文を新たに生成することができる。元のスコアは最大値であったのだから、次式が成立する。 \[ (L _ 1 + L _ 2 - 1) ^ 2 + 1 ^ 2 \leq L _ 1 ^ 2 + L _ 2 ^ 2. \] 変形すると、次式が得られる。 \[ (L _ 1 - 1)(L _ 2 - 1) \leq 0. \] $L _ 1 - 1 \geq L _ 2 - 1 \geq 0$ より、これが実現するのは、 $L _ 2 = 1$ しかない。これが示すべきことであった。
ポイント
競技プログラミングに慣れていれば直感的に答えがわかる問題かと思う。証明には結構骨が折れるが一直線である。
H - 8^kゲーム
解法
$N$ を $9$ で割った余りを $X$ とする。 $X = 0, 2, 4, 6$ ならば Lose 、 $X = 1, 3, 5, 7, 8$ ならば Win である。
解法の正当化
2019/02/19 更新：昔の証明をかなり簡単にすることに成功しました。昔の証明はこの記事の末尾につけます。
$L = \{ 0, 2, 4, 6 \} \subset \mathbb{Z} / 9\mathbb{Z}$ とし、 $W = (\mathbb{Z} / 9\mathbb{Z}) \setminus L$ とする。問題文に書かれている操作を「操作 $k$ 」と呼ぶことにする。
$F = N \% 9 \in \mathbb{Z} / 9\mathbb{Z}$ とする。
まず、次の補題を示す。
補題 1：任意の可能な操作について、その操作を $1$ 回行うことにより、 $F \gets F - 1$ または $F \gets F + 1$ となる。
証明： $- 8^k = - (-1)^k$ は $\pm 1$ のいずれかであるから。
補題 2： $F \in L$ ならば、任意の可能な操作について、その操作を $1$ 回行うことにより $F \in W$ になる。
証明：補題 1 を用いて $F \in L$ の全ての場合について愚直に調べればよろしい。
補題 3： $F \in W$ ならば、ある可能な操作が存在し、その操作を $1$ 回行うことにより $F \in L$ になる。
証明：補題 1 を用いると、次の 2 つの場合以外は補題 2 と同様に証明される(というかどのように操作をしても良い)。したがって、次の 2 つを示せば証明が完了する。
- $F = 8$ の場合に $F \gets 0$ となるような可能な操作が存在する。
- $F = 7$ の場合に $F \gets 6$ となるような可能な操作が存在する。
このうち 1. は $N \geq 8$ であるから、 $k = 1$ の操作で可能である。 2. は $k = 0$ の操作で可能である。
解答の正当化： 初期段階で $N = F \in L \text{ in } \mathbb{Z} / 9\mathbb{Z}$ の場合は、補題 2 により、高橋君がどのような操作をしても $F \in W$ となる。よって補題 3 により青木君は $F \in L$ とできる。これを繰り返していくと、青木君のターンの操作後 $N = 0$ となる。よって高橋君は Lose となる。
初期段階で $N = F \in W \text{ in } \mathbb{Z} / 9\mathbb{Z}$ の場合は、補題 3 により、高橋君が適切に操作をすることにより $F \in L$ となる。よって補題 2 により青木君は $F \in W$ とする他ない。これを繰り返していくと、高橋君のターンの操作後 $N = 0$ となる。よって高橋君は Win となる。
ポイント
上のような証明は制限時間内では思いつかないだろうが、トップクラスの人なら少々実験すれば実験結果から予想がついてしまうので実装でき AC を取れるだろうという意図が見て取れる。
この問題のセットの C - 11で割った余りの計算方法 が証明のヒントになっている という、非常に凝っているセットだと思う。
Others
Writer の chokudai さんは「一発ネタが多い」と謙遜しておられたが(確かに F は一発ネタ)、 E はモロに実装力が出るからあのような舞台で高速に AC を取れるのはすごい盛り上がるだろうし、 G はある程度のクラスなら証明より先に直感で実装できるタイプの問題、 H はトップクラスなら規則性を見抜いて実装してしまうだろうという問題である。そして実際 semiexp さんは実装して全問正解したのである。さらに C が H の解法の布石になっているので、こうやって解説を書いていても味わい深い。
「見る人にとっても、やる人にとっても、あとで遊ぶ人にとっても面白い」という、全体的に chokudai さんの writer としての凄さが垣間見えるセットであった。
H の昔の証明
$\{ a _ i \} _ {i = 0} ^ K$ を $N$ の $8$ 進法表記とする。すなわち $0 \leq i \leq K$ に対し $0 \leq a _ i \leq 7$ が成立し、次式が成立する。 \[ N = \sum _ {i = 0} ^ K a _ i 8 ^ i. \tag{H.1} \] 次式が鍵である。 \[ F = \sum _ {i = 0} ^ K (-1)^i a _ i \text{ in } \mathbb{Z} / 9\mathbb{Z}. \tag{H.2} \]
まず、次の補題を示す。
補題 1：任意の可能な操作について、その操作を $1$ 回行うことにより、 $F \gets F - 1$ または $F \gets F + 1$ となる。
証明：元の式でも考えられる人はそれでいいけど、私は \[ F = a _ 0 + 8 a _ 1 + a _ 2 + 8 a _ 3 + \dots + (-1)^K a _ K \] の方が考えやすいので、これで以下記述をする。操作 $k$ を行うものとする。すると以下の通りに場合分けされる。
- $a _ k \geq 1$ のとき： $a _ k \gets a _ k - 1$ になるので、 $F$ は $1$ 減るか、 $8$ 減ることになる。すなわち $\mathbb{Z} / 9\mathbb{Z}$ 上で $1$ 増えるか、 $1$ 減ることになる。
- $a _ k = 0$ のとき：操作の可能性により、 $l > k$ が存在し、 $a _ l \geq 1$ である。このとき、 $a _ l \gets a _ l - 1$ 、かつ $k \leq i \leq l - 1$ に対し $0 = a _ k \gets 7$ となる。前者により、 $F$ は $1$ 減るか、 $8$ 減ることになる。
- 前者で $1$ 減る場合： $7 = -2$ 及び $7 \cdot 8 = 56 = 2$ より、結局後者では合計で $2$ 増えるか $\pm 0$ である。つまり総計では $F$ は $1$ 減るか $1$ 増えるかしかない。
- 前者で $8$ 減る場合：同様に考察すると、後者では $2$ 減るか $\pm 0$ である。つまり総計では $1$ 減るか $1$ 増えるかしかない。
補題 2： $F \in L$ ならば、任意の可能な操作について、その操作を $1$ 回行うことにより $F \in W$ になる。
証明：補題 1 を用いて $F \in L$ の全ての場合について愚直に調べればよろしい。
補題 3： $F \in W$ ならば、ある可能な操作が存在し、その操作を $1$ 回行うことにより $F \in L$ になる。
証明：補題 1 を用いると、次の 2 つの場合以外は補題 2 と同様に証明される(というかどのように操作をしても良い)。したがって、次の 2 つを示せば証明が完了する。
- $F = 8$ の場合に $F \gets 9 = 0$ となるような可能な操作が存在する。
- $F = 7$ の場合に $F \gets 6$ となるような可能な操作が存在する。
必要なら $K$ を小さくすることにより $a _ K \geq 1$ と仮定して一般性を失わない。
まず 1. を示す。 $F = 8$ と仮定する。このときまず、奇数 $i$ が存在し $a _ i \geq 1$ となっていると仮定する。この場合 $k = i$ と選べば $a _ i \gets a _ i - 1$ となると $8$ 減るので、確かに $F = 0$ となる。したがって、以下では任意の奇数 $i$ に対し $a _ i = 0$ と仮定して良い。このときまず $K = 0$ はありえない(もしそうなら $1 \leq F = a _ 0 \leq 7$ となるからである)。よって $K \geq 2$ として良い。このとき、 $k = 1$ の操作ができる。この操作で何が起こるのか考える。まず偶数 $1 < l \leq K$ が存在し、 $a _ l \geq 1$ 、かつ、 $1 \leq i \leq l - 1$ に対し $a _ i = 0$ である。まず $a _ l \gets a _ l - 1$ により、 $1$ が減る。しかし、 $1 \leq i \leq l - 1$ に対し $a _ i \gets 7$ により、合計 $2$ 増える。 $l - 1$ も $1$ も奇数であるからである。よって全体では $1$ 増える。つまり $F \gets 9 = 0$ となる。
続けて 2. を同様に示す。 $F = 7$ と仮定する。このときまず、偶数 $i$ が存在し $a _ i \geq 1$ となっていると仮定する。この場合 $k = i$ と選べば $a _ i \gets a _ i - 1$ となると $1$ 減るので、確かに $F = 6$ となる。したがって、以下では任意の偶数 $i$ に対し $a _ i = 0$ と仮定して良い。このとき、 $k = 0$ の操作ができる(できないなら $N = 0$ であるから $F = 0 \in L$ である)。この操作で何が起こるのか考える。まず奇数 $1 \leq l \leq K$ が存在し、 $a _ l \geq 1$ 、かつ、 $0 \leq i \leq l - 1$ に対し $a _ i = 0$ である。まず $a _ l \gets a _ l - 1$ により、 $1$ 増える。しかし、 $0 \leq i \leq l - 1$ に対し $a _ i \gets 7$ により、合計 $2$ 減る。 $l - 1$ も $0$ も偶数であるからである。よって全体では $1$ 減る。つまり $F \gets 6$ となる。
補題 4： $N = F \text{ in } \mathbb{Z} / 9\mathbb{Z}$ が成立する。
証明：(H.1), (H.2) 式と二項定理より、次式の通り示される。
\[
\begin{align}
N &= \sum _ {i = 0} ^ K a _ i (9 - 1) ^ i
= \sum _ {i = 0} ^ K a _ i \left( \sum _ {k = 0} ^ i \begin{pmatrix} k \\ i \end{pmatrix} 9^{i - k} (-1)^k \right) \\
&= \sum _ {i = 0} ^ K (-1)^i a _ i = F \text{ in } \mathbb{Z} / 9\mathbb{Z}.
\end{align}
\]
以下同様。