サイコロとコイン

n面ダイスとコインを使用するゲームの勝率を求める。初期値としてダイスを振り、値が1～K-1の場合コインを繰り返し振る。表が出れば値が倍増、裏が出れば0になり、0で敗北またはK以上で勝利となる。

解法

初期値1～nについて、勝利条件は値が2^x倍されてK以上になることである。各初期値の勝率は1/2^xで、n個の初期値の勝率を合計後nで除算する。

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

int main() {
    int n, k;
    cin >> n >> k;
    double result = 0.0;
    long long base = 1;
    vector<long long> multipliers(32);
    for (int i = 0; i <= 30; i++) {
        multipliers[i] = base;
        base *= 2;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 30; j++) {
            if (multipliers[j] * i >= k) {
                result += 1.0 / multipliers[j];
                break;
            }
        }
    }

    result /= n;
    printf("%.10lf\n", result);
    return 0;
}

両端キュー操作

長さnの数列と操作回数上限kが与えられる。操作は以下の4種類：左端から要素取得(A)、右端から要素取得(B)、取得要素を左に返却(C)、取得要素を右に返却(D)。保持要素の総和最大化を目指す。

解法

A/B操作回数を全探索し、優先度付きキューで負の値を返却。取得順序は小さい値から返却することで総和を最大化する。

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    long long max_sum = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int left = 0; left <= k; left++) {
        for (int right = 0; left + right <= k && left + right <= n; right++) {
            for (int l = 0; l < left; l++) pq.push(arr[l]);
            for (int r = n - 1; r >= n - right; r--) pq.push(arr[r]);

            int returns = k - left - right;
            while (!pq.empty() && returns > 0 && pq.top() < 0) {
                pq.pop();
                returns--;
            }

            long long current = 0;
            while (!pq.empty()) {
                current += pq.top();
                pq.pop();
            }
            max_sum = max(max_sum, current);
        }
    }
    cout << max_sum << endl;
    return 0;
}

列の分解

n個の数値が与えられ、i<jかつA_i<A_jを満たす要素を同色で塗る。最小色数を求める。

解法

最長増加部分列の逆発想。末尾要素を管理し、二分探索で新しい要素を挿入可能な最小の末尾を探す。挿入位置がなければ新規シーケンス作成。

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

int main() {
    int n;
    cin >> n;
    vector<int> seq(n);
    for (int i = 0; i < n; i++) cin >> seq[i];

    vector<int> tails;
    for (int i = n - 1; i >= 0; i--) {
        auto pos = upper_bound(tails.begin(), tails.end(), seq[i]);
        if (pos == tails.end()) tails.push_back(seq[i]);
        else *pos = seq[i];
    }
    cout << tails.size() << endl;
    return 0;
}

格子点距離

n×m格子からk点選択し、全点対間のマンハッタン距離総和の全選択パターン合計をmod 10^9+7で求める。

解法

縦横の座標差を独立に計算。組合せ数学を適用し、各距離dの出現回数と組合せ係数を乗算。mod演算を適宜適用。

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;

long long mod_pow(long long base, int exp) {
    long long res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

long long nCr(long long n, int r) {
    if (r < 0 || r > n) return 0;
    long long num = 1;
    for (int i = 1; i <= r; i++) {
        num = num * (n - i + 1) % MOD;
        num = num * mod_pow(i, MOD - 2) % MOD;
    }
    return num;
}

int main() {
    int rows, cols, k;
    cin >> rows >> cols >> k;
    long long total = 0;

    for (int d = 1; d < rows; d++) {
        total = (total + 1LL * d * (rows - d) % MOD * cols % MOD * cols) % MOD;
    }
    for (int d = 1; d < cols; d++) {
        total = (total + 1LL * d * (cols - d) % MOD * rows % MOD * rows) % MOD;
    }
    total = total * nCr(1LL * rows * cols - 2, k - 2) % MOD;
    cout << total << endl;
    return 0;
}

フレンドシップグラフ

n頂点からk個の距離2の点対を持つ無向連結グラフを構築。不可能な場合は-1を出力。

解法

スターグラフで最大距離2点対数を達成。最大値は(n-1)(n-2)/2で、kが超えると不可能。不足分は頂点を環状に連結して補う。

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

int main() {
    int vertices, required;
    cin >> vertices >> required;
    int max_pairs = (vertices - 1) * (vertices - 2) / 2;

    if (required > max_pairs) {
        cout << "-1\n";
    } else {
        cout << vertices - 1 + max_pairs - required << '\n';
        for (int i = 2; i <= vertices; i++) cout << "1 " << i << '\n';
        for (int i = 2; i <= vertices; i++) {
            for (int j = i + 1; j <= vertices; j++) {
                if (max_pairs == required) return 0;
                cout << i << ' ' << j << '\n';
                max_pairs--;
            }
        }
    }
    return 0;
}

整数カード操作

n個の整数とm個の操作(B,C)が与えられる。操作では最大B個の任意の値をCに変更可能。総和の最大化を目指す。

解法

変更値Cを降順に処理。multisetで最小値から順に変更可能か判定。大きなC値で小さな元の値を置換することで総和を最大化。

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

int main() {
    int n, m;
    cin >> n >> m;
    multiset<int> nums;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        nums.insert(x);
    }

    vector<pair<int, int>> operations;
    map<int, int> count_map;
    while (m--) {
        int b, c;
        cin >> b >> c;
        count_map[c] += b;
    }

    for (auto &[c, b] : count_map) operations.push_back({c, b});
    sort(operations.rbegin(), operations.rend());

    for (auto &[c, b] : operations) {
        while (b > 0 && !nums.empty() && *nums.begin() < c) {
            nums.erase(nums.begin());
            nums.insert(c);
            b--;
        }
    }

    long long total = 0;
    for (int num : nums) total += num;
    cout << total << endl;
    return 0;
}