Official

C - Jumping Through Intervals Editorial by Kite_kuma


この問題には様々な解法がありますが,ここでは簡潔な説明が可能な admin の解法を紹介します.

まず \(1\leq k\leq N\) と整数 \(x\) に対し,\(f_k(x)\) を以下のように定めます:

\[ f_k(x) = \Big(A_k = x, L_i \leq A_i \leq R_i\ (k + 1 \leq i \leq N) という制約のもとでの,\sum_{i=k}^{N-1}|A_{i+1}-A_i| の最小値\Big) \]

定義より,明らかに \(f_N(x) = 0\) です.また,整数の集合 \(I_k\) を以下で定めます:

\[ \begin{aligned} I_k & \coloneqq \underset{x\in [L_k, R_k] \cap \mathbb{Z}}{\mathrm{argmin }} f_k(x) \\ & = \Big\lbrace x \in [L_k, R_k] \cap \mathbb{Z} \Bigm\vert f_k(x) = \min_{x'\in [L_k, R_k] \cap \mathbb{Z}} f_k(x') \Big\rbrace. \end{aligned} \]

このとき以下の命題が成立します.

命題 \(1\).

  1. \(1\leq k \leq N\) に対し,\(I_k\) は整数の区間として表せる.すなわち,ある整数 \(l_k, r_k \ (l_k \leq r_k)\) が存在して \(I_k = [l_k, r_k] \cap \mathbb{Z}\) である.以降でもこの \(l_k, r_k\) を用いる.
  2. \(I_N = [L_N, R_N]\) であり,\(k < N\) に対して,
    • \([L_k, R_k] \cap I_{k+1} \neq \emptyset\) のとき,\(I_k = [L_k, R_k] \cap I_{k+1}\).
    • \(R_k < l_{k+1}\) のとき,\(I_k = \lbrace R_k \rbrace\).
    • \(L_k > r_{k+1}\) のとき,\(I_k = \lbrace L_k \rbrace\).
    である.
  3. \(m_k =\displaystyle \min_{x \in [L_k, R_k] \cap \mathbb{Z}} f_k(x)\) とする.\(1 \leq k < N\) に対して

    \[ f_k(x) = \begin{cases} m_{k+1} + l_k - x & (x < l_k)\\ m_{k+1} & (x\in [l_k, r_k])\\ m_{k+1} + x - r_k & (r_k < x) \end{cases} \]

    が成り立つ.

この命題は \(k\) の降順に帰納法を用いることにより証明できます.命題 \(1\) より,\(I_k = [l_k, r_k]\) となる整数 \(l_k, r_k\) が存在します.また命題 \(1\) の 2. に従って \(k\) の降順に各 \(l_k, r_k\) を求めることができます.

次に,辞書順最小の解の構築を考えます.\(I_1\) の定義より,\(A_1 = \min I_1 = l_1\) としてよいです.以下では \(k \geq 2\) において,\(A_1, \dots, A_{k-1}\) までが確定している状況で \(A_k\) を決めることを考えます.このとき \(|x - A_{k-1}| + f_k(x)\) を最小化する \(x\in [L_k, R_k]\) のうち,最小のものを \(A_k\) とすればよいです.命題 \(1\) の 3. を用いて計算することで,\(A_k = \max\lbrace \min \lbrace A_{k-1}, r_k \rbrace , L_k \rbrace\) となることが分かります.よって \(k\) の昇順に各 \(A_k\) を求めることができます.

実装例 (C++):

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;

	vector<ll> L(n), R(n);
	for(int i = 0; i < n; i++) cin >> L[i] >> R[i];

	vector<ll> l(n), r(n);
	l.back() = L.back(), r.back() = R.back();

	for(int i = n - 2; i >= 0; i--) {
		if(R[i] < l[i + 1]) {
			l[i] = r[i] = R[i];
		} else if(L[i] > r[i + 1]) {
			l[i] = r[i] = L[i];
		} else {
			l[i] = max(L[i], l[i + 1]);
			r[i] = min(R[i], r[i + 1]);
		}
	}

	vector<ll> a(n);
	a.front() = l.front();

	for(int i = 1; i < n; i++) { a[i] = clamp(a[i - 1], L[i], r[i]); }
	for(int i = 0; i < n; i++) { cout << a[i] << (i == n - 1 ? '\n' : ' '); }
}

posted:
last update: