drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ HackerRank 数え上げ問題 順列を題材とした問題 順列の数え上げ 中央値(メディアン)に関する問題 Greedy：先に進むほど新たな選択肢が挿入される 各地点について自由度を掛け算していく 後ろから見たらわかった 問題へのリンク 問題概要 の順列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 任意の 以下の奇数 に対して、 のメディアンは である 制約 考えたこと 簡単のため、 を奇数として考えてみる。このとき、まず最後尾の値が一意に決まってしまうことに注意しよう。 たとえば であったならば、最後の要素はかならず 3 になる。よって残りの を並び替える問題になる。ここで注意したいことは、 最後から 2 番目の要素としてどれを選んだとしても、残りの 3 つの数の並べる場合の数は変わらない ということだ。よって、最後から 2 番目の要素は … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F02%2F29%2F195100" title="フォルシアゆるふわ競プロオンサイト #3 B - Median Permutation locked - けんちょんの競プロ精進記録" 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 2020-02-29 19:51:00 rich https://drken1215.hatenablog.com/entry/2020/02/29/195100 1.0 100%