ABC 267 G — Increasing K Times

考察

要素は同値でも添字で区別されるので、値の非減少順に固定した順序で一要素ずつ最終列のgapへ挿入すると各permutationを一意に構成できる。

両端へ0 sentinelを置くと、最終列の元のstrict ascent K個に加えて左sentinelから先頭へのascentが必ず一つあり、管理目標はK+1になる。

棄却する候補: N!個の添字permutationを列挙して隣接するA値を比較する。

N=5000でpermutation列挙は不可能である。

採用する候補: 値の小さい順に挿入し、dp[n][m]をn要素挿入後のascent数mの方法数として、ascentが増えるgap数と増えないgap数で遷移する。

新値xは既存値以上なので、gapの局所比較だけでascent変化が0か1か決まり、その候補数はmと同値既挿入数から求まる。

n要素挿入済み、ascent数m、既に挿入したxと同値の要素数cなら、ascentを一つ増やすgapは n+1−m−c 個である。

残る m+c 個のgapではascent数が変わらないので、newdp[m]+=dp[m](m+c)、newdp[m+1]+=dp[m](n+1−m−c) と遷移する。

Eulerian-number型のgap insertion DPをmultiset-like equal valuesへ拡張し、strict ascentを作れないequal-left gapsの補正を加える。

典型の発動条件

昇順挿入によるascent数DP

発動条件: permutationの隣接大小関係数を数え、要素を大小順に追加すると局所変化が単純になるとき。

現在のascent数を状態にし、新最大要素を各gapへ入れたときの増分別に候補数を掛ける。

sentinelによる端点統一

発動条件: 列の先頭・末尾gapを内部gapと同じ挿入規則で扱いたいとき。

値域外または最小のdummyを両端に置き、端点比較を通常の隣接比較へ含める。

問題固有の要素

既存左値が新値xと等しい下降・等値gapへ挿入しても左比較がstrict ascentにならないため、同値既挿入数cを増加gapから引く。

別の問題へ持ち帰る視点: distinct値向けEulerian recurrenceを重複値へ拡張するときは、strict比較が成立しないequal boundaryを数える。

正当性

値順に固定したラベル順でgapへ挿入すると各最終順列から最大処理要素を順に削除できるので構成は一意。sentinel込みascent mのうち増えないgapはm+c、増えるgapはn+1−m−c。既存ascentの置換と同値左隣gapを分けたこの分類は全gapを覆うため、DPが正しい分布を生成し最終K+1を取れば元のstrict ascent Kになる。

実装上の注意

  • Aを値順にsortし、同じ値group内で何個処理済みかをcとして一要素ごとに増やす。
  • 初期列(0,0)はascent0の一通りで、最終的にdp[K+1]を答えとする。

復習の核

  • permutationの局所比較統計は、値順に要素を挿入したとき一つのgapがどう変わるかで数える。
  • 重複値がある場合、distinct版の候補gap数からstrict不等号を失う同値境界を明示的に除く。

計算量と制約

時間

O(N²)(目標Kで打切ればO(NK))とsort O(N log N)。

空間

O(N)、打切りO(K)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 5000; 0 \leq K \leq N - 1; 1 \leq A_i \leq N \, (1 \leq i \leq N); All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Increasing K Times の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題