drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ HUPC 順列を題材とした問題 順列テク:巡回群の直積と見る 考察：操作・条件・目的関数を言い換える DP 個数重複も考慮したナップサックDP シーケンシャルDP Yes/No判定問題 部分和 数量が小さいことの活用：総和がNになる整数列の種類数はO(√N) 順列テク:順列は互換(swap操作)の積として表せる これ好き！！！ 問題へのリンク editorial 問題概要 の順列が与えられる。これらの順列のうち、 個を赤く塗り、 個を青く塗る方法であって、次の条件を満たすようにするものは存在するか、判定せよ。 赤い要素同士を swap することを好きな順序で好きな回数だけ繰り返し 青い要素同士を swap することを好きな順序で好きな回数だけ繰り返すことで 順列全体がソートされた状態にすることができる 制約 考えたこと つまり、 赤く塗った要素の index (1-indexed) の集合 赤く塗った要素の集合 が一致するようにできるかどうかを問う問題となっている。具体的に様子を掴んでみる。たとえば … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F10%2F15%2F012800" title="AOJ 2955 Two Colors Sort (HUPC 2019 day2-D) - けんちょんの競プロ精進記録" 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-10-15 01:28:00 rich https://drken1215.hatenablog.com/entry/2020/10/15/012800 1.0 100%