mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ AOJ 問題 Rabbit Game Playing | Aizu Online Judge数列 D が与えられる。これに関して, 以下の条件を満たす並べ方は何通りあるか求めよ。 条件: 任意の i について, D[i] 解法 挿入DP というやつ？dp[i] = (i 番目までの並べ方の場合の数) というのが分かっているとき, i+1 番目の数を入れられるところは, 今までの並べ方に関係なく決まります(直後の数との差が T 以下なら大丈夫)。よって, i+1 番目の数を挿入できるところは i+1 - (D[i+1]-T 以上の要素の数) + 1 となるのですが, これは D をソートしておくと高速に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F06%2F25%2F114813" title="AOJ 2383 Rabbit Game Playing - 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-06-25 11:48:13 rich https://mayokoex.hatenablog.com/entry/2016/06/25/114813 1.0 100%