今日解いた競プロの問題。

第6回ドワンゴからの挑戦状予選-B: 主客転倒を使うのはいいが、各区間が何回数えられるかをどう効率的に計算するのかが分からなかった。小さいnで愚直に計算することはできたので、OEISで検索してみたらA000254というのがそれっぽかったので実装したらACした。なんかスターリング数とかいうやつらしい。

カタラン数とか今回のスターリング数とか、ARCの上のランクの問題を安定的に解こうと思ったらちゃんと勉強しなければならないのかなあと思うが、本質的な考察力さえあれば良くて数学的背景に対する知識はそこまで重要ではないのかなあとも思う。

一度ACした後、改めてよく考えたらシンプルな考え方で解けた。あるスライム$i$が区間$x_{j+1}-x_j$を通る確率を考える。これが起きるのはスライム$i+1,i+2,…j$の全てよりも遅くスライムiが選択された場合である。

スライム$i$～$j$の$j-i+1$匹のスライムが選ばれる順番は$(j-i+1)!$通りであり、各スライムの立場が対等であることからこれらは同確率で起きる。この内、スライム$i$が最も遅く選ばれる場合の数は$!(j-i)$であり、確率は$1/(j-i+1)$である。

区間$x_{j+1}-x_j$がカウントされる回数の期待値はこの確率をスライム$i\ (i\leq j)$について足した総和である。これは$1/1+1/2+1/3+…$であり、良い感じに計算すれば普通に$O(N)$で解ける。

---

今日摂取したコンテンツ。

設計回りの話はそこまで詳しくないので、こういうキャッチーな奴でも割とたすかる。

---

実験のレポートが今回こそちゃんと期限までに提出出来て嬉しい。いつもいつも提出がギリギリになり、納得のいかないクオリティのものを出せたり出せなかったりしている。今回は一応ある程度納得のいくものを余裕をもって出せた。余裕をもってと言っても数時間とかそんなんだが。

結局徹夜にはなってしまった。どうしたものか。とりあえず今回は一応成功経験みたいな感じになったので、次回はこれを改善していく感じの心意気で行きたい。