mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ TopCoder 問題 TopCoder Statistics - Problem Statement同じ長さ L の文字列が n 個与えられる。これを辞書順にソートするのだが, ソートの仕方が少し特殊で, 長さ L の順列 p が与えられて, p[0] 番目の文字, p[1] 番目の文字, ..., p[L-1] 番目の文字, という順番でソートことにする。 順列 p の与え方がランダム(L! 通りある)のとき, 1 番はじめにくる文字が i 番目の文字列である確率はいくらであるか。0 解法 dp[i][s] = (集合 s の中で i が最も先頭に来る確率) とします。答えは, dp[0][2^n - 1]… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F04%2F21%2F192239" title="SRM 542 div1 med: StrangeDictionary2 - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-04-21 19:22:39 rich https://mayokoex.hatenablog.com/entry/2016/04/21/192239 1.0 100%