Xmas Contest 2020 - hos.lyric's blog

Xmas Contest 2020 にご参加いただいた皆様，どうもありがとうございました！

大変遅くなりましたが解説記事が準備できました．略解を AtCoder 上に載せて一息ついたのもあって 2019 よりもさらに遅くなってしまいました……．その分濃い情報を提供できているつもりなのでお許しください．

今回は，どうやら難易度がかなり高めだったようです．maroon さんはわたしの問題を (実装込みで) かなりの速度で解いていっていたので，ちょっと難しめだけど大丈夫かなと思っていました……．また例年にも増して海外の方が多く参加していただき (日本語問題文しかないのに) ありがたい限りです．ちなみにわたしも最近中国語のコンテストにたまに出ています．

わたしが原案を出した問題の解説はこちらです．

それ以外の問題との対戦結果は以下になります．こちらも解法ネタバレを含みます．

A: Additive-Subtractive Stamps

ビジュアライザ開発段階で試しでちょっと触る→手作業は難しそうだな～と思う→実際のデータができて「プログラム書いて出力，目で見てちまちま修正」の方針で 1 時間半ほどで AC，でした．

f:id:hos-lyric:20210113004024p:plain

方針は，まず背景の長方形を引き算を使って正確に塗り分け (正確と言いつつ横方向 1 ピクセル分さぼりました)，文字やうさぎの部分に引き算を連打するのを大きいスタンプから順に適当にやりました．回数制限が意外ときつかったです．

完全手動で正解した方や本当にぴったり塗り分けた方がいらして感動でした．

E: Eternal Dice

最初に見せられたときは $A = 1$ で， $\pi$ の $n$ 次未満と言われていませんでした．ひとまず素直に計算すると $\sum_{2=i_1\lt\cdots\lt i_N} \frac{1}{i_1^2 - 1} \cdots \frac{1}{i_N^2 - 1}$ みたいなものが求められればいいなあとなって，これは $i_1, \ldots, i_N$ が相異なるとだけして $N!$ で割ればよく，よくある包除でできる (集合の分割がなす poset での Möbius 反転)， $\sum_i \left(\frac{1}{i^2 - 1}\right)^j$ みたいなのは部分分数分解を丁寧にやるとかで求まる (留数定理を使うのもあるらしい)，ということで $N$ の多項式時間なら解けたというところで止まりました．後ほど交渉して 10 点を置いてもらいました．

その後三角関数の無限積の式を使うと言われ (この式の存在は記憶の彼方でした)，しかし $\sin(\pi (1 - \sqrt{1+t}))$ など想定と違うものを考えてしまった結果解けず，結局立式を聞いて各 $N$ での多項式を並べた表を見てエスパーできるか確認する仕事をしました (エスパーできました)．ところで解説の「この解説では厳密性を気にしません．」は定数項が $0$ でないものを代入したりしているところにあるのですが， $\sin$ の収束半径が無限大だとかそういうところから正当化できます (面倒)．

すると $A \gt 1$ が解けたと言われ， $A = 1$ を OEIS しろというヒントをもとに何日も考えました．結果的には， $\left. \left(\frac{d}{dx}\right)^N \left(\frac{\sin\sqrt{x}}{\sqrt{x}}\right)^A \right|_{x=\pi^2}$ を求めようとなり， $A = 1$ の結果から辿り着いた OEIS の $\frac{1}{x} \frac{d}{dx}$ の累乗の展開式が使えそうと思い，求めたいものが $\left. \left(\frac{1}{x} \frac{d}{dx}\right)^N \left(\frac{\sin x}{x}\right)^A \right|_{x=\pi}$ とだいたい同じなことに気づくと，必要になる $\left(\frac{\sin x}{x}\right)^A$ の高階微分をぐっと眺めて OEIS を駆使してエスパーしました．エスパー結果だけ書いておくと，

$\begin{align} \left. \left(\frac{d}{dx}\right)^n \left(\frac{\sin x}{x}\right)^A \right|_{x=\pi} = \sum_{A+2j\le n} \left((A+2j)! [x^{A+2j}] (\sinh x)^A\right) \frac{(-1)^{n-j} n!}{(A+2j)!} \binom{n-1-2j}{A-1} \pi^{2j} \end{align}$

です．大変でした……．これであとは畳み込むと解けます．

maroon さんの解法とは違いましたが使う道具はほとんど同じになりました．なお解説の「これは頑張ると証明できます．」というのは帰納法をがんばるということです．

当然正解者 0 人を予想しました．見た目のインパクトがすごい上にやってみると非自明な数列をいくつも観察することになるのでそれはそれはすごかったです．

F: Famous in Russia

AGC048 や AGC049 でも出題された，最適化問題の答えを数え上げるシリーズです．問題設定 (ロシアで既出) は実話だそうですが，わたしには最初から数え上げの形で提案されました．

まず最適化を考えると， $B_i$ の降順に料理を作るのはよくある議論で分かって，しかし各 $k$ について答えで二分探索してそれぞれ $O(N^2)$ の DP ということになってしまってここでしばらく詰まりました．その後日が経ってから，後ろから見ると答えの決め打ちが消せることに気づき無事合計 $O(N^2)$ がわかりました (ここがすぐわからなかったのは大反省です)．DP テーブルを眺めて凸性とかないかなと考えていましたが，最適化パートは降参しました．

解説の「詳細は省きますが，ここで考察を行うと，」の部分ですが，これはわたしの maroon さんの「調理は連続して $A_i$ 時間じゃなくて， $1$ 単位時間ずつやっても結果が変わらない」という説明でぴんときました (これでわかる人も多いかなと思って書いておきます)．

で，数え上げなわけですが，これも 1 週間ほど唸ってできました．各 $A_i$ が答えにどのくらい寄与するか，みたいに考えてしまうとはずれで， $A_i$ を決めるだけでなく料理を作るかどうかまで決めたものを数えればよいというところが難しいですね．数え方さえわかってしまえば，priority queue の状態をシミュレートするのに必要なものを挙げていくとちゃんと多項式時間の DP ができます．

まさかこんなきれいな貪欲で解けるなんて思いませんでした．そして数え上げにも非自明なポイントがあって，とても面白い問題だなと思います．実際ロシア既出がなければ rated なコンテストに送られていたようです．正解者は出ないかなと思いつつ，超強い人がやってくれないかなと淡い期待を抱いていましたが，やっぱり出ませんでした．