Codeforces Round #175 Div2 - くじらにっき++

順列に関する問題セットでした。

A. Slightly Decreasing Permutations

http://www.codeforces.com/problemset/problem/285/A

順列 $p_1,\ p_2,\ ...,\ p_n$ について $p_i\ >\ p_{i+1}$ となる $i$ の個数のことを、その順列の decreasing coefficient と呼びます。

整数nとkを与えるので、長さnで decreasing coefficient がkである順列を表示して下さい。複数存在する場合は、どれを表示しても構いません。また、そのような順列が必ず存在することは保証されています。

いろいろ方法はありますが [1, 2, ..., n] という順列をつくり [0, k] の範囲を反転させる、という方法を使いました。

n=5, k=2 なら [1, 2, 3, 4, 5] => [3, 2, 1, 4, 5] となります。

B. Find Marble

http://www.codeforces.com/problemset/problem/285/B

PetyaさんとVasyaさんがゲームをします。Petyaさんはn個のコップを一列に並べます。それぞれのコップが置かれている位置を、左から右に 1, ..., n と呼ぶことにしましょう。

Petyaさんはまずsの位置にあるコップにビー玉を入れます。続いて、並べ替えの方法を定義した $p_1,\ p_2,\ ...,\ p_n$ にしたがって、コップを並べ替えます。並べ替えは1の位置にあるコップを $p_1$ の位置へ、2の位置にあるコップを $p_2$ の位置へ… というように行われます。

Petyaさんがこの並べ替えを任意の回数行ったあと、PetyaさんはVasyaさんにビー玉がどの位置のコップにあるか伝えます。Vasyaさんの課題は、ビー玉がsからtへ移動するのに必要な並べ替えの最小の回数を答えることです。Petyaさんが不正な操作を行ったと思われる場合は -1 と答えて下さい。

並べ替えの操作を長さ1の有向グラフにしてsからtへの最短路を求めました。はっきり言って冗長な方法ですが、この方法を使うと、-1と答えなければならない場合にも、難しいことを考えずに済みます。

頂点の数、辺の数がともに 1 <= n <= 10⁵ となるので、最短路を求めるアルゴリズムについてはお察しください。もしもワーシャル-フロイド法で間に合う大きさであれば、実装量的にも有効な方針だったのですが…

C. Building Permutation

http://www.codeforces.com/problemset/problem/285/C

数列 $a_1,\ a_2,\ ...,\ a_n\ (-10^{9} \leq a_i \leq 10^{9},\ 1 \leq n \leq 3\cdot10^{5})$ が与えられます。この数列に対して、1回の操作で以下のどちらかを行えます。

いずれかの数をインクリメントする
いずれかの数をデクリメントする

この操作を複数回行なって、この数列を次の条件に合うようにします。

数列を構成するどの数も、nを超えない正の整数である
数列に含まれる数に、重複は無い

必要な操作の最小の回数を答えて下さい。

数列と書いてありますが、順序は関係ありません。つまり「[1, n] の集合を作ってね」ということです。

順序が関係ない入力が与えれるときは、「とりあえずソートしてみる」というのが意外と有効だったりします。実は、昇順にソートして前の要素から順に 1, 2, ... n に変更していけば良いです。

既に1..nの範囲にある要素はそのままにして……というようなことをやりたくなりますが、そんな余計なことを考える必要はありません。蟻本に載っている Ants を参考にして下さい。

前回の反省を全く活かせていなくて、見てくださいる方に申し訳ないのですが、答えはintに収まりません。