ARC #068-F : Solitaire - 問題解決の宝石箱

日本語につき問題文は略。

atcoder.jp

比較的理解が容易*1な解法を紹介する。

求める数列の条件

最初のステップ

すぬけくんは 1,2,3,…,N が書かれたカードをこの順に、それぞれデックの先頭あるいは末尾に挿入します。

これで生成される数列はどんな性質を満たすか考えよう。1 をデックに入れ、2〜N までを順番に左or右に入れるので、単調減少する列と単調増加する列が組み合わさった形になる。

f:id:hama_DU:20170208233910p:plain

これを踏まえ、

次のステップ

その後、すぬけくんはデックの先頭あるいは末尾からカードを取り出して食べる、という操作を N 回行います。食べたカードに書かれていた数を食べた順番に並べて数列を作ることにします。

最終的にできる数列が満たすべき条件を考えよう。

現在デックにある数列の左右から合計 k-1 個を取って、その後 1 を並べなければならない。すると左右どちらかは 1 の隣まで取りきる必要があると分かる。以降の説明では、 1 より左の数をすべて取りきった、とする。

f:id:hama_DU:20170208234443p:plain

このとき、先頭からk-1個の数列は、以下の条件を満たすことが分かる。

(条件1) 単調減少する数列が 2 つ組み合わさった形
(条件2) 1より右に残った数(:= 白い数)の最大値が、1を含まない方の減少列(:= 青い数) の最小値より大きい

ここまでは解説動画の通り。以下、端折られている部分を解説する。

左パート: k-1個

まず (条件2) を無視した簡単なバージョンの問題を解こう。

1〜Nの順列の中で、高々2つの減少列に分割できるもの（以降、このような数列を「よい数列」と呼ぶ。）は何通りあるだろうか。

以下の操作を幾つか繰り返してよい数列を作ろう。

現在考えている数を x とおく。x の初期値は N 。
(1)、(2)、(3) の中から1 つ選んで操作を行う。
ただし (2) を選んだ直後に (3) を選んではいけない。

(1) x を数列の末尾に追加する。x を1つ減らす。
(2) x を保留中の数に追加する。x を1つ減らす。
(3) 保留中の数があるなら、最大のものを取り数列の末尾に追加する。

x が 0 になり、保留中の数が無くなったら操作を終了する。

操作とその結果の数列は、以下の性質を満たす。

(a) 操作によってできた数列はよい数列である。
(b) 任意のよい数列は、ある操作列から作られる。
(c) 操作列が異なると、できあがる数列は異なる。

証明

(a) 数がどの操作によって追加されたかで色分けをする。
(1) で追加される数は N から操作をするごとに減るので、単調減少する。
(3) で追加される数は保留中の数の最大値から順に取り出すので、単調減少する。
したがって、同色の数を抜き出して作った列はそれぞれ単調減少となる。
これらを組み合わせて作った数列は、明らかに高々2つの減少列に分割される。

(b) 任意のよい数列を次の「貪欲」な方法で分割する。

先頭の数を赤く塗る。
直前に赤く塗った数より小さく、最も左に出現する数を赤く塗る。
塗れる数が無くなるまで↑の操作を繰り返す。
赤く塗った以外の数を青で塗る。

赤と青で塗られた数列はそれぞれ単調減少となっている。
赤く塗られた数は操作(1)で追加、青く塗られた数は操作(2)で退避させてから操作(3)で追加できる。

(c) 任意の状態において、次に(1)または(3)が行われるまでの操作列が異なると
それらが等しくなりえないことを示す。
次の数を追加するまでの操作列は

【任意回の(2)の操作】-> (1) : ${x - 【(2)をした回数】}$ が追加される
(3) : その時保留されていた数 ${max(H)}$ が追加される

の2通りが考えられるが、 ${x < max(H)}$ であるため、追加される数は異なる。

操作の途中で覚えておくべき情報は、

現在考えている数
保留中の数の個数
直前に (2) をしたかどうか

だけなので、(1), (2), (3) の操作を漸化式に翻訳すればDPの更新式が得られる。

ここまでできれば元の問題を解くのは簡単で、数列に数が k-1 個溜まった時点で以降の操作をやめれば良い。そして、大きな数から処理をしているので、操作によりできた数列は(条件2)の条件を自動的に満たす。 また、この時点で保留中の数を昇順に並べたものが、1から右の残りになる。

右パート: n-k個

こちらは簡単。k-1個と、1を並べ終わったあとデックに残るのは n-k 個。これを左右から自由にとって並べる場合の数を考えよう。

n個の並べ方の数を ${p(n)}$ とおく。デックの最後の数が、出来上がる数列の何番目にできるかで場合分けする。

先頭に来る場合 : 残り n-1 個の並べ方と等しいので、 ${ p(n-1) }$
2番目に来る場合 : ${a_1, a_n}$ ときて、残りは n-2 個の並べ方と等しいので、 ${ p(n-2) }$
i番目に来る場合 : ${a_1, a_2, .. , a_{i-1}, a_n}$ ときて、残りは n-i 個の並べ方と等しいので、 ${ p(n-i) }$
最後に来る場合 : 1通り

.. と考えると、 ${ p(n) = p(n-1) + p(n-2) + .. + p(1) + 1 }$ という漸化式が立つ。また ${ p(1) = 1 }$ である。これを解くと、 ${p(n) = 2^{n-1}}$ になる。よって、 ${p(n-k) = 2^{n-k-1}}$ を左パートの計算結果と掛け算すると最終的な答えになる。

解答コード

gist39180cf8529c8ce3cdf854b1dce75e22

*1:個人の感想