行選択による列制約の充足判定

グリッド状のデータに対し、行の削除操作を制限回数内で行った後、残存する列の要件数が指定値以下に収まるかを検証する問題である。行数が比較的小さいため、深さ優先探索を用いて行の採用・不採用のパターンを網羅する。各探索ノードでは、未削除行に含まれる列インデックスを集合に記録し、重複を除いた後のサイズが閾値を超えないか判定する。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

void solve() {
    int rows, cols, max_row_ops, max_col_ops;
    cin >> rows >> cols >> max_row_ops >> max_col_ops;
    vector<string> grid(rows);
    for (auto &line : grid) cin >> line;

    vector<bool> row_skipped(rows, false);
    bool possible = false;

    auto explore = [&](auto &self, int current_row, int used_ops) -> void {
        if (possible || used_ops > max_row_ops) return;
        if (current_row == rows) {
            unordered_set<int> pending_cols;
            for (int r = 0; r < rows; ++r) {
                if (row_skipped[r]) continue;
                for (int c = 0; c < cols; ++c) {
                    if (grid[r][c] == '*') pending_cols.insert(c);
                }
            }
            if (pending_cols.size() <= max_col_ops) possible = true;
            return;
        }

        row_skipped[current_row] = true;
        self(self, current_row + 1, used_ops + 1);
        
        row_skipped[current_row] = false;
        self(self, current_row + 1, used_ops);
    };

    explore(explore, 0, 0);
    cout << (possible ? "yes" : "no") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cases;
    cin >> cases;
    while (cases--) solve();
    return 0;
}

階乗の倍数判定と最小自然数の探索

与えられた整数 \(P\) が \(N!\) の約数となる最小の自然数 \(N\) を導出する。まず \(P\) を素因数分解し、各素因数の必要指数を記録する。次に、ルジャンドルの公式を用いて \(N!\) に含まれる特定素因数の総数を計算する。各素因数について条件を満たす最小の \(N\) を二分探索で求め、そのうち最大値が最終的な解となる。

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

using namespace std;

long long count_factor_in_factorial(long long n, long long p) {
    long long cnt = 0;
    while (n > 0) {
        cnt += n / p;
        n /= p;
    }
    return cnt;
}

void solve() {
    long long target;
    cin >> target;
    long long temp = target;
    vector<pair<int, int>> factors;

    for (long long i = 2; i * i <= temp; ++i) {
        if (temp % i == 0) {
            int exp = 0;
            while (temp % i == 0) {
                temp /= i;
                ++exp;
            }
            factors.emplace_back(i, exp);
        }
    }
    if (temp > 1) factors.emplace_back(temp, 1);

    long long answer = 1;
    for (auto &[prime, req_exp] : factors) {
        long long low = 1, high = target;
        while (low <= high) {
            long long mid = low + (high - low) / 2;
            if (count_factor_in_factorial(mid, prime) >= req_exp) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        answer = max(answer, low);
    }
    cout << answer << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cases;
    cin >> cases;
    while (cases--) solve();
    return 0;
}

完全グラフの辺削除数と頂点除去の最適化

\(N\) 頂点の完全グラフから \(X\) 個の頂点を順次除去する際、消滅する辺の総数は \(X \cdot N - \frac{X(X+1)}{2}\) で表される。この値が指定数 \(M\) 以下となる最大の \(X\) を求める際、中間計算で64ビット整数の範囲を超える可能性があるため、多倍長整数型を用いた評価関数を二分探索に組み込む。

#include <iostream>
#include <vector>

using namespace std;

using i128 = __int128_t;

void solve() {
    long long n, m;
    cin >> n >> m;

    auto edges_removed = [&](long long x) -> i128 {
        return (i128)x * n - (i128)x * (x + 1) / 2;
    };

    long long left = 1, right = n - 1;
    long long optimal = 0;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (edges_removed(mid) <= m) {
            optimal = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << optimal << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cases;
    cin >> cases;
    while (cases--) solve();
    return 0;
}

整数オーバーフローを問う特殊問題

32ビット符号なし整数の循環特性や入力制限を利用する問題であり、実際には特定の固定値を出力することで正解となる。実装は単純な標準出力のみで構成される。

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int dummy;
    if (std::cin >> dummy) {
        std::cout << 4294967296LL << "\n";
    }
    return 0;
}

木構造の辺重み付けと貪欲的割り当て

木グラフの各辺に \(1\) から \(N-1\) の異なる重みを割り当て、全パスの重み合計を最大化する手法。任意の辺が経由される回数は、その辺で分断される部分木の頂点数 \(S\) と残りの頂点数 \(N-S\) の積で算出できる。通過回数を降順にソートし、頻度の高い辺から順に小さい重みを割り当てることで最適解が導かれる。

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<long long> traversal_counts;
    vector<int> subtree_size(n + 1, 1);

    function<void(int, int)> dfs = [&](int u, int parent) {
        for (int v : adj[u]) {
            if (v == parent) continue;
            dfs(v, u);
            subtree_size[u] += subtree_size[v];
        }
        if (u != 1) {
            long long cnt = 1LL * subtree_size[u] * (n - subtree_size[u]);
            traversal_counts.push_back(cnt);
        }
    };

    dfs(1, 0);
    sort(traversal_counts.rbegin(), traversal_counts.rend());

    long long total_score = 0;
    for (size_t i = 0; i < traversal_counts.size(); ++i) {
        total_score += traversal_counts[i] * (i + 1);
    }
    cout << total_score << "\n";
    return 0;
}

2の冪乗による目標値構築判定

与えられた \(2^{K_i}\) の集合から \(2^{30}\) を構築可能か判定する問題。上位の冪乗から順に貪欲に必要な数を消化するアプローチを取る。目標とする上位階層の必要数を `demand` として管理し、現在の桁の個数が `demand * 2` 以上であれば直接充足できる。不足分は次の下位桁へ繰り越し、最終的に `demand` が 0 になれば構築可能と判定する。

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> counts(31, 0);
    vector<int> original_inputs(n);
    for (int i = 0; i < n; ++i) {
        cin >> original_inputs[i];
        counts[original_inputs[i]]++;
    }

    int demand = 1;
    vector<int> used = counts;
    for (int exp = 29; exp >= 0; --exp) {
        if (used[exp] >= demand * 2) {
            used[exp] -= demand * 2;
            demand = 0;
            break;
        }
        demand = demand * 2 - used[exp];
        used[exp] = 0;
    }

    if (demand > 0) {
        cout << "impossible\n";
    } else {
        for (int val : original_inputs) {
            if (counts[val] > used[val]) {
                cout << '1';
                used[val]++;
            } else {
                cout << '0';
            }
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cases;
    cin >> cases;
    while (cases--) solve();
    return 0;
}

辞書順最大の部分文字列の取得

文字列の辞書順比較において、共通の接頭辞を持つ場合は長い文字列が優先される性質を利用する。したがって、全接尾辞を生成して辞書順でソートし、末尾の要素を選択すれば最適な解が得られる。

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    
    vector<string> suffixes;
    suffixes.reserve(s.length());
    for (size_t i = 0; i < s.length(); ++i) {
        suffixes.emplace_back(s, i);
    }
    sort(suffixes.begin(), suffixes.end());
    cout << suffixes.back() << "\n";
    return 0;
}

配列の最大差分計算

一次元配列内の要素の最大値と最小値の差を求める。線形探索で極値を更新するか、標準ライブラリのアルゴリズムを用いて効率的に算出する。

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> data(n);
    for (auto &x : data) cin >> x;
    
    auto result = minmax_element(data.begin(), data.end());
    cout << (*result.second - *result.first) << "\n";
    return 0;
}