World Tour Finals 2019 Open Contest
Updated:
World Tour Finals 2019 Open Contest
Source codes
Solutions
A - Magic
まず、マジシャンの最適戦略は、すぬけ君が、財宝の入っている箱を開ける直前に、手品を使って他の箱に移動させることである。それ以外に手品を使うメリットはない。どこに移動させるか？ 少なくとも、箱を開けることのできない、つまり $a _ i = 0$ となった箱が存在する場合、そこに移動させればすぬけ君の敗北が決定する。
次にすぬけ君の戦略を考える。すぬけ君はマジシャンに手品を確実に使わせて、確実に使わせたタイミングで $K$ を減らす。そして $K = -1$ になった瞬間に勝利が確定する。 $K = -1$ になったならば、完了形の意味で、その過程でどこかで財宝を見つけていないとおかしいからである。そしてすぬけ君が $K$ を確実に減らすための唯一の方法は、 全ての箱を $1$ 回ずつ開封すること である。するとマジシャンはどこかのタイミングで財宝を $1$ 回は移動させる必要がある。ここまでをまとめると、以下の通りである。
- マジシャンの勝利条件：すぬけ君に箱を開けさせて $a _ i = 0$ となる箱を作らせそこに財宝を移動する。
- すぬけ君の勝利条件：すぬけ君が全ての箱をチェックすることで、 $K$ を減らさせ、 $K = -1$ を達成させる。
ここで 「全ての箱を 1 回ずつ開封する」一連の動作をする際に、最後に開けた箱が極めて重要である 。この瞬間にマジシャンは、残りの $N - 1$ 個の箱のどこかに財宝を隠すはずである。もちろんその中に $a _ i = 0$ の箱があった場合、マジシャンの勝利が確定する。そしてすぬけ君は、その $N - 1$ 個の箱を全てチェックすることで、さらにまた $K$ をまた減らすことができる。つまり、「一連の動作」は、 1 回目と、 2 回目以降は違うのである。
ゆえに、 一連の動作で最後に開ける箱は、すぬけ君にとって、マジシャンに財宝を隠して欲しくない箱であるべきである。すなわち、 $a _ i$ が最小の箱であるべきである 。これがすぬけ君の最適戦略である。これを繰り返す。その過程で、 $K = -1$ までたどり着ければすぬけ君の勝ち、そうでなければ負けである。
ポイント
幸いにして、私は 1h 程度で自力で解答にたどり着いた。この問題を AC したら 0 時を回っていたので、睡眠薬を飲んだ。そのあとこれを書いてある(寝て起きた後に commit して push しましたのでコンテスト中に upload していません)。
この問題だけは、私は理解し、解けた。しかし普通のコンテストと違っていた。 ヒントとなる定跡が全くない ように思う。よくある grundy 数とか、不変量を作るとか、必要条件を列挙していくと十分条件だったとか、全く関係ない。素早く AC した人の色を見てもバラバラである。私は 600 点くらいの問題かなと思ったけど、人によっては 1000 点以上に感じたかもしれない。 地頭勝負の問題 である。これだけ見ても、もはや、異次元のコンテストである。
このコンテストは、プログラミングコンテストであるかもしれないけど、普通のプログラミングコンテストではない。 定跡を頼りにそれらを高速に適用していくコンテストではないことがこれだけ見てもわかる。
B - Multiple of Nine
ポイント
C1 - Triangular Lamps Easy
ポイント
C2 - Triangular Lamps Hard
ポイント
D - Distinct Boxes
ポイント
E - e
解答の方針
まず入力例 1 の内容を rng さんの解説から学ぶ必要がある。何よりまず、
ある文字 $S[i]$ が
Xであるための必要十分条件は、確率変数の列 $\{ X _ j \} _ {j = -\infty} ^ \infty$ を定めた際に $X _ i$ から見て左右それぞれ最長減少列が偶数個でできていることである。-はその排反。
が基本的な理解となる。以下入力例 1 の計算が続くが、テイラー展開が出てくるので大学 1 年生程度の数学の知識が必要である。この計算例を元に戦略を立てると、
- 左から順に見ていくのだが、 $X _ 0$ を設定した段階で左を見たとき最長減少列の偶奇の確率がそれぞれ $e^{-x}$, $1 - e^{-x}$ である。
- 文字列の中身について、 DP で遷移していく。
- $X _ {N - 1}$ を検討し終えた段階で、右を見たとき、またそれと独立に最長減少列の偶奇の確率がそれぞれ $e^{-x}$, $1 - e^{-x}$ となっている。
- DP の結果とこれらを適宜掛け合わせて $[0, 1]$ 区間上で積分すると答えが求まる。
ということになる。
DP の詳細
以下 DP で答えを出すのだが、 rng さんの解説と同様の方針をとる。 $[0, 1]$-valued の確率変数 $X _ j$ の変数を小さい方から順に決めていき、 $\{ X _ j \} _ {j = -\infty} ^ i$ の情報を今後必要な分だけ保持したい。その情報は、以下の通りである。
- 添字 $i$ 。
- $X _ i$ から左を見たときの最長減少列の偶奇。
- 文字列 $S[0, i]$ を生成するための「条件付き確率」(後述)。
- $X _ i$ から右を見たときの最長減少列が偶数/奇数の際に、それぞれ文字列 $S[0, i]$ が実際生成されるか否か。
そこで条件付き確率を $x = X _ i$ の関数としてとる DP をする。正確に言えば、
$DP[i][j][k][l] = $ 確率変数 $\{ X _ i \} _ {j = -\infty}^i$ を定めた際に、$X _ i$ から左を見たときの最長減少列の偶奇が $j$ であり (even なら $0$, odd なら $1$) 、かつ、文字列 $S[0, i]$ が生成される確率。ただし、これの生成には $X _ i$ から右を見たときの最長減少列が even/odd であるかにも依存する。 $k = 1$ の時は even を仮定した際に生成することを意味し、 $l = 1$ の際は odd を仮定した際に生成することを意味する。
つまり興味があるのは $DP[i][j][0][1]$, $DP[i][j][1][0]$, $DP[i][j][1][1]$ である。そしてこれらは $[0, 1]$ を定義域とし、条件付き確率を返す 関数 であり、遷移の際に 積分 が必要であるので、 $DP[i][j][k][l] (x)$ などと変数を表記する。
初期条件は以下の通り。
S[0] == 'X'の場合は、 $DP[0][0][1][0] (x) = e^{-x}$, $DP[i][j][k][l] (x) = 0$ (otherwise).S[0] == '-'の場合は、 $DP[0][0][0][1] (x) = e^{-x}$, $DP[0][1][1][1] (x) = 1 - e^{-x}$, $DP[i][j][k][l] (x) = 0$ (otherwise).
遷移は以下の通り。以下表記の煩雑さを避けるため、 $0$ と $1$ の和をとる場合は $[0/1]$ のように表記するものとする。積分には線形性があるので、和を取ってから積分しても、積分してから和をとってもよい。左・右の最小減少列を「左」「右」と略記するものとする。
S[i] == 'X'のとき： 左右共に偶数でないといけないから $DP[i][0][1][0]$ のみが計算の対象となる。- $X _ {i - 1} < X _ i$ のとき： $X _ i$ から見て左は even でなくてはならないので $X _ {i - 1}$ からみて左は odd でなくてはならない。 $X _ {i - 1}$ から見て右は自動的に even になっている。よって次式で遷移が書ける。 \[ DP[i][0][1][0] \mathbin{ {+} {=} } \int _ 0 ^x DP[i - 1][1][1][0/1] (y) dy. \]
- $X _ {i - 1} > X _ i$ のとき： $X _ i$ から見て左は自動的に even になっている。 $X _ {i - 1}$ から見て左はどちらでも良い。一方で $X _ i$ から見て右は even でなくてはならないため、 $X _ {i - 1}$ から見て右は odd になっている必要がある。よって次式で遷移が書ける。 \[ DP[i][0][1][0] \mathbin{ {+} {=} } \int _ x ^ 1 DP[i - 1][0/1][0/1][1] (y) dy. \]
S[i] == '-'のとき： 左右のどちらかの最小減少列は奇数でないといけないから $DP[i][0][0][1]$ と $DP[i][1][1][1]$ のみが計算の対象となる。- $X _ {i - 1} < X _ i$ のとき： $2$ パターンに分かれる。
- $X _ i$ から見て左が odd ならば、 $X _ {i - 1}$ から見て左は even である。 $X _ i$ の右は even, odd どちらでも良い。ただし $X _ {i - 1}$ から見て右は自動的に even になる。よって次式で遷移が書ける。 \[ DP[i][1][1][1] (x) \mathbin{ {+} {=} } \int _ 0 ^ x DP[i - 1][0][1][0/1] (y) dy. \]
- $X _ i$ から見て左が even ならば、 $X _ {i - 1}$ から見て左は odd である。 $X _ i$ の右は odd である必要がある。やはり $X _ {i - 1}$ から見て右は自動的に even になる。よって次式で遷移が書ける。 \[ DP[i][0][0][1] (x) \mathbin{ {+} {=} } \int _ 0 ^ x DP[i - 1][1][1][0/1] (y) dy. \]
- $X _ {i - 1} > X _ i$ のとき： $X _ i$ から見て左は even である。よって右は odd でなくてはならない。したがって$X _ {i - 1}$ から見て右は even でなくてはならない。一方で $X _ {i - 1}$ から見て左はどちらでも良い。よって次式で遷移が書ける。 \[ DP[i][0][0][1] (x) \mathbin{ {+} {=} } \int _ x ^ 1 DP[i - 1][0/1][1][0/1] (y) dy. \]
- $X _ {i - 1} < X _ i$ のとき： $2$ パターンに分かれる。
最終的な答えは、 $DP[N - 1][0/1][k][l]$ を用いて表記される。 $k = l = 1$ のときは $X _ {N - 1}$ の右は odd, even どちらでも良いから確率 $1$ をかけて積分する。 $k = 1$, $l = 0$ の場合は $X _ {N - 1}$ の右は even でなくてはならないから確率 $e^{-x}$ をかけて積分する。 $k = 0$, $l = 1$ の場合は $X _ {N - 1}$ の右は odd でなくてはならないから確率 $1 - e^{-x}$ をかけて積分する。したがって答えは、以下の通りである。
\[
\begin{align}
A =& \int _ 0 ^ 1 DP[N - 1][0/1][1][1] (x) dx \\
&+ \int _ 0 ^ 1 DP[N - 1][0/1][1][0] (x) e ^ {-x} dx \\
&+ \int _ 0 ^ 1 DP[N - 1][0/1][0][1] (x) (1 - e ^ {-x}) dx. \tag{E.1}
\end{align}
\]
実装について
さて計算機上で上記の計算を行うのは計画性が必要である。幸いなことに rng さんも指摘している通り、
\[
DP[i][j][k][l] (x) = \sum _ {\alpha = 0} ^ K a _ \alpha x ^ \alpha + e^{-1} \sum _ {\beta = 0} ^ L b _ \beta x ^ \beta + c e^{-x}
\]
の形を必ずしているので、 typedef vector<ll> Poly; としてその上に多項式演算を実装して、 typedef tuple<Poly, Poly, ll> Func; で三つ組 $(\{ a _ \alpha \}, \{ b _ \beta \}, c)$ で式を管理すれば良い。 $N \leq 1000$ で $4$ sec もあるので、安直な実装で問題はない。
遷移の部分の積分は高校レベルであるので省略する。各自試みられたい。
問題は (E.1) 式の積分である。ここは $P + Qe^{-1} + Re^{-2}$ (ただし $P, Q, R \in \mathbb{Z}/(10 ^ 9 + 7) \mathbb{Z}$) の形で結果が返ってくるから、要するに typedef tuple<ll, ll, ll> Flush; とした時に Flush integral(Func f) および Flush integral_e(Func f) を定義して $[0, 1]$ 区間を積分すればよろしい。ただし後者は $f$ に $e^{-x}$ をかけた積分である。前者の積分はすぐに $(P, Q, 0)$ の形で積分が求まるが、後者は次の積分を計算する必要がある。
\[
I _ i = \int _ 0 ^ 1 x ^ i e ^ {-x} dx \ \ \ (i \in \mathbb{N}).
\]
この不定積分は簡単ではない。読者はプロコンが好きでやっているはずで、積分が好きかどうかは人によるだろう。こんな積分計算なんてしたくないよというかもしれない。大抵大学入試問題では漸化式を用いて導出するところであるが、私が簡単だと思う導出方法を書いておく。出典を忘れました。初等的だし、多分有名だと思うからいいでしょう。
まず $\lvert t \rvert < 1$ (複素数と思ってもいいし実数と思ってもいい) に対し、
\[
I = \int _ 0 ^ 1 e^{tx} e^{-x} dx
\]
と定める。すると積分ののちに $t$ のべき無限和に直すと、次式が得られる1。
\[
\begin{align}
I &= \int _ 0 ^ 1 e^{(t - 1) x} dx = \left[ \frac{1}{t - 1} e^{(t - 1)x} \right] _ 0 ^ 1 = \frac{1 - e^{t - 1}}{1 - t} \\
&= \sum _ {i = 0} ^ \infty (1 - e ^ {t - 1}) t ^ i
= \sum _ {i = 0} ^ \infty \left( 1 - e^{-1} \sum _ {j = 0} ^ \infty \frac{1}{j !} t ^ j \right) t ^ i \\
&= \sum _ {i = 0} ^ \infty \left( 1 - e^{-1} \sum _ {j = 0} ^ i \frac{1}{j !} \right) t^i.
\end{align}
\]
一方で、テイラー展開(というか $\exp$ の定義)により、次式が得られる2。
\[
I = \sum _ {i = 0} ^ \infty \frac{t ^ i}{i !} \int _ 0 ^ 1 x ^ i e ^ {-x} dx.
\]
テイラー展開の一意性により、次式が成立する。
\[
\begin{align}
& & \frac{1}{i !} \int _ 0 ^ 1 x ^ i e ^ {-x} dx &= 1 - e^{-1} \sum _ {j = 0} ^ i \frac{1}{j !}, \\
\text{i.e.,} & & I _ i &= \left( i ! \right) + e^{-1} \left( - i ! \sum _ {j = 0} ^ i \frac{1}{j !} \right).
\end{align}
\]
以上を実装すれば、答えが得られる。
ポイント
E を見ていると、クラクラすると同時に、 思わず涙が出そうになるくらい感動した 。こんなに高度なレベルで数学と計算機の基礎事項が綺麗に融合している、それが 4h で解ける可能性は、人類にきちんとあったんだとわかると、本当にプログラミングコンテストって、すごい営みだなって思います。
Others
A - sample: 2, tle: 2.000, time: 59:48, from_submit: 00:00
B - sample: 3, tle: 4.000, time: 00:00
C1 - sample: 1, tle: 2.000, time: 00:00
C2 - sample: 1, tle: 4.000, time: 00:00
D - sample: 1, tle: 2.000, time: 00:00
E - sample: 6, tle: 4.000, time: 00:00
コンテスト名に (注: 異常な難易度です) と書いてあるほど難しい問題であったが、かろうじて A だけは AC できた。これすらそもそも定跡がない問題で、自分の頭を絞って考えるしかない。そうとしか振り返ることができない。
AGC は神々の戦いであるし、今後も私は一生見学状態でしょう。しかしそれでも、コンテスタントの最先端、最高レベルって、すごいと思います。この問題たち (といっても A と E しかわからないんですが) を作った rng_58 さんのことを心から尊敬します。磨きに磨き切った問題を出せるにも関わらず、その一方でいつも ABC/ARC で典型問題をおろそかにせず私たちに向けて丁寧に解説なさることに頭が下がります。
rng さんに於かれましては、これからも自分の能力を最大限発揮してくださり、私たちにプロコンのあるべき姿を教えてくださるものと信じております。