ABC 225 F — String Cards

考察

選んだカードの順序と選ぶ集合を同時に考えるとN!に広がる。二文字列A,Bの相対順は A+B と B+A の辞書順だけで決められるが、この順にsortした先頭K枚が最適とは限らない。

採用する候補: S_i+S_j≤S_j+S_i の比較で全カードの相対順を固定し、suffixからちょうどj枚選ぶ辞書順最小文字列をDPする。

棄却する候補: 連結比較でsortしたカードの先頭K枚をそのまま連結する。

比較規則は選ばれた二枚の相対順しか保証せず、どのK枚を選ぶべきかは保証しないため公式の反例で失敗する。

連結比較でsortした後、i=Nから逆順に不採用と採用の二遷移を辞書順比較し、ちょうどK枚を選ぶdp[0][K]を答える。

典型の発動条件

連結順序の A+B 比較

発動条件: 複数文字列を並べ替えて連結した結果の辞書順または数値を最小化するとき。

二文字列の隣接順を A+B と B+A で比較し、交換で全体の標準順を作る。

sort後の個数制約付き選択DP

発動条件: sortで選択要素の相対順は固定できるが、選ぶ部分集合自体は最適化する必要があるとき。

suffixと選択枚数を状態にし、現在要素を先頭へ付ける採用遷移と不採用遷移を比較する。

問題固有の要素

連結比較sortは順序だけを決め、選ぶカードまで決めない。また採用時にS_iを前へ付けるため、DPはprefixでなくsuffixから組む。

別の問題へ持ち帰る視点: 貪欲sortが成立しても『相対順の正当化』と『採用集合の正当化』を分離し、後者に別の最適化が要るか確認する。

正当性

比較 A+B≤B+A は隣接交換で全選択カードを標準順へ直せる順序を与え、『好きな順に連結』という自由度を除去する。 dp[i][j]をi以降からj枚選ぶ最小文字列とすれば、S_iを使う場合は必ず先頭へ付くので min(dp[i+1][j], S_i+dp[i+1][j-1]) が成立する。 交換によって任意の選択集合をこの順へ直せる一方、所属選択は独立に残るため、sortで順序を消してDPで集合を選べる。

実装上の注意

  • 不可能状態を実文字列より必ず大きいsentinelで表し、j=0は空文字列とする。比較関数が同値を含む場合もsortの要件を壊さないようにする。

復習の核

  • A+B比較でsortしただけでは先頭K枚を選べない。sortが消した自由度は『順序だけ』だと区別して覚える。

計算量と制約

時間

O(N log N·L+NK²L)、L最大カード長。文字列連結・比較を含む保守的上界。

空間

O(K²L+NL)、rolling DP。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq K \leq N \leq 50; 1 \leq |S_i| \leq 50; S_i consists of lowercase English letters.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

主題
追加で学ぶ技能
    なし
    既習技能
    • 列・subsequence DP: 列の順序を保つ状態と、選ぶ・選ばない遷移を設計できる。

    主タグ: 貪欲法と交換論

    補助タグ: 列・subsequence DP

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

    学習の位置

    体系上の位置: 交換論から選択順を導く

    • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

    先に読む単元:

    • 列・subsequence DP — DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence DPの発動条件・正当化・境界を重複なく学ぶ。

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

    • 対称操作による状態の正規化。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題