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

問題概要

$1$ から $N$ までの番号がつけられた $N$ 個のマスが一列に並んでいる。最初、 $M$ 個のマスに石が入っており、マス $X_i$ には $A_i$ 個の石が入っている。これから次の操作を0回以上行うことを考える。

マス $i \: (1 \leq i \leq N-1)$ に石があるとき、マス $i$ から石を1つマス $i+1$ に移動させる。

このとき、 $N$ 個のマスすべてに石がちょうど1個ずつ入っている状態にするために必要な操作回数の最小値を求めよ。ただし、不可能な場合は-1を出力せよ。

制約

入力は全て整数。
$2 \leq N \leq 2 \times 10^{9}$
$1 \leq M \leq 2 \times 10^{5}$
$M \leq N$
$1 \leq X_i \leq N$
$1 \leq A_i \leq 2 \times 10^{9}$

考察

条件を達成可能な石の配置かの判定

まず、最終的に $N$ 個のマスに1つずつ石が置かれている必要があるので、 $\displaystyle \sum_{i = 1}^{M} A_i = N$ でなければならない。

この条件を満たすとき、各々の石は必ずどこかのマスに置かれるはずである。しかし、 $X_i$ の位置と $A_i$ の値によっては、これが不可能な場合がある。それはどういう状態だろうか。

とりあえず、サンプルケースを図に表して考えてみる。なお、マスは数直線として考え、石は丸印で表し、中の数字は対応するマス (最終的に置かれるべきマス) を、緑括弧の中の数字はそのマスまでに置かれた石の個数の合計を表している。

ついでに、もう2つほど実験してみる。

これを眺めていると、あることに気づくだろう。

マス $1, 2, \cdots, N$ と見ていったときに、マス $i$ の時点で石の合計が $i$ 個以上であるならば、条件を満たす。

これは意外と思いつくかもしれない。

ただ、制約で $N \leq 2 \times 10^{9}$ となっているのがこの問題を難しくしている要素の1つである。愚直にマスを1つずつ見ていくのではもちろん TLE になってしまうし、すべてのマスを配列で管理しようとすると MLE に陥る可能性もある。

ここで注目したいのが、石の合計が変化するのは $X_i$ のマスだけであるという点だ (当たり前) 。つまり、この $M$ 個のマスだけについて上の条件を確認すればよさそう ( $M \leq 2 \times 10^{5}$ という制約もヒントか？) 。

石の合計は愚直に $A_i$ をその都度足していく、という方法で十分だが、問題は $X_i, A_i$ が入力ではソートされていないということ。サンプルケースではこれらがすべてソートされた状態の入力であるから、この制約を見逃しがちだ。問題はよく読みましょう (n 敗) 。

最小操作回数の計算

問題はこれで終わりではない。条件を満たす石の配置の場合は、条件を満たすのに必要な操作の最小回数を計算しなければならない。

これは、 $N$ 個の石をマス $0$ に置いて、「そこから入力ケースの状態にするまでに必要な操作の回数」と「最終状態までに必要な操作の回数」に分けて考えるとわかりやすいだろう。

マス $0$ に置かれた石を各マスに置いていくのに必要な操作の回数は全部で $1 + 2 + \cdots + N = \dfrac{N(N+1)}{2}$ 回。これに加えて、入力ケースの状態にするまでに必要な操作の回数は、 $\displaystyle \sum_{i = 1}^{M} X_i A_i$ と書くことができる (上図参考) 。

したがって、求めるべき操作回数は両者の差 $\dfrac{N(N+1)}{2} - \displaystyle \sum_{i = 1}^{M} X_i A_i$ で計算できる。

ここまでわかれば後は実装するだけ。オーバーフローにも気を付けること。

コード

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

using ll = long long;

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

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> X(M), A(M);
    rep(i, 0, M) cin >> X[i];
    rep(i, 0, M) cin >> A[i];

    vector<Pair_ll> stones;
    rep(i, 0, M)
    {
        stones.push_back({X[i], A[i]});
    }
    sort(all(stones));

    if (stones[0].first != 1)
    {
        cout << -1 << endl;
        return 0;
    }

    vector<ll> ps(M + 1, 0);
    rep(i, 0, M) ps[i + 1] = ps[i] + stones[i].second;

    if (ps[M] != N)
    {
        cout << -1 << endl;
        return 0;
    }

    rep(i, 1, M)
    {
        if (ps[i] < stones[i].first - 1)
        {
            cout << -1 << endl;
            return 0;
        }
    }

    ll ans = N * (N + 1) / 2;
    rep(i, 0, M) ans -= stones[i].first * stones[i].second;

    cout << ans << endl;
}