実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 521

問題概要

$N$ 個の整数組 $(L_1, R_1), (L_2, R_2), \cdots, (L_N, R_N)$ が与えられる。以下の条件を満たす長さ $N$ の整数列 $X$ が存在するか判定し、存在するならば1つ出力せよ。

条件 :
- 各 $i = 1, 2, \cdots, N$ について、 $L_i \leq X_i \leq R_i$ 。
- $\displaystyle \sum_{i=1}^{N} X_i = 0$

制約

入力はすべて整数。
$1 \leq N \leq 2 \times 10^5$
$-10^9 \leq L_i \leq R_i \leq 10^9$

考察

重要な考察として、「 $\displaystyle \sum_{i=1}^{N} L_i > 0$ または $0 > \displaystyle \sum_{i=1}^{N} R_i$ ならば、条件を満たす $X$ は存在しない」ということが挙げられる。もし $\displaystyle \sum_{i=1}^{N} L_i > 0$ ならば、全ての $X_i$ を $L_i$ にしたとしても $0$ より大きくなってしまい、条件2を満たさないからである。 $R$ についても同様。

以下、 $\displaystyle \sum_{i=1}^{N} L_i \leq 0 \leq \displaystyle \sum_{i=1}^{N} R_i$ とする。

このとき、 $X_i = L_i$ を初期状態として、各 $i$ について次のような貪欲法を取ることで答えを求められる。

$R_i > X_i$ かつ $0 > \displaystyle \sum_{i=1}^{N} X_i$ を満たしている限り $R_i$ に1を加える。 $\implies$ $X_i$ に $\min\biggl( R_i - L_i, \, -\displaystyle \sum_{i=1}^{N} X_i \biggr)$ を加える。

イメージとしては各 $i$ 毎に和を $0$ に揃えていく感じだろうか。

すぐに解法が思いつかない場合はとりあえず貪欲解を試してみる、というのも一つの手である。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<ll> L(N), R(N);
    ll sum_L = 0, sum_R = 0;
    rep(i, 0, N)
    {
        cin >> L[i] >> R[i];
        sum_L += L[i];
        sum_R += R[i];
    }

    if (sum_L > 0 || sum_R < 0)
    {
        cout << "No" << endl;
        return 0;
    }
    else
    {
        cout << "Yes" << endl;
    }

    vector<ll> ans = L;
    ll sum = sum_L;
    rep(i, 0, N)
    {
        ll diff = min(R[i] - L[i], -sum);
        ans[i] += diff;
        sum += diff;
    }

    rep(i, 0, N)
    {
        cout << ans[i] << " ";
    }
}