この問題は、すべてのマスに \(1\) 個ずつ石を置くことができるか判定することと可能な場合は操作回数の最小値を求めることが必要です。

すべてのマスに \(1\) 個ずつ石を置くことができる条件

まず、\(\sum_{i=1}^{M}A_i=N\) である必要があります。以降、満たしているとします。

このとき、\(i=1,2,\ldots,N\) について、マス \(1,2,\ldots,i\) にある石の個数が合計で \(i\) 個以上であることが必要十分条件となっています。

これは、石が入っているマスの番号が小さい順に最終的なマスを \(1,2,\ldots,N\) と割り当てていくことで、すべての石は必ず割り当てられた先のマスに移動させることができると考えるとわかりやすいです。

この条件を全ての \(i\) について確認することは \(N\) が最大で \(2 \times 10^9\) であることより少し難しいですが、マス \(1,2,\ldots,i\) にある石の個数の合計が変化するような \(i\) が\(X_1,X_2,\ldots,X_M\) の \(M\) 個であることより、\(i=X_1-1,X_2-1,\ldots,X_M-1\) \((1 \leq i \leq M)\) について確認するだけで十分であることがわかります。また、番号が \(i\) 以下のマスの石の総和を求めやすくするために\(X_1 < X_2 \ldots <X_M\) をみたすように事前に適切にソートしておき、累積和を求めていくことでこの条件の確認をソート以外の部分は \(O(M)\) で行うことができます。

必要な操作回数の最小値の求め方

全ての石についてそれが入っているマスの番号の総和を考えます。操作を \(1\) 回することでマス \(i\) にあった石がマス \(i+1\) に置かれます。このとき、マスの番号の総和が \(1\) 増加しています。すでに条件を満たすことができるか事前に判定していれば、この値がどれだけ変化するかを元に操作回数を求めることができます。

よって、操作回数の最小値は \(\frac{N(N+1)}{2}-\displaystyle \sum_{i=1}^{M}X_i \times A_i \) となります。

ソートがボトルネックとなり、計算量は \(O(M\log M)\)になります。

実装例(C++):

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

int main() {
    long long n;
    int m;
    cin >> n >> m;
    vector<pair<int, long long>> xa(m);
    for (int i = 0; i < m; ++i) {
        cin >> xa[i].first;
    }
    for (int i = 0; i < m; ++i) {
        cin >> xa[i].second;
    }
    sort(xa.begin(), xa.end());
    long long sum = 0, sum_idx = 0;
    for (int i = 0; i < m; ++i) {
        if (sum < xa[i].first - 1) {
            cout << -1 << endl;
            return 0;
        }
        sum += xa[i].second;
        sum_idx += xa[i].second * xa[i].first;
    }
    if (sum != n) {
        cout << -1 << endl;
        return 0;
    }
    cout << n * (n + 1) / 2 - sum_idx << endl;
}