全国統一プログラミング王決定戦(日経コン)2019 エキシビジョン解説

A:接頭辞たちは、文字列の先頭から何文字か切り出したものなので、辞書順ソートすると接頭辞の長さ順になります。よって、接頭辞配列は{先頭から1文字目まで,先頭から2文字目まで,...,先頭からN文字目まで}を意味する{1,2,...,N}となります。

B:A^2がNを超えない最大のAは二分探索可能です。Nが小さいので1から順にループを回して実験しても高々33400に解を発見できます。

C:Nが小さいのでint型で受け取ってN%11すればよいです。N<=10^{100000}ならchar型で受け取って文字列の指示に従うか、多倍長を使いましょう。

D:Nの範囲が充分大きいので、任意の整数と考えてよいでしょう。辞書順で小さい順からK番目は10^{K-1}です。

K=1のとき明らかに正しく、K=iのとき正しいと仮定するとその次に辞書順で小さい数は後ろに0をひとつつけたものになり、K=i+1の時でも正しいので数学的帰納法より証明も完了しました。

E:forと条件分岐を合成して、問題文に従い実装します。

F:f(x)は、(だいたい)xがコラッツ問題において何手で1になるかを示したものです。一見コラッツ問題を逆から遡らなければならないように見えますが、なんと1000手で終わる入力例があるので、それを1手進めれば999手の解、さらに1手進めれば998手の解…のように導出できます。

G:回文は、偶数文字ある文字種がいくつかと、高々1つの奇数文字ある文字種からなります。(これは回文の性質を考えると軸の有無を考えると分かります)

これを利用して、まず、全ての文字種から偶数文字取り出して長い回文を1つ作り、最後に各文字種について余った0文字か1文字を回文として主張します。

証明は、スコアについて(a+k)(a+k)+(a-k)(a-k)>=2*a^2の不等式を利用して可能です。

H:結論から言うと、このゲームの結果はスタートが(mod 9)で合同なら等しくなります。

というのも、(まずこれを仮定して、)

1≡1

8≡-1

64≡1

512≡-1

4096≡1

...

と、どう操作しても(mod 9)において各人がmod1つ分しか結果をずらせないことがわかります。

ここで、スタートが9以下の結果が"LWLWLWLWW"となることから、(手を逆に戻していくイメージで、)Wはうまくやれば相手をLに誘導できること、Lはどう転んでも相手をWに運んでしまうことがわかるので、(mod 9)において結果が合同であることが示されました。

(もっときれいで厳密な説明や証明があると思いますが思いつかなかったのでこれで許して下さい…)

physics0523's 精進ログ