mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ CodeForces 問題 codeforces.com 解法 dp[k][i] = (数列 a をつなげた個数が k 個で, 末尾の添字が i となるような場合の数) とします。これがわかれば, 数列が k 個つないでいるようなものが大体 p = L/N - k 個あるのでそれを数えて dp[k][i] * p の和を取っていけば良いです。ということで, dp[k][i] を求めます。 dp[k][i] は, a[j] k-1][j] の和になるので, これの値を cnt[] として求めます。これは, a[i] の lower_bound を計算しておけば(この lower_bound の値を a[i] として保… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2015%2F10%2F17%2F133035" title="Codeforces Round #326 (Div. 1) B. Duff in Beach - 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 2015-10-17 13:30:35 rich https://mayokoex.hatenablog.com/entry/2015/10/17/133035 1.0 100%