本記事では、複数のアルゴリズム問題について考察し、それぞれの問題に対する効率的な解法を説明します。

避難所配置問題

この問題は、特定の範囲内で最も効率的な方法で避難所を配置する必要がある。具体的には、以下の関数を考える：

[ g(y, r) ] は、右境界が (r) の場合に、位置 (y) に避難所を設置したときのコストを表す。

我々が必要とするのは、[ \max_{j \geq mid} g(j, r) ] を求めるアルゴリズムである。

(g(y, r)) の性質について詳しく調べると、次のことがわかる：

• 右境界 (r) を増やしていくと、既に避難所に入っている人々が増え続けるため、凸性を持つ。
• この特性により、(r) に対して (g(y, r)) は単調増加となる。

以上の観察から、次のようなアルゴリズムが導かれる：

1. スタックを使用して各後方区間の最大値を管理する。
2. 求めたい結果を二分探索で得る。

以下に実装例を示す：

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

const int MAX_N = 200003;
long long cum_sum, arr[MAX_N], prefix_sums[MAX_N], prefix_sq_sums[MAX_N], results[MAX_N];
vector<int> queries[MAX_N];
int query_l[MAX_N], query_r[MAX_N], query_mid[MAX_N];
int stack_indices[MAX_N], stack_positions[MAX_N], stack_top;

inline long long cost(int l, int r) {
    return (prefix_sq_sums[r] - prefix_sq_sums[l]) - l * (prefix_sums[r] - prefix_sums[l]);
}

inline long long compute_cost(int x, int r) {
    if (x <= 0) return 0;
    int t = min({r - x, x - 1, x});
    return cost(x - t - 1, x + t) + (cum_sum - prefix_sums[x + t] + prefix_sums[x - t - 1]) * (t + 1);
}

void process_queries() {
    for (int i = 1; i <= MAX_N - 3; ++i) {
        prefix_sums[i] = prefix_sums[i - 1] + arr[i];
        prefix_sq_sums[i] = prefix_sq_sums[i - 1] + (long long)i * arr[i];
    }
    stack_top = 0;
    for (int i = MAX_N - 3; i >= 1; --i) {
        while (stack_top > 0 && compute_cost(i, stack_positions[stack_top]) >= compute_cost(stack_indices[stack_top], stack_positions[stack_top])) --stack_top;
        if (stack_top > 0) {
            int l = stack_indices[stack_top], r = stack_positions[stack_top];
            // Binary search logic here...
        } else {
            stack_positions[++stack_top] = MAX_N - 3;
        }
        stack_indices[stack_top] = i;
        for (auto q : queries[i]) {
            int pos = upper_bound(stack_positions + 1, stack_positions + stack_top + 1, query_r[q], greater<int>()) - stack_positions - 1;
            results[q] = max(results[q], compute_cost(stack_indices[pos], query_r[q]));
        }
        queries[i].clear();
    }
}

int main() {
    int n = read(), q = read();
    cum_sum = read<long long>();
    for (int i = 1; i <= n; ++i) {
        arr[i] = read<long long>();
    }
    process_queries();
    // Reverse logic and reprocess
    for (int i = 1; i <= q; ++i) printf("%lld\n", results[i]);
}

チェス盤上の移動問題

チェス盤上で駒を移動させる問題を考える。駒ごとに異なる制約があり、最短経路を求めなければならない。

例えば、Bishop（角）の場合、以下のステップを踏む：

1. 最初の移動方向を決定し、可能な限り端まで移動する。
2. 経路を調整するために、途中のコーナーで1歩減らす操作を行う。
3. コンビネーション数を使って、すべての可能性を計算する。

以下にコード例を示す：

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

const int MOD = 1e9 + 7;
const int MAX_SIZE = 1003;

struct Polynomial {
    int coefficients[2 * MAX_SIZE];
    friend Polynomial operator*(const Polynomial &a, const Polynomial &b) {
        Polynomial result;
        memset(result.coefficients, 0, sizeof(result.coefficients));
        for (int i = 0; i < MAX_SIZE; ++i)
            for (int j = 0; j < MAX_SIZE; ++j) {
                int idx = (i + j) % (2 * MAX_SIZE);
                result.coefficients[idx] = (result.coefficients[idx] + (long long)a.coefficients[i] * b.coefficients[j]) % MOD;
            }
        return result;
    }
};

Polynomial base_poly;
int factorial[MAX_SIZE], inverse_factorial[MAX_SIZE];

inline int comb(int a, int b) {
    if (b > a || b < 0) return 0;
    return (long long)inverse_factorial[b] * factorial[a] % MOD * inverse_factorial[a - b] % MOD;
}

void preprocess() {
    base_poly.coefficients[0] = base_poly.coefficients[1] = base_poly.coefficients[MAX_SIZE - 1] = 1;
    factorial[0] = 1;
    for (int i = 1; i < MAX_SIZE; ++i) factorial[i] = (long long)factorial[i - 1] * i % MOD;
    inverse_factorial[MAX_SIZE - 1] = power_mod(factorial[MAX_SIZE - 1], MOD - 2);
    for (int i = MAX_SIZE - 2; i >= 0; --i) inverse_factorial[i] = (long long)inverse_factorial[i + 1] * (i + 1) % MOD;
}

int main() {
    preprocess();
    Polynomial current = base_poly;
    int rows = read(), cols = read(), queries = read();
    for (int i = 0; i < rows - 1; ++i) current = current * base_poly;
    while (queries--) {
        char piece_type;
        cin >> piece_type;
        int start_col = read(), end_col = read();
        if (piece_type == 'B') {
            if ((start_col ^ end_col ^ rows) & 1) {
                // Complex computation here...
            } else {
                cout << "0 0\n";
            }
        }
    }
}

ロボットマッチング問題

最後の問題は、与えられた配列に基づいてロボットを最適にマッチングするものである。

左から右へ順番にスキャンを行い、条件を満たさない要素をスタックに積み、条件を満たす要素を見つけ次第スタックから取り出す。

以下に実装例を示す：

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

const int MAX_N = 200003;
int n, a[MAX_N], b[MAX_N], stack_buffer[MAX_N], stack_size;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    long long total_cost = 0;
    for (int i = 1; i <= n; ++i) total_cost += abs(a[i] - b[i]);
    cout << total_cost << "\n";
    stack_size = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] >= b[i]) {
            while (stack_size > 0 && b[stack_buffer[stack_size]] - a[stack_buffer[stack_size]] <= a[i] - b[i]) {
                cout << stack_buffer[stack_size--] << " ";
            }
            cout << i << " ";
        } else {
            stack_buffer[++stack_size] = i;
        }
    }
    while (stack_size > 0) cout << stack_buffer[stack_size--] << " ";
    return 0;
}