drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ JOI JOI春合宿 JOI難易度6 AtCoder 各桁ごとに見る アナグラム 文字列 順列の数え上げ 制約条件:総和<=K 辞書順 数え上げ問題 二項係数 どの場所で初めてsmallerになるかを考える NoviSteps2Q 桁DPとは違うけど、桁DP的な発想で解けた ジャッジページへのリンク 問題概要 長さ の文字列 が与えられる。 の各文字を並び替えてできる文字列をすべて考えたとき、 はその中で辞書順で何番目の文字列に相当するのかを求めよ。 制約 の文字はすべて英大文字 考えたこと よりも辞書順で小さい文字列の個数を数え上げて、最後に 1 を足せば OK。 よりも辞書順の小さい文字列は、以下のように捉えることができる。 最初の 文字は と一致する 文字目が よりも小さい (0-indexed) それ以降は自由に並び替えて良い について場合分けして、丁寧に数え上げよう。なお、たとえば 'A' が 文字 'B' が… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F12%2F04%2F020500" title="JOI 春合宿 2007 day3-1 anagram (2Q, 難易度 6) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-12-04 02:05:00 rich https://drken1215.hatenablog.com/entry/2020/12/04/020500 1.0 100%