典型てんこ盛り、地力が問われるいい問題。
問題文は日本語に付き省略。
結果の数え上げ
「操作によって生成されうる結果」が何通りあるか、を求めさせる問題は多い。 本ブログではこのパターンの問題を「結果の数え上げ」と呼ぶことにする。 このタイプの問題に取り組む際の第一歩は、結果にどのような特徴があり得るか必要条件を考えてみることである。
必要条件の列挙
減少列の長さ
まず、結果列の連続した4つの数が減少列であることはありえない。 何故なら減少列は $N$本のうち同じ数列から取る必要があるため（そうでないと、より小さい値が別の数列の頭にあったことになり、操作の条件に矛盾する）。
最大の要素に注目
条件はこれだけだろうか？他にもありそうだ。 数列の最大要素に着目してみる(最大・最小主義)と、例えば $N = 3$ のとき、$9$ が先頭に来ることはない。
$9$ がどこで出現するかを考えると、
- 最後に出現 (長さ3の数列の最後にある)
- 最後から2番目に出現 (〃真ん中にある)
- 最後から3番目に出現 (〃先頭にある)
のどれかしかありえない。これらの場合分けによって結果の数列は異なる。 以降帰納的に考える。数列の最後の方から見て高々長さ $3$ の数列たちに分割していく操作を考えると、その先頭の要素たちは昇順に並んでなければならない。 以降、これらの分割した列を長さに応じて タイプ$1$、タイプ$2$、タイプ$3$ と呼ぶ。
数列の長さと個数
前項で述べた数列への分割だが、その長さと個数の組み合わせに制約がある。 これは問題の設定上、分割したタイプ1〜3の数列たちを長さ $3$ の数列 × $N$ に当てはめる必要性から生じる。 具体的には以下。(★)
- 長さの合計が $3N$ であること
- タイプ $2$ と タイプ $3$ の個数の和が $N$ 以下であること
実装方針
★ の条件を素直に書き下すと次のような動的計画法が思いつく。
dp[i][j] := 最後から $i$ 個の数値が埋まっていて、タイプ $2$ と タイプ $3$ の個数の和が $j$ である。
状態数は $O(N^2)$ となる。
