第6回ドワンゴからの挑戦状予選 D - Arrangement

D - Arrangement

公式解説の読解がちょっとつらいので、それよりは分かりやすい解法になっているはず…

解法

まずは貪欲に作ってみる

「カード $i$ の右隣のカードがカード $a_{i}$ であってはならない」という条件は、そんなに厳しい条件ではないように思います。なのでまずは前から貪欲に順列を作ってしまい、そこから修正していく方針が取れないか考えてみましょう。

というわけで、まずは前から貪欲に以下のような置き方をしてみます。

1枚目にカード $1$ を置く。
2枚目から $N-1$ 枚目までを順に決める。このとき残っているカードの中で一番小さいカードを置ける（1つ前のカードの $a_{i}$ の値と異なる）ならそれを置き、置けない場合は2番目に小さいカードを置く。

この方法で $N-1$ 枚目までは必ずカードを置くことができます。またこれより辞書順で小さい順列を作ることは絶対にできません。もし最後に残ったカードを $N$ 枚目としてそのまま置けるなら、これが答えです。

最後が置けない場合の修正案

最後のカードが置けない場合を考えます。このときは既に置いた $N-1$ 枚のカードを崩すことになります。辞書順最小の答えを得るためには、既に置いたカードの順番を先頭からできるだけ長く保ちたいです。

カードを並べた状態が次の図のようになっているとしましょう。

f:id:betrue12:20200112090303p:plain

最後に残ったカードを $B$ とします。そして末尾に連続する $a_{i} = B$ であるカード群の先頭を $C$ 、そのさらに前を（存在する場合） $D$ とします。このとき $a_{D} \ne B$ であり、さらに $C$ を置けていることから $a_{D} \ne C$ でもあります。

このとき、先頭から $C$ までの順番を保持して $C$ より後ろを組み替えても、 $B$ をどのカードの後ろにも置けないので絶対に条件を満たせません。

では先頭から $D$ までの順番を保持して、 $C$ とそれ以降のカードを一旦取り除き、 $C$ があった位置に他のカードを置きます。このとき代わりに置ける可能性があるのは $B$ だけです。ここに $B$ 以外のカードを置いても、 $B$ をどのカードの後ろにも置けないという状況は全く同じだからです。

そして $B$ の次は「残っている中で最小のカード、ただしそれが $a_{B}$ と一致する場合は2番目」のカードを置きます。 $B$ を置いた時点で余りカードが2枚以上残っているならば、このとき必ず置けるカードが存在します。

これ以降、「次に置いてはいけないカード」は全て $B$ になります。そして $B$ はもう既に使っているので、残ったカードはどんな順番で置いても良いです。小さい順に貪欲で置けば答えを求められます。

$B$ の次を置けない場合

最後に残ったケース、先ほどの方法で $B$ の次に置けるカードが存在しない場合を考えます。

これはどのような状態になっているでしょうか。 $C$ とそれ以降を取り除いて $B$ を置いた時点で余りカードが2枚未満ということは、 $C$ は $N-1$ 枚目のカードだったということになります。そして $B$ の後ろに余りカード（つまり $C$ ）を置けないということは、以下のような状態になっているはずです。

f:id:betrue12:20200112090315p:plain