ABC 234 F — Reordering

考察

部分列を最後に自由に並べ替えるため、元の位置や選択順は消え、各文字を何個使うかだけが生成可能性を決める。

使用個数 c_a,…,c_z を固定すると、得られる相異なる文字列数は総文字数の順列を同一文字の入替えで割った多項係数になる。

棄却する候補: 元文字列の全ての部分列を列挙し、それぞれの全順列を集合へ入れて重複排除する。

位置選択と並べ替えの両方が指数・階乗規模で、同じ文字列の重複も非常に多い。

採用する候補: 文字種を一つずつ処理し、使用済み総長 j の文字列へ新文字を k 個挿入する位置 C(j+k,k) を掛ける DP を行う。

同じ新文字 k 個は区別せず、既存文字列との相対順を保った挿入位置だけで各完成文字列を一度数えられる。

文字種ごとの頻度上限だけを残すことで、長さ最大 5000 の位置情報を「処理済み文字種と総使用数」の二状態へ圧縮する。

部分列選択を文字頻度ベクトルへ商約し、各文字種の同一要素を既存列へ挿入する二項係数遷移で全長の multiset permutation 数を DP する。

典型の発動条件

頻度制約付き multiset permutation DP

発動条件: 元集合から種類別上限以内を選び、選んだ同種要素を区別せず全順列を数えるとき。

種類を順に追加し、新種類 k 個の配置場所を完成長に対する二項係数で選ぶ。

問題固有の要素

新文字を k 個追加する際、既存文字の相対順を固定して新文字の位置だけ選ぶと C(j+k,k) 通りになり、文字列を一意に分解できる。

別の問題へ持ち帰る視点: 同一要素の追加では factorial 公式を直接全頻度へ適用せず、既存構造へ同一要素を挿入する組合せで逐次 DP にできる。

正当性

使う各文字数を固定すると元の位置は生成文字列に影響しない。同じ文字をk個追加する際、既存長jの列へ入れる位置集合はC(j+k,k)通りで、削除すれば元の列へ一意に戻る。文字種を順に処理するDPは各頻度ベクトルとその並べ方を一度ずつ生成する。最後に空列を除く。

実装上の注意

  • 各文字の k は 0 からその頻度まで、既存長との合計が |S| 以下の範囲だけ遷移する。
  • dp[0]=1 は遷移用の空文字列として保持するが、最終答案では長さ 1 以上の係数だけを合計する。

復習の核

  • 選択後に自由な並べ替えがあるなら、元位置の情報が消えて種類別個数だけが残ることを最初に確認する。
  • 同じ文字 k 個の追加は区別せず、完成列のどの k 位置を新文字にするかという二項係数で数える。

計算量と制約

時間

O(|S|²)、文字種数26は定数。

空間

O(|S|)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: S is a string of length 1 and 5000 (inclusive) consisting of lowercase English letters.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Reordering の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 組合せ係数と対称性で数える

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 組合せ係数・数え上げ

    補助タグ: 法上の四則演算・高速累乗・逆元

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 組合せ係数と対称性で数える

    • 選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。

    先に読む単元:

    この解説で扱わないこと:

    • 重なりを交互加減する包除・Möbius反転。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題