C問題：石の山の配置

石を後方にしか移動できないという制約下で、目標の配置が可能かどうかを判定し、最小移動回数を求める問題です。

条件を満たす配置は一意に定まるため、以下の3点をチェックします。

• 石の総数がnと一致しない場合は不可能。
• 最初の山の位置が1でなければ不可能。
• 途中の位置で、それまでの石の合計数が必要数に満たない場合は不可能。

解答の計算では、現在の山から次の山までの間にあるべき石を現在の山から補充し、余った石を次の山に移動させます。もし移動後に不足が生じれば、その時点で不可能と判断します。

入力の山の情報は、位置でソートしておく必要があります。

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

int n, m;
struct Node{
    int pos, cnt;
} p[200005];
int total, ans;

bool cmp(Node a, Node b){
    return a.pos < b.pos;
}

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> p[i].pos;
    for(int i = 1; i <= m; i++){
        cin >> p[i].cnt;
        total += p[i].cnt;
    }
    sort(p + 1, p + m + 1, cmp);
    p[m + 1].pos = n + 1;

    if(total != n || p[1].pos != 1){
        cout << -1 << endl;
        return 0;
    }

    for(int i = 1; i <= m; i++){
        int gap = p[i + 1].pos - p[i].pos - 1;
        ans += gap * (gap + 1) / 2;
        int rem = p[i].cnt - gap - 1;
        if(rem < 0){
            cout << -1 << endl;
            return 0;
        }
        ans += rem * (p[i + 1].pos - p[i].pos);
        p[i + 1].cnt += rem;
    }

    cout << ans << endl;
    return 0;
}

D問題：花の収穫

無数の花瓶がある状況で、3種類の操作を実装する問題です。

• 操作1：現在時刻に新しい花を植える。
• 操作2：現在時刻をxだけ進める。
• 操作3：基準高さxに達した花を収穫する。花の高さは（現在時刻 - 植えた時刻）で決まる。

植えた時刻を管理するために優先度付きキュー（最小値が先頭）を使用します。操作3では、収穫条件を満たす花を順に取り出します。

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

int q, cur;
priority_queue<int, vector<int>, greater<int> > pq;

signed main(){
    cin >> q;
    while(q--){
        int op, x;
        cin >> op;
        if(op == 1){
            pq.push(cur);
        } else if(op == 2){
            cin >> x;
            cur += x;
        } else {
            cin >> x;
            int limit = cur - x, cnt = 0;
            while(!pq.empty()){
                int t = pq.top();
                if(t <= limit){
                    pq.pop();
                    cnt++;
                } else break;
            }
            cout << cnt << endl;
        }
    }
    return 0;
}

E問題：部分文字列の総和

長さnの数字列Sの全ての部分文字列を数値とみなしたときの総和を求める問題です。

各桁の寄与を考えます。例えばS=25374の場合、各数字が現れる回数は以下の通りです。

• S[1]=2：万の位1回、千の位1回、百の位1回、十の位1回、一の位1回 → 2 × 11111
• S[2]=5：千の位2回、百の位2回、十の位2回、一の位2回 → 5 × 2222
• ... 以下同様

一般化すると、S[1]×1, S[2]×2, ..., S[n]×n を重みとして、累積和を取ることで各桁の値が求まります。これを高精度で計算し、繰り上がり処理を行います。

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

int n;
char s[200005];
long long acc;
long long ans[3000005];
int idx;

int main(){
    cin >> n >> s + 1;
    for(int i = 1; i <= n; i++) acc += (s[i] - '0') * i;

    for(int i = n; i >= 1; i--){
        ans[++idx] = acc;
        ans[idx] += ans[idx - 1] / 10;
        ans[idx - 1] %= 10;
        acc -= (s[i] - '0') * i;
    }

    while(ans[idx] >= 10){
        idx++;
        ans[idx] += ans[idx - 1] / 10;
        ans[idx - 1] %= 10;
    }

    for(int i = idx; i >= 1; i--) cout << ans[i];
    return 0;
}

F問題：山と展望

数列h（山の高さ）と複数のクエリ（l_i, r_i）が与えられます。各クエリに対して、l_iとr_iの両方から見えるr_iより右側の山の数を求めます。

山i（i > r）が両方から見える条件は、l<j<iかつr<j<iの区間の最大値がh[i]以下であることです。後者の条件は前者に包含されるため、実質的にはmax(h[l+1], ..., h[i-1]) ≤ h[i]かつi > rです。

この問題を解くために、次のように処理します。

• クエリをlの値で分類する（オフライン処理）。
• インデックスをnから1に向かって走査し、単調減少スタックを維持する。新しい要素がスタックトップより大きい場合、スタックトップは前方から隠れるため取り除く。
• 各lにおいて、スタックはlから見える山の集合を表す。この集合から、インデックスがrより大きいものを二分探索で数える。

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

int n, q;
int h[200005];
vector<pair<int, int>> query[200005];
int st[200005], top;
int ans[200005];

int binsearch(int x){
    int lo = 0, hi = top;
    while(lo < hi){
        int mid = (lo + hi + 1) / 2;
        if(st[mid] > x) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        query[l].push_back({r, i});
    }

    for(int i = n; i >= 1; i--){
        for(auto &p : query[i])
            ans[p.second] = binsearch(p.first);
        while(top && h[st[top]] <= h[i]) top--;
        st[++top] = i;
    }

    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
    return 0;
}