AT_tenka1_2013_final_b 天下一マジック

[problemUrl]: https://atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_b どこかの会社の社長である高橋くんは社員を楽しませるためにマジックを披露しようと考えました。 マジックを成功させるためには一見ランダムに並んでいるカードを社員に気付かれないように素早くソートしなければなりません。 使うカードの枚数$ 2N+1 $は必ず奇数で、便宜上それぞれのカードは$ 1 $番から$ 2N+1 $番の番号が書かれているものとします。 高橋くんは次の$ 2 $通りの操作を連続して行いカードを並び替えていきます。 ただし、$ X $は$ 1 $以上$ 2N+1 $未満の整数から成る集合です。 操作$ 1 $（[カット](http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB_(%E3%82%AB%E3%83%BC%E3%83%89)#.E3.82.AB.E3.83.83.E3.83.88)）: 集合$ X $の要素$ K $を選び、カードの先頭から$ K $枚抜き取り、そのままの順番でカードの末尾に置く。 例えば、$ K=3 $の場合は、この操作で\[5, 1, 4, 7, 6, 2, 3\] → \[7, 6, 2, 3, 5, 1, 4\]となる。 操作$ 2 $（[リフルシャッフル](http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB_(%E3%82%AB%E3%83%BC%E3%83%89)#.E3.83.AA.E3.83.95.E3.83.AB.E3.82.B7.E3.83.A3.E3.83.83.E3.83.95.E3.83.AB)）: カードの先頭から$ N+1 $枚のカードと、残りの$ N $枚のカードに分けて、 先頭から$ 1 $枚ずつ交互にカードを取っていく。この際、最初は$ N+1 $枚のカードからなるグループから取る。 例えば、この操作で\[5, 1, 4, 7, 6, 2, 3\] → \[5, 6, 1, 2, 4, 3, 7\]となる。 カードの初期配置と集合$ X $が与えられるので、高橋くんがカードを昇順に並び替えるのに必要な操作の数の最小値を求めなさい。 ただし、カードを完全に昇順に並び替えるのが不可能な場合は`-1`を出力しなさい。 - $ 1≦N≦4 $、$ X=\{1\} $（$ M=1 $、$ K_1=1 $）の入力に正解すると、$ 200 $ 点満点に対して部分点として、$ 20 $ 点が与えられる。 - $ 1≦N≦2013 $、$ X=\{1\} $（$ M=1 $、$ K_1=1 $）の入力に正解すると、$ 200 $ 点満点に対して部分点として、上記とは別に $ 80 $点が与えられる。 - $ 0≦N≦2013 $、$ 0≦M＜2N+1 $の入力に正解すると、$ 200 $ 点満点に対して残りの $ 100 $ 点が与えられる。 カードを昇順に並び替えるのに必要な操作の数の最小値を標準出力に$ 1 $行で出力せよ。 ただし、カードを昇順に並び替えることができない場合は、操作の数の最小値の代わりに`-1`を出力せよ。 なお、最後には改行を出力せよ。 ``` 1 1 3 2 1 1 ``` ``` 2 ``` ``` 2 1 3 2 5 1 4 1 ``` ``` -1 ``` - この場合はどうやっても昇順に並び替えることはできません。 ``` 2 1 4 2 5 3 1 1 ``` ``` 4 ``` - 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。 - 操作$ 2 $を行います。\[4, 2, 5, 3, 1\] → \[4, 3, 2, 1, 5\] - 操作$ 2 $を行います。\[4, 3, 2, 1, 5\] → \[4, 1, 3, 5, 2\] - $ K=1 $として操作$ 1 $を行います。\[4, 1, 3, 5, 2\] → \[1, 3, 5, 2, 4\] - 操作$ 2 $を行います。\[1, 3, 5, 2, 4\] → \[1, 2, 3, 4, 5\] ``` 3 1 1 2 3 4 5 6 7 1 ``` ``` 0 ``` - 最初から昇順になっているため、必要な操作回数の最小値は$ 0 $となります。 ``` 4 2 2 3 4 5 6 7 8 9 1 1 6 ``` ``` 3 ``` - 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。 - $ K=1 $として操作$ 1 $を行います。\[2, 3, 4, 5, 6, 7, 8, 9, 1\] → \[3, 4, 5, 6, 7, 8, 9, 1, 2\] - $ K=6 $として操作$ 1 $を行います。\[3, 4, 5, 6, 7, 8, 9, 1, 2\] → \[9, 1, 2, 3, 4, 5, 6, 7, 8\] - $ K=1 $として操作$ 1 $を行います。\[9, 1, 2, 3, 4, 5, 6, 7, 8\] → \[1, 2, 3, 4, 5, 6, 7, 8, 9\]

N/A

N/A