はじめに

今回のコンテストでは問題Eに大部分の時間を費やすことになり、残り15分でようやく正解にたどり着くという危ない場面でした。緑色レベルの問題にも苦戦するようでは、まだまだ実力不足を感じます。

A - Election 2

高橋君と青木君のどちらかが過半数の票を獲得したかどうかを判定するシンプルな問題です。

#include <iostream>

using namespace std;

int main() {
    int total, takahashi, aoki;
    cin >> total >> takahashi >> aoki;

    bool is_majority = (takahashi > total - takahashi) || (aoki > total - aoki);
    
    cout << (is_majority ? "Yes" : "No") << endl;
    return 0;
}

B - Vertical Writing

文字列を90度回転して出力する問題です。文字列の長さが揃っていない場合、足りない部分をアスタリスクで埋める必要があります。ループの順序やインデックス管理に注意が必要で、特に内側のループでは下から上へ走査する必要があります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<string> grid(n);
    int max_length = 0;
    
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
        max_length = max(max_length, (int)grid[i].length());
    }

    for (int col = 0; col < max_length; ++col) {
        string result_line = "";
        int pending_stars = 0;
        
        for (int row = n - 1; row >= 0; --row) {
            if (col < grid[row].length()) {
                // 現在の列に文字がある場合
                result_line += string(pending_stars, '*');
                result_line += grid[row][col];
                pending_stars = 0;
            } else {
                // 文字がない場合（穴埋め対象）
                pending_stars++;
            }
        }
        cout << result_line << endl;
    }

    return 0;
}

C - Balls and Bag Query

多重集合の操作をシミュレートする問題です。クエリに応じて要素の追加や削除を行い、現在の異なる要素の種類数を管理します。要素のカウントが0から1に増えたとき、または1から0に減ったときに種類数を更新します。

#include <iostream>
#include <map>

using namespace std;

int main() {
    int q;
    cin >> q;
    
    map<int, int> counter;
    int unique_types = 0;
    
    while (q--) {
        int command;
        cin >> command;
        
        if (command == 1) {
            int x;
            cin >> x;
            if (counter[x]++ == 0) {
                unique_types++;
            }
        } else if (command == 2) {
            int x;
            cin >> x;
            if (--counter[x] == 0) {
                unique_types--;
            }
        } else {
            cout << unique_types << endl;
        }
    }
    return 0;
}

D - Cuboid Sum Query

3次元の累積和を利用して、直方体領域の総和を高速に求める問題です。包含と排除の原理を用いて、各点の累積和を計算します。事前に3次元配列で累積和を構築しておくことで、任意のクエリに対して定数時間で回答を導き出せます。

#include <iostream>

using namespace std;

const int MAX_N = 105;
long long sum[MAX_N][MAX_N][MAX_N];

int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                long long val;
                cin >> val;
                sum[i][j][k] = val 
                    + sum[i-1][j][k] + sum[i][j-1][k] + sum[i][j][k-1]
                    - sum[i-1][j-1][k] - sum[i-1][j][k-1] - sum[i][j-1][k-1]
                    + sum[i-1][j-1][k-1];
            }
        }
    }
    
    int q;
    cin >> q;
    while (q--) {
        int x1, x2, y1, y2, z1, z2;
        cin >> x1 >> x2 >> y1 >> y2 >> z1 >> z2;
        
        long long ans = sum[x2][y2][z2]
            - sum[x1-1][y2][z2] - sum[x2][y1-1][z2] - sum[x2][y2][z1-1]
            + sum[x1-1][y1-1][z2] + sum[x1-1][y2][z1-1] + sum[x2][y1-1][z1-1]
            - sum[x1-1][y1-1][z1-1];
            
        cout << ans << endl;
    }
    return 0;
}

E - Manhattan Multifocal Ellipse

マンハッタン距離の条件を満たす点の数を数える問題です。走査線法と二分探索を組み合わせて解きます。

まず、すべての座標を正の領域にシフトします。次に、走査線（x座標）を左から右へ移動させながら、各x座標におけるy方向の距離の総和を計算します。走査線が右に移動すると、走査線より左側の点とは距離が1近づき、右側の点とは距離が1遠ざかります。この変化量を管理しながら、二分探索を用いて条件「距離の総和がd以下」を満たす点の数を効率的に数え上げます。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int OFFSET = 2e6;
const int RANGE = 4e6 + 5;

int main() {
    int n, d;
    cin >> n >> d;
    
    vector<int> x_coords(n), y_coords(n);
    vector<int> count_x(RANGE, 0);
    vector<int> count_y(RANGE, 0);
    
    for (int i = 0; i < n; ++i) {
        cin >> x_coords[i] >> y_coords[i];
        x_coords[i] += OFFSET;
        y_coords[i] += OFFSET;
        count_x[x_coords[i]]++;
        count_y[y_coords[i]]++;
    }
    
    // x方向の累積カウント
    vector<int> prefix_count_x(RANGE, 0);
    for (int i = 0; i < RANGE; ++i) {
        prefix_count_x[i] = count_x[i] + (i > 0 ? prefix_count_x[i-1] : 0);
    }
    
    // y方向の距離計算用の累積和
    vector<long long> dist_y(RANGE, 0);
    long long current_points = 0;
    for (int i = 0; i < RANGE; ++i) {
        if (i > 0) dist_y[i] = dist_y[i-1] + current_points;
        current_points += count_y[i];
    }
    
    current_points = 0;
    vector<long long> dist_y_reverse(RANGE, 0);
    for (int i = RANGE - 1; i >= 0; --i) {
        if (i < RANGE - 1) dist_y_reverse[i] = dist_y_reverse[i+1] + current_points;
        current_points += count_y[i];
    }
    
    vector<long long> total_distances(RANGE);
    long long sum_x = 0;
    for (auto& x : x_coords) sum_x += x;
    
    for (int i = 0; i < RANGE; ++i) {
        total_distances[i] = dist_y[i] + dist_y_reverse[i] + sum_x;
    }
    
    sort(total_distances.begin(), total_distances.end());
    
    long long answer = 0;
    long long delta = 0;
    
    auto get_count = [&](int l, int r) {
        if (l > r) return 0;
        return prefix_count_x[r] - (l > 0 ? prefix_count_x[l-1] : 0);
    };
    
    for (int i = 0; i < RANGE; ++i) {
        // 走査線が位置iにあるとき、条件を満たす距離は d - delta 以下
        long long limit = d - delta;
        // upper_boundを使って limit 以下の要素数を数える
        answer += upper_bound(total_distances.begin(), total_distances.end(), limit) - total_distances.begin();
        
        // deltaの更新: 左側(0..i)の点は距離が近づき(-)、右側(i+1..)の点は遠ざかる(+)
        // ただし、マンハッタン距離の定義式における符号変化に注意
        // 走査線が右に移動すると、左側の点との距離は減る(-1)、右側の点との距離は増える(+1)
        // sum_dx = (left_count - right_count) * 1
        delta -= get_count(0, i);
        delta += get_count(i + 1, RANGE - 1);
    }
    
    cout << answer << endl;
    return 0;
}

F - Maximum Composition

一次関数の合成順序を最適化し、最大値を求める問題です。

2つの一次関数 $f_1(x) = a_1x + b_1$ と $f_2(x) = a_2x + b_2$ を合成する順序を考えます。$f_1(f_2(x))$ と $f_2(f_1(x))$ を比較すると、$x$ の係数は同じですが定数項が異なります。定数項の大小関係 $a_1b_2 + b_1$ と $a_2b_1 + b_2$ を比較することで、どの順序で合成するのが最適かを判断できます。この基準に基づいて関数をソートした後、動的計画法（DP）によって最大値を求めます。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<pair<long long, long long>> functions(n);
    for (int i = 0; i < n; ++i) {
        cin >> functions[i].first >> functions[i].second;
    }
    
    // ソート基準: f1を内側、f2を外側としたときの定数項の大小
    // f2(f1(x)) = a1*a2*x + a2*b1 + b2
    // f1(f2(x)) = a1*a2*x + a1*b2 + b1
    // f2(f1) > f1(f2) なら f1を先にする（f1を内側にする）方が良い
    // よって a2*b1 + b2 > a1*b2 + b1 の順でソートする
    sort(functions.begin(), functions.end(), [](const auto& lhs, const auto& rhs) {
        // lhs を先に（内側に）するべきか判定
        // rhs(lhs(x)) の定数項 > lhs(rhs(x)) の定数項
        long long val1 = rhs.first * lhs.second + rhs.second; // rhs(lhs(x)) const
        long long val2 = lhs.first * rhs.second + lhs.second; // lhs(rhs(x)) const
        return val1 < val2; // 昇順にしておくと、DPで後ろから取るか前から取るか調整可能
        // ここでは、lhsを先に使った方が結果が大きくなるように順序付け
        // 実際には val2 > val1 (lhs(rhs) > rhs(lhs)) なら lhsを後にしたい（外側）
        // つまり rhsを先にする。
        // 比較関数は sort(p, p+n, cmp) で p[i] が p[j] より前なら p[i] -> p[j] の合成が良いという意味にする
        // p[i] -> p[j] が良い <=> p[j](p[i]) > p[i](p[j])
        // <=> aj*bi + bj > ai*bj + bi
        return lhs.second * (rhs.first - 1) < rhs.second * (lhs.first - 1); // 必要に応じて調整
        // 一般的な解法: a1*b2+b1 と a2*b1+b2 を比較
        return 1LL * lhs.first * rhs.second + lhs.second < 1LL * rhs.first * lhs.second + rhs.second;
    });

    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    
    long long result = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if (j + 1 <= k) {
                long long val = functions[i].first * dp[i][j] + functions[i].second;
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], val);
            }
        }
        result = max(result, dp[i + 1][k]);
    }
    
    cout << result << endl;
    return 0;
}