CF1872B 通路の限界

問題概要

一列に並んだ部屋のうち、いくつかには罠があります。各罠のある部屋には、到達可能な時間の制限があります。プレイヤーは1番目の部屋から最大で何番目の部屋まで往復できるかを求めます。

解法

各罠部屋の到達可能な最大位置を計算します。この位置は、罠の発生時間の半分を基準に計算されます。すべての罠部屋を距離順にソートし、途中で到達不可能な罠が現れるまで探索します。

コード

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

struct Trap {
    int distance;
    int time;
};

bool compare(const Trap& a, const Trap& b) {
    return a.distance < b.distance;
}

void solve() {
    int n;
    cin >> n;
    vector<Trap> traps(n);
    for (int i = 0; i < n; ++i) {
        cin >> traps[i].distance >> traps[i].time;
    }
    sort(traps.begin(), traps.end(), compare);
    
    int current_limit = traps[0].distance + (traps[0].time - 1) / 2;
    for (int i = 1; i < n; ++i) {
        if (traps[i].distance > current_limit) {
            break;
        }
        int new_limit = traps[i].distance + (traps[i].time - 1) / 2;
        current_limit = min(current_limit, new_limit);
    }
    cout << current_limit << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

CF1872C 共通因数を持つ数の分割

問題概要

2つの整数 l と r が与えられます。a + b が l 以上 r 以下となるような a と b の組で、最大公約数が1でないものを求めます。

解法

r が 3 以下の場合は解がありません。それ以外の場合、r 以下の偶数の中で最も大きな数を取り、その数の因数を使って a と b を構成します。

コード

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

void find_solution(int x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            cout << i << " " << x - i << endl;
            return;
        }
    }
    cout << -1 << endl;
}

void solve() {
    int l, r;
    cin >> l >> r;
    if (l == r) {
        find_solution(l);
    } else if (r <= 3) {
        cout << -1 << endl;
    } else {
        for (int i = r; i >= l; --i) {
            if (i % 2 == 0) {
                find_solution(i);
                return;
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

CF1872D 加減順列

問題概要

n 個の要素を持つ順列 p があり、x の倍数の位置の値の合計から y の倍数の位置の値の合計を引いた最大値を求めます。

解法

x の倍数かつ y の倍数ではない位置には最大の値を、y の倍数かつ x の倍数ではない位置には最小の値を割り当てます。これにより合計値の差が最大になります。

コード

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

long long sum(int x) {
    return (long long)x * (x + 1) / 2;
}

int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

void solve() {
    long long n, x, y;
    cin >> n >> x >> y;
    long long lcm = x * y / gcd(x, y);
    long long count_x = n / x - n / lcm;
    long long count_y = n / y - n / lcm;
    long long sum_x = sum(n) - sum(n - count_x);
    long long sum_y = sum(count_y);
    cout << sum_x - sum_y << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}