問題概要と考察

本稿では3つのアルゴリズム問題を解くための手法について説明します。各問題で異なる技術が要求されています。

第1問：骨牌配置の最適化

n枚の骨牌を並べるとき、ある位置から倒すことで連続して倒れる骨牌の数を最小化する問題です。

考え方

最終的な回答は、末尾のいくつかの骨牌を削除した後の状態から計算できます。任意の位置まで考えた時の最適値をDPで保持し、各位置で最も効率的な戦略を選びます。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 100005;
struct Piece {
    int pos, len;
} data[MAXN];

int dp[MAXN], N;

int main() {
    ios::sync_with_stdio(false);
    cin >> N;
    
    for (int i = 1; i <= N; i++) {
        cin >> data[i].pos >> data[i].len;
    }
    
    sort(data + 1, data + N + 1, [](Piece a, Piece b) {
        return a.pos < b.pos;
    });
    
    for (int i = 1; i <= N; i++) {
        int threshold = data[i].pos - data[i].len;
        int idx = lower_bound(data + 1, data + N + 1, 
            Piece{threshold, 0},
            [](Piece a, Piece b) {
                return a.pos < b.pos;
            }) - data;
        
        dp[i] = dp[idx - 1] + (i - idx);
    }
    
    int best = 1e9;
    for (int i = 1; i <= N; i++) {
        best = min(best, dp[i] + (N - i));
    }
    
    cout << best << endl;
    
    return 0;
}

第2問：区間最大値の累積和

配列の隣接要素間の差を取った後、各区間における最大値の総和を求める問題です。

アプローチ

各要素がどの範囲で最大値になるかを特定するために、単調スタックを用います。左方向と右方向にそれぞれ最初に出現する大きい値の位置を記録し、その要素が最大となる区間の個数を乗算原理で計算します。

#include <cstdio>
#define ll long long

const int INF = 2147483647;
const int SZ = 100010;

int arr[SZ], L[SZ], R[SZ], stack[SZ], top;
int n, queries;
int absolute(int x) { return x > 0 ? x : -x; }

int main() {
    scanf("%d %d", &n, &queries);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    
    for (int i = 1; i < n; i++) {
        arr[i] = absolute(arr[i + 1] - arr[i]);
    }
    n--;
    arr[0] = arr[n + 1] = INF;
    
    // 左端を探す
    top = 0;
    stack[++top] = 0;
    for (int i = 1; i <= n; i++) {
        while (top && arr[stack[top]] <= arr[i]) top--;
        L[i] = stack[top] + 1;
        stack[++top] = i;
    }
    
    // 右端を探す
    top = 0;
    stack[++top] = n + 1;
    for (int i = n; i >= 1; i--) {
        while (top && arr[stack[top]] < arr[i]) top--;
        R[i] = stack[top] - 1;
        stack[++top] = i;
    }
    
    while (queries--) {
        int leftBound, rightBound;
        scanf("%d %d", &leftBound, &rightBound);
        
        ll total = 0;
        for (int i = leftBound; i < rightBound; i++) {
            ll l = i > leftBound ? L[i] : leftBound;
            ll r = i < rightBound - 1 ? R[i] : rightBound - 1;
            total += (ll)arr[i] * (i - l + 1) * (r - i + 1);
        }
        
        printf("%lld\n", total);
    }
    
    return 0;
}

第3問：モンスター討伐順の最適化

各モンスターに攻撃コストと回復量が設定されているとき、すべてのモンスターを倒せる順序を決定する問題です。

方針

モンスターを二種類に分類します。攻撃コストが回復量より小さいもの（タイプA）と、そうでないもの（タイプB）です。タイプAはコスト昇順に処理し、タイプBは逆方向から考えることで最適な順序が得られます。

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

const int M = 200005;
pair monster[M];
int resultOrder[M];
int n;
long long initialHealth, currentHealth;

bool compareTypeA(int a, int b) {
    return monster[a].first < monster[b].first;
}

bool compareTypeB(int a, int b) {
    return monster[a].second > monster[b].second;
}

int main() {
    scanf("%d %lld", &n, &initialHealth);
    currentHealth = initialHealth;
    
    vector<int> groupA, groupB;
    
    for (int i = 1; i <= n; i++) {
        int attack, heal;
        scanf("%d %d", &attack, &heal);
        monster[i] = {attack, heal};
        
        if (attack <= heal) {
            groupA.push_back(i);
        } else {
            groupB.push_back(i);
        }
    }
    
    sort(groupA.begin(), groupA.end(), compareTypeA);
    sort(groupB.begin(), groupB.end(), compareTypeB);
    
    for (int id : groupA) {
        currentHealth -= monster[id].first;
        if (currentHealth <= 0) {
            cout << -1 << endl;
            return 0;
        }
        currentHealth += monster[id].second;
    }
    
    long long tempHealth = currentHealth;
    for (auto it = groupB.rbegin(); it != groupB.rend(); ++it) {
        tempHealth -= monster[*it].second;
        if (tempHealth <= 0) {
            cout << -1 << endl;
            return 0;
        }
        tempHealth += monster[*it].first;
    }
    
    for (int id : groupA) {
        printf("%d ", id);
    }
    for (auto it = groupB.rbegin(); it != groupB.rend(); ++it) {
        printf("%d ", *it);
    }
    printf("\n");
    
    return 0;
}