Codeforces Round 776 (Div. 3) C – Weight of the System of Nested Segments / D – Twist the Permutation を解いた記録
C – Weight of the System of Nested Segments
問題の概要
数直線上に \(m\) 個の点がある．点 \(i\) の座標は \(x_{i}\), 重さは \(w_{i}\) である．
2点の組からなる区間を \(n\) 個作りたい．ただし，区間は入れ子状になっていなければならない（問題のページにある図を参考にせよ）．
区間に採用される点の重みの総和の最小値を求めよ．また，区間を実際に構築せよ．
制約
- \(1 \leq n \leq 10^{5}\)
- \(2 \times n \leq m \leq 2 \times 10^{5}\)
- \(-10^{9} \leq x_{i} \leq 10^{9}\)
- \(-10^{4} \leq w_{i} \leq 10^{4}\)
- 入力はすべて整数
解法
実はどのように \(2 \times n\) 個の点を持ってきても，入れ子状になった区間は構築できます．
そこで，重さの小さい点から貪欲に \(2 \times n\) 個採用し，実際に区間を構築すればよいです．
実装例
D – Twist the Permutation
問題の概要
数列 \(a = (1, 2, \dots, n)\) が与えられる．次の操作を \(n\) 回行う．
- \(i\) 回目の操作では，数列の先頭から \(1\) 番目から \(i\) 番目までの要素について循環シフト（ローテーション）を行う．このとき，シフト幅は任意とする（0でもよい）．
操作後の数列が与えられるので，数列をそのようにするための操作手順を構築せよ．
制約
- \(1 \leq n \leq 2 \times 10^{3}\)
- 入力はすべて整数
解法
最後に行う操作を考えてみます．数字 \(n\) は最後の操作でしか動かせないので，操作が全て終わったあとの数列を数列 \(P, Q\) により
\[(P \quad n \quad Q)\]
のように表せたとすると，最後の操作を行う前の数列は
\[(Q \quad P \quad n)\]
のように表せます．
同様にして最後の操作から順々に考えていけば，初期状態の数列を与えられた数列にするための操作手順を構築できます．