yukicoder contest 459 開催記
yukicoder でコンテストを開催しました：yukicoder.me
最近コンテストに出るだけで全然練習していない身ですが、作問は細々と続けていたのでコンテストを開催してみました。今回で 3 回目の yukicoder contest です。
過去回もまだ解いていなければ是非解いてもらえると嬉しいです：
問題について
A. Swing
ブランコのようなイメージで Swing と名付けました。実験（とオーバーフローに対する注意力）が重要な問題です。
B. Contest Coordinator
ABC387への言及を見て思いついた問題です。
$T = 2,\ X \gt Y$ で $(1,3,4,4,10,11,14)$ を選択したときの最適な並び順が $(14, 10, 11, 1, 3, 4, 4)$ になってしまってめちゃくちゃなのでモデリングが妥当ではなさそう。
解法に関しては、一度DPに向かってしまうと軌道修正が苦しいのではないかと思っています。
C. Prefix Removal
二重Σの順序を取り替える操作は主に数え上げを高速化する際によく行うので慣れておくとお得そうです。
個人的には、和を取る領域を二次元平面に描いてあげるとこの取り替えをスムーズに行いやすいです。
D. Make All Divisible
Bで崖を作らないのが大切という話をしておいて大崖を生成して反省。
元々の設定は解説にある言い換え後の問題だったんですが、そうすると最小化の対象が不自然に見えたので問題設定を少し弄って今の形になりました。
「十分大きな値は $k$ だけ減らしても答えが変わらない」の "十分大きな" がどれくらいなのかを正確に見積もるのはやや面倒ですが、実行時間に間に合うギリギリの値を閾値に設定すると間違いなく通ってしまいます。
E. Increasing Sliding Window Minimum
解説にあるように window サイズ $K$ が任意でも同じ計算量で解けるので、ぜひ考えてみてください。$K=2$ が分かればそう難しくないと思います。
元は全て $A _ i = -1$ の設定を考えていましたが、解説にあるように OEIS で簡単にヒットする答えになってしまったので今の設定になりました （全単射の作り方が面白いです）。
F. $((0 \And 1) \mathop{|} 2) \oplus 3$
行列累乗の式を丁寧に計算する方針でも解き得る気がしますが、苦しいと思います。
$1$ に対する遷移が $\begin{pmatrix} 1 & 1 \cr 2 & 2\end{pmatrix}$ という列が等しい行列になっていることに注目できれば解説の方針に合流します。
$0$ が続く部分に関する議論も、$0$ に対する遷移は $(1,0)$ 成分が $0$ の行列 $\begin{pmatrix} 3 & 1 \cr 0 & 2\end{pmatrix}$ で表せることが関係しています。
行列のべき乗の周期を利用した解法は準備時に想定できていませんでした。本当は線形で通して欲しい問題なので制約が甘かったです。
G. Good Modulo
商列挙の方針が初めに浮かぶ人も多そう。経験的に、商列挙で sqrt が付く解法は見方を変えると調和級数の log に落ちることが多い気がします（今回の問題はさらに loglog まで落とせますが）。
$X \log \log X$ を要求したい気持ちにもなりましたが、C++だけでも区別が難しそうで、Python の $X\log\log X$ vs. C++ の $X\log X$ に至っては恐らくどうにもならないので試す前に諦めました。
H. Simple Chicken Game
$3$ 人以上のゲームを考えたくて作った問題です。
問題名はチキンレースですが、本当の元ネタは Blackjack です。ディーラーとの勝負ではなかったり、枚数に制限がなかったりと違いが多く混乱の元になりそうだったので Blackjack という単語を登場させませんでした。
コインを投げても投げなくても順位の期待値が等しい場合の挙動を色々実験していると、今の設定で綺麗な性質が現れたので出題しました。
プレイヤー $i$ のスコアに $-i$ の補正項が入っているのは、後の手番の人は前の人の結果を見られる分だけ有利だからです。ただ、そうすると今度は後の手番の人の方が不利になるらしいです（※未証明）。例えば $N=5$ だと順位の期待値はプレイヤー $1$ から順に $\dfrac{327}{128}, \dfrac{327}{128}, \dfrac{390}{128}, \dfrac{420}{128}, \dfrac{456}{128}$ です。
解法について、解説にあるように最適戦略の証明は煩雑です。実験コードを書いて最適戦略を予想するのが contestant としては正攻法かと思います。特に、今回の場合は実験コードさえ正しく書くことが出来れば最適戦略の予想を立てるのは非常に簡単だと思います。
計算にあまり依存しない直感的な証明がもし出来たら教えてください。
ところで、ボーナスとして書いたように実は線形時間で解けるようで（テスターの rin さんに教えて頂きました）、びっくり。
余談：問題作成について
作問ツールを自作して遊んでいました：https://github.com/suisen-cp/cp-problem-maker
Rime など、有名なツールがあるので自作する意味はあまり無いと思います。
