第6回 ドワンゴからの挑戦状 予選 D - Arrangement
公式解説の読解がちょっとつらいので、それよりは分かりやすい解法になっているはず…
解法
まずは貪欲に作ってみる
「カード の右隣のカードがカード
であってはならない」という条件は、そんなに厳しい条件ではないように思います。なのでまずは前から貪欲に順列を作ってしまい、そこから修正していく方針が取れないか考えてみましょう。
というわけで、まずは前から貪欲に以下のような置き方をしてみます。
- 1枚目にカード
を置く。
- 2枚目から
枚目までを順に決める。このとき残っているカードの中で一番小さいカードを置ける（1つ前のカードの
の値と異なる）ならそれを置き、置けない場合は2番目に小さいカードを置く。
この方法で 枚目までは必ずカードを置くことができます。またこれより辞書順で小さい順列を作ることは絶対にできません。もし最後に残ったカードを
枚目としてそのまま置けるなら、これが答えです。
最後が置けない場合の修正案
最後のカードが置けない場合を考えます。このときは既に置いた 枚のカードを崩すことになります。辞書順最小の答えを得るためには、既に置いたカードの順番を先頭からできるだけ長く保ちたいです。
カードを並べた状態が次の図のようになっているとしましょう。
最後に残ったカードを とします。そして末尾に連続する
であるカード群の先頭を
、そのさらに前を（存在する場合）
とします。このとき
であり、さらに
を置けていることから
でもあります。
このとき、先頭から までの順番を保持して
より後ろを組み替えても、
をどのカードの後ろにも置けないので絶対に条件を満たせません。
では先頭から までの順番を保持して、
とそれ以降のカードを一旦取り除き、
があった位置に他のカードを置きます。このとき代わりに置ける可能性があるのは
だけです。ここに
以外のカードを置いても、
をどのカードの後ろにも置けないという状況は全く同じだからです。
そして の次は「残っている中で最小のカード、ただしそれが
と一致する場合は2番目」のカードを置きます。
を置いた時点で余りカードが2枚以上残っているならば、このとき必ず置けるカードが存在します。
これ以降、「次に置いてはいけないカード」は全て になります。そして
はもう既に使っているので、残ったカードはどんな順番で置いても良いです。小さい順に貪欲で置けば答えを求められます。
の次を置けない場合
最後に残ったケース、先ほどの方法で の次に置けるカードが存在しない場合を考えます。
これはどのような状態になっているでしょうか。 とそれ以降を取り除いて
を置いた時点で余りカードが2枚未満ということは、
は
枚目のカードだったということになります。そして
の後ろに余りカード（つまり
）を置けないということは、以下のような状態になっているはずです。
この図のように であり、さらに
の位置にカードが存在する場合
です。
そのため以下の2つの置き方はいずれも の条件に違反せず、
のさらに前にあるカードの条件を考慮しても少なくとも一方は正当な並べ方であることが分かります。これらをどちらも試し、正当なもののうち辞書順で小さいものを答えとすれば良いです。
※後のリンク先ACコードでは少し違う処理をしていて、 が
枚目のカードだった時点で
の末尾での並べ方6通りのうち少なくとも1つは条件を満たすので、これを全探索しています。
ただし入力例2にある
2 2 1
の場合、この にあたるカードも存在せず、条件を満たす順列は存在しません。
-1を出力するケースはこれだけです。
