[Codeforces] Round #529 D. Circular Dance

Circular Dance

https://codeforces.com/contest/1095/problem/D

考え方

題意

\( n \) までの自然数の円順列 \( p \) を考えます。

配列 \( a[i][j] \) が与えられます。この配列は \( n \times 2 \) の配列で、\( a[i][0],\  a[i][1] \) は \( i \) よりも前に存在していることが分かりますが、どちらが一つ前か二つ前にあるかは分かりません。

方針

\( n = 3 \) のときの円順列はパターンは “1 – 2 – 3” と “1 – 3 – 2” の \(2 \) 通りありますが、与えられる情報からはどちらかを特定することができないので、どちらを出力しても構いません。

\( n \geq 4 \) について考えます。\( p_1 = 1 \) とします。\( a[p_i][0], \ a[p_i][1] \) は \( p_i \) の前にあります。\( a[p_i][0]\) が \( p_i \) の一つ前にあるとき、\(a[p_i][0] \) の前に \( a[p_i][1] \) がいなければなりません。このとき、\( p_{i + 1} = a[p_i][0] \) となります。このように調べることで順列を作ることができます。

コード

感想

難しいように思えて、実は簡単な問題でした。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする