弦なし閉路の検出と辺グラフ変換
長さ4以上の弦なし閉路を検出する問題では、頂点ベースの探索ではなく辺をノードとする線グラフへの変換が有効である。有向辺 $(u \to v)$ と $(v \to w)$ の間に、辺 $(u, w)$ が存在しない場合にのみ有向辺を張る。この変換により、元のグラフにおける三角形は新グラフで閉路を形成しなくなる。新グラフ上でDFSを実行し、最も深い返祖辺を検出することで、極小な弦なし閉路を $O(N^3)$ の建図コストと線形探索で特定できる。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 1005, MAX_E = 200005;
int num_v, num_e;
int edge_map[MAX_V][MAX_V];
pair<int, int> edge_info[MAX_E * 2];
vector<int> adj_line[MAX_E * 2];
int depth_arr[MAX_E * 2], path_stack[MAX_E * 2], top_idx;
bitset<MAX_E * 2> on_stack;
void traverse(int u, int parent) {
depth_arr[u] = depth_arr[parent] + 1;
path_stack[++top_idx] = u;
on_stack[u] = 1;
int best_back = 0;
for (int v : adj_line[u]) {
if (on_stack[v] && depth_arr[v] > depth_arr[best_back]) {
best_back = v;
}
}
if (best_back) {
cout << edge_info[u].second << ' ';
--top_idx;
while (true) {
cout << edge_info[path_stack[top_idx]].second << ' ';
if (path_stack[top_idx] == best_back) exit(0);
--top_idx;
}
}
for (int v : adj_line[u]) {
if (!depth_arr[v]) traverse(v, u);
}
on_stack[path_stack[top_idx--]] = 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> num_v >> num_e;
for (int i = 1; i <= num_e; ++i) {
int u, v; cin >> u >> v;
edge_map[u][v] = i;
edge_map[v][u] = num_e + i;
edge_info[i] = {u, v};
edge_info[num_e + i] = {v, u};
}
for (int mid = 1; mid <= num_v; ++mid) {
for (int src = 1; src <= num_v; ++src) {
for (int dst = src + 1; dst <= num_v; ++dst) {
if (edge_map[src][mid] && edge_map[mid][dst] && !edge_map[src][dst]) {
adj_line[edge_map[src][mid]].push_back(edge_map[mid][dst]);
adj_line[edge_map[dst][mid]].push_back(edge_map[mid][src]);
}
}
}
}
for (int i = 1; i <= 2 * num_e; ++i) {
if (!depth_arr[i]) traverse(i, 0);
}
cout << "no\n";
return 0;
}
下降階乗冪とスターリング数による数式変形
多項式 $G(k)$ と二項係数の積の和 $\sum G(k)\binom{n}{k}x^k$ を計算する際、通常冪を下降階乗冪 $k^{\underline{i}}$ に変換すると閉じた式が得られる。第二種スターリング数 $\left\{ \begin{matrix} n \\ k \end{matrix} \right\}$ を用いて $k^m = \sum_{i=0}^m \left\{ \begin{matrix} m \\ i \end{matrix} \right\} k^{\underline{i}}$ と展開する。生成関数 $F(x)=(1+x)^n$ の $i$ 階微分を利用すると、$\sum \binom{n}{k} k^{\underline{i}} x^k = n^{\underline{i}} x^i (1+x)^{n-i}$ が導かれる。これにより、多項式係数を下降階乗基底に変換した後、各次数について独立に計算可能となる。
実装例
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAX_DEG = 1005;
i64 mod_val, base_x, n_val, deg_m;
i64 poly_coeff[MAX_DEG], falling_coeff[MAX_DEG], stirling[MAX_DEG][MAX_DEG];
i64 mod_pow(i64 a, i64 b) {
i64 res = 1;
for (; b; b >>= 1, a = a * a % mod_val)
if (b & 1) res = res * a % mod_val;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n_val >> base_x >> mod_val >> deg_m;
for (int i = 0; i <= deg_m; ++i) cin >> poly_coeff[i];
stirling[0][0] = 1;
for (int i = 1; i <= deg_m; ++i)
for (int j = 1; j <= i; ++j)
stirling[i][j] = (stirling[i-1][j-1] + j * stirling[i-1][j]) % mod_val;
for (int i = 0; i <= deg_m; ++i)
for (int j = i; j <= deg_m; ++j)
falling_coeff[i] = (falling_coeff[i] + poly_coeff[j] * stirling[j][i]) % mod_val;
i64 total = 0, falling_n = 1;
for (int i = 0; i <= deg_m; ++i) {
i64 term = falling_coeff[i] * falling_n % mod_val;
term = term * mod_pow(base_x, i) % mod_val;
term = term * mod_pow(base_x + 1, n_val - i) % mod_val;
total = (total + term) % mod_val;
falling_n = falling_n * (n_val - i) % mod_val;
}
cout << total << '\n';
return 0;
}
多項式重み付き行列木定理
生成木の辺権の総和を求める場合、各辺の重みを一次多項式 $w x + 1$ とみなす。行列木定理により得られるラプラシアン行列の行列式は、多項式の積の和となる。このとき $x^2 \equiv 0$ とすれば、定数項は生成木の数、一次項の係数は辺権の総和に対応する。ガウス消去法を多項式環 $\mathbb{Z}_p[x]/(x^2)$ 上で実行し、逆元計算を $(a+bx)^{-1} \equiv a^{-1} - a^{-2}bx$ と近似することで、効やかに計算できる。約数ごとに辺をフィルタリングし、オイラー関数 $\varphi(d)$ を重みとして加算する。
実装例
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 MOD = 998244353;
const int MAX_N = 35, MAX_W = 152515;
struct LinearPoly {
i64 c1, c0; // c1*x + c0
};
LinearPoly operator+(LinearPoly a, LinearPoly b) { return {(a.c1+b.c1)%MOD, (a.c0+b.c0)%MOD}; }
LinearPoly operator-(LinearPoly a, LinearPoly b) { return {(a.c1-b.c1+MOD)%MOD, (a.c0-b.c0+MOD)%MOD}; }
LinearPoly operator*(LinearPoly a, LinearPoly b) { return {(a.c1*b.c0 + a.c0*b.c1)%MOD, (a.c0*b.c0)%MOD}; }
LinearPoly inverse(LinearPoly a) {
i64 inv0 = 1, base = a.c0, exp = MOD - 2;
for(; exp; exp>>=1, base=base*base%MOD) if(exp&1) inv0=inv0*base%MOD;
return {(-a.c1 * inv0 % MOD * inv0 % MOD + MOD) % MOD, inv0};
}
int n_nodes, m_edges, phi[MAX_W], edge_cnt[MAX_W];
bool is_composite[MAX_W];
vector<int> primes;
LinearPoly mat[MAX_N][MAX_N];
void sieve_phi(int limit) {
phi[1] = 1;
for (int i = 2; i <= limit; ++i) {
if (!is_composite[i]) { primes.push_back(i); phi[i] = i - 1; }
for (int p : primes) {
if (i * p > limit) break;
is_composite[i * p] = true;
phi[i * p] = (i % p == 0) ? phi[i] * p : phi[i] * (p - 1);
if (i % p == 0) break;
}
}
}
i64 determinant(int sz) {
int swaps = 0;
for (int i = 1; i <= sz; ++i) {
int pivot = i;
while (pivot <= sz && mat[pivot][i].c0 == 0) ++pivot;
if (pivot > sz) continue;
if (pivot != i) { swap(mat[i], mat[pivot]); swaps ^= 1; }
LinearPoly inv_p = inverse(mat[i][i]);
for (int j = i + 1; j <= sz; ++j) {
LinearPoly factor = mat[j][i] * inv_p;
for (int k = i; k <= sz; ++k) mat[j][k] = mat[j][k] - factor * mat[i][k];
}
}
LinearPoly res = {0, swaps ? MOD - 1 : 1};
for (int i = 1; i <= sz; ++i) res = res * mat[i][i];
return res.c1;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n_nodes >> m_edges;
vector<tuple<int,int,int>> edges(m_edges);
int max_w = 0;
for (auto& [u,v,w] : edges) {
cin >> u >> v >> w;
max_w = max(max_w, w);
for (int d = 1; d * d <= w; ++d) if (w % d == 0) {
edge_cnt[d]++;
if (d * d != w) edge_cnt[w/d]++;
}
}
sieve_phi(max_w);
i64 ans = 0;
for (int d = 1; d <= max_w; ++d) {
if (edge_cnt[d] < n_nodes - 1) continue;
memset(mat, 0, sizeof(mat));
for (auto [u,v,w] : edges) if (w % d == 0) {
LinearPoly p = {w % MOD, 1};
mat[u][u] = mat[u][u] + p; mat[v][v] = mat[v][v] + p;
mat[u][v] = mat[u][v] - p; mat[v][u] = mat[v][u] - p;
}
ans = (ans + phi[d] * determinant(n_nodes - 1)) % MOD;
}
cout << ans << '\n';
return 0;
}
オイラー路構成と最小全域木の融合
必須辺をすべて含む最小コストのパス構築は、次数の偶奇調整と連結性維持の2段階で解決する。まず必須辺を追加し、奇数次数の頂点を座標順にソートして隣接ペアリングすることで、追加コスト $|i-j|$ を最小化する。この操作でグラフが分断される場合、隣接する重要点間の辺のみを候補とした最小全域木（MST）を構築して連結化する。奇数点ペアリング時に間の偶数点も同時に連結処理へ回すことで、MSTの計算量を抑制できる。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2505;
struct DSU {
vector<int> parent;
DSU(int n) : parent(n + 1) { iota(parent.begin(), parent.end(), 0); }
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void unite(int a, int b) { a = find(a); b = find(b); if (a != b) parent[a] = b; }
};
int degree[MAX_N], n, m, start_node;
bool is_key[MAX_N];
vector<pair<int,int>> bucket[MAX_N];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> start_node;
is_key[start_node] = true; degree[start_node]++;
DSU base_dsu(n);
long long base_cost = 0;
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
base_dsu.unite(u, v);
base_cost += abs(u - v);
is_key[u] = is_key[v] = true;
degree[u]++; degree[v]++;
}
for (int target = 1; target <= n; ++target) {
is_key[target] = true; degree[target]++;
vector<int> keys;
for (int i = 1; i <= n; ++i) if (is_key[i]) keys.push_back(i);
DSU cur_dsu = base_dsu;
long long cur_ans = base_cost;
int last_odd = 0;
for (int idx = 0; idx < keys.size(); ++idx) {
int u = keys[idx];
if (degree[u] & 1) {
if (!last_odd) last_odd = idx + 1;
else {
cur_ans += u - keys[last_odd - 1];
for (int k = last_odd - 1; k < idx; ++k) cur_dsu.unite(keys[k], u);
last_odd = 0;
}
}
}
for (int i = 0; i + 1 < keys.size(); ++i)
bucket[keys[i+1] - keys[i]].emplace_back(keys[i], keys[i+1]);
for (int w = 1; w <= n; ++w) {
for (auto [u, v] : bucket[w]) {
if (cur_dsu.find(u) != cur_dsu.find(v)) {
cur_ans += 2LL * w;
cur_dsu.unite(u, v);
}
}
bucket[w].clear();
}
cout << cur_ans << (target == n ? '\n' : ' ');
degree[target]--;
if (!degree[target]) is_key[target] = false;
}
return 0;
}
木構造における比率制約とハッシング
親ノードの値が子ノードの値の和に等しいという制約は、根を基準とした相対比率に還元できる。各ノード $u$ について、根の値を $1$ としたときの理論倍率 $R_u$ をDFSで計算する。実際の重み $W_u$ に対して $W_u \times R_u$ が一定となるノードは、同一の根の値を要求する。この値をハッシュマップで集計し、最頻値を $N$ から引くことで、変更が必要な最小ノード数が得られる。衝突回避のため二重ハッシュまたは64bit整数のペアを用いる。
実装例
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
const int MAX_N = 500005;
const u64 MOD_HASH = 1000000007;
u64 weight[MAX_N], ratio_real[MAX_N], ratio_mod[MAX_N];
vector<int> children[MAX_N];
map<pair<u64, u64>, int> freq;
int n;
void dfs_ratio(int u, int p) {
if (u == 1) { ratio_real[u] = 1; ratio_mod[u] = 1; }
else {
u64 deg = children[p].size();
ratio_real[u] = ratio_real[p] * deg;
ratio_mod[u] = (ratio_mod[p] * deg) % MOD_HASH;
}
freq[{weight[u] * ratio_real[u], (weight[u] * ratio_mod[u]) % MOD_HASH}]++;
for (int v : children[u]) dfs_ratio(v, u);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> weight[i];
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
children[u].push_back(v);
}
dfs_ratio(1, 0);
int max_f = 0;
for (auto& [_, c] : freq) max_f = max(max_f, c);
cout << n - max_f << '\n';
return 0;
}
永続トライ木と優先度付きキューによる区間XOR最大値
区間 $[L, R]$ のXOR和の最大値を上位 $K$ 個抽出する問題では、累積XOR配列 $S_i$ を構築し、$S_i \oplus S_j$ の最大化を永続0-1トライ木で処理する。各右端 $R$ に対して最適な左端 $L$ をトライ木で探索し、結果を優先度付きキューに格納する。キューから最大値を取り出すたびに、探索区間を最適位置で分割して新たな候補をキューに追加する。この手法は区間分割の性質を利用し、$O((N+K)\log (\max A))$ で動作する。
実装例
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAX_N = 500005, BITS = 33;
struct Node { int ch[2], cnt, end_idx; } tree[MAX_N * BITS];
int root[MAX_N], node_cnt;
i64 prefix_xor[MAX_N];
int clone_node(int src) {
int id = ++node_cnt;
tree[id] = tree[src];
return id;
}
int insert(int prev, i64 val, int idx) {
int cur = clone_node(prev);
tree[cur].cnt++;
int p = cur;
for (int b = 31; b >= 0; --b) {
int bit = (val >> b) & 1;
tree[p].ch[bit] = clone_node(tree[prev].ch[bit]);
p = tree[p].ch[bit]; prev = tree[prev].ch[bit];
tree[p].cnt++;
}
tree[p].end_idx = idx;
return cur;
}
pair<i64, int> query_max(int l_root, int r_root, i64 target) {
i64 res = 0;
int u = l_root, v = r_root;
for (int b = 31; b >= 0; --b) {
int want = ((target >> b) & 1) ^ 1;
if (tree[tree[v].ch[want]].cnt - tree[tree[u].ch[want]].cnt > 0) {
res |= (1LL << b);
u = tree[u].ch[want]; v = tree[v].ch[want];
} else {
u = tree[u].ch[want^1]; v = tree[v].ch[want^1];
}
}
return {res, tree[v].end_idx};
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k; cin >> n >> k;
root[0] = insert(0, 0, 0);
for (int i = 1; i <= n; ++i) {
i64 a; cin >> a;
prefix_xor[i] = prefix_xor[i-1] ^ a;
root[i] = insert(root[i-1], prefix_xor[i], i);
}
priority_queue<tuple<i64, int, int, int, int>> pq;
for (int i = 1; i <= n; ++i) {
auto [val, pos] = query_max(root[0], root[i-1], prefix_xor[i]);
pq.emplace(val, 0, i-1, pos, i);
}
i64 total = 0;
while (k--) {
auto [val, l, r, pos, idx] = pq.top(); pq.pop();
total += val;
if (l < pos) {
auto [nv, np] = query_max(root[l], root[pos-1], prefix_xor[idx]);
pq.emplace(nv, l, pos-1, np, idx);
}
if (r > pos) {
auto [nv, np] = query_max(root[pos+1], root[r], prefix_xor[idx]);
pq.emplace(nv, pos+1, r, np, idx);
}
}
cout << total << '\n';
return 0;
}
博弈グラフのトポロジカルソートと環処理
有限状態の二人零和ゲームは、状態をノード、遷移を辺とする有向グラフでモデル化できる。終局状態から逆方向にBFS（トポロジカルソート）を行い、勝敗を確定させる。ある状態から「相手の負け確定状態」へ遷移可能なら自身の勝ち、「自身の勝ち確定状態」へしか遷移できないなら相手の勝ちとなる。環に含まれる状態でも、勝ち確定状態へ到達可能な分岐があれば環を断ち切って勝ちと判定できる。最後まで勝敗が確定しない状態は引き分けとする。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_STATE = 2000005;
struct Edge { int to, next; } edges[MAX_STATE * 5];
int head[MAX_STATE], edge_cnt, in_degree[MAX_STATE];
int result[MAX_STATE], steps[MAX_STATE];
bool visited[MAX_STATE];
char grid[15][15];
int n, m;
inline void add_edge(int u, int v) {
edges[++edge_cnt] = {u, head[v]};
in_degree[u]++;
head[v] = edge_cnt;
}
inline int encode(int turn, int bx, int by, int r1x, int r1y, int r2x, int r2y) {
int id = turn * 1000000 + (bx-1)*10000 + (by-1)*100 + (r1x-1)*10 + (r1y-1); // simplified hash
visited[id] = true;
return id;
}
void solve_case() {
edge_cnt = 0;
memset(head, 0, sizeof(head));
memset(in_degree, 0, sizeof(in_degree));
memset(result, -1, sizeof(result));
memset(visited, 0, sizeof(visited));
cin >> n >> m;
// State generation and graph building omitted for brevity.
// Core logic: reverse BFS from terminal states.
queue<int> q;
for (int i = 0; i < MAX_STATE; ++i) {
if (visited[i] && in_degree[i] == 0) {
if (result[i] == -1) result[i] = (i / 1000000) ^ 1;
q.push(i);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int e = head[u]; e; e = edges[e].next) {
int v = edges[e].to;
if (in_degree[v] == 0) continue;
int turn_v = v / 1000000;
if (turn_v == result[u]) {
result[v] = turn_v;
steps[v] = steps[u] + 1;
in_degree[v] = 0;
q.push(v);
} else {
if (--in_degree[v] == 0) {
steps[v] = steps[u] + 1;
q.push(v);
}
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
while(T--) solve_case();
return 0;
}
次数剥離法と独立集合の同時構築
最小次数が $p$ 以上の部分グラフと、サイズ $q$ の独立集合を同時に構成する問題では、優先度付きキューを用いた次数剥離（Peeling）が有効である。毎回次数最小の頂点 $u$ を取り出し、$p$ を更新する。この過程で $u$ が未訪問であれば独立集合に追加し、隣接頂点を使用済みとしてマークする。剥離順序の性質により、独立集合のサイズは $\lfloor N/(p+1) \rfloor$ 以上となることが保証され、条件を満たす構成が線形時間で得られる。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10005;
vector<int> adj[MAX_N];
int deg[MAX_N];
bool removed[MAX_N], blocked[MAX_N];
void run_solver() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; ++i) {
adj[i].clear(); removed[i] = blocked[i] = false;
}
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
for (int i = 1; i <= n; ++i) {
deg[i] = adj[i].size();
pq.emplace(deg[i], i);
}
vector<int> subgraph, indep_set;
int best_p = 0;
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (removed[u]) continue;
removed[u] = true;
if (d > best_p) { best_p = d; subgraph.clear(); }
subgraph.push_back(u);
if (!blocked[u]) {
indep_set.push_back(u);
for (int v : adj[u]) if (!removed[v]) blocked[v] = true;
}
for (int v : adj[u]) if (!removed[v]) {
deg[v]--;
pq.emplace(deg[v], v);
}
}
cout << subgraph.size(); for(int x:subgraph) cout << ' ' << x; cout << '\n';
cout << indep_set.size(); for(int x:indep_set) cout << ' ' << x; cout << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
while(T--) run_solver();
return 0;
}
差分列による単調増加列の数え上げ
長さ $K$ の単調非減少列 $A$ で $1 \le A_1 \le \dots \le A_K \le N$ を満たすものについて、隣接項の差 $D_i = A_{i+1} - A_i$ を導入する。条件は $D_i \ge 0$ かつ $\sum D_i \le N - A_1$ に変換される。各 $D_i$ が独立に $[0, M]$ の範囲を動く場合、総和の期待値または総数を多項式展開せずに直接計算できる。等差数列の和の公式を適用し、$N \cdot M^{K-1} - M^{K-2}(K-1)\frac{M(M+1)}{2}$ という閉形式に簡約化することで、$O(\log K)$ で解答が得られる。
実装例
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 mod_pow(i64 a, i64 b, i64 m) {
i64 r = 1;
for (; b; b >>= 1, a = a * a % m) if (b & 1) r = r * a % m;
return r;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
i64 n, k, m, mod;
cin >> n >> k >> m >> mod;
if (k == 1) { cout << n % mod << '\n'; return 0; }
n %= mod; m %= mod;
i64 term1 = n * mod_pow(m, k - 1, mod) % mod;
i64 sum_m = m * (m + 1) % mod * ((mod + 1) / 2) % mod;
i64 term2 = mod_pow(m, k - 2, mod) * ((k - 1) % mod) % mod * sum_m % mod;
cout << (term1 - term2 + mod) % mod << '\n';
return 0;
}
遷移コストの漸化式によるビットDP最適化
信号配置の順序決定問題では、状態をビットマスクで表すDPが基本となる。遷移コスト $\text{cost}(S, i)$ は、マスク $S$ に頂点 $i$ を追加する際のコストである。このコストは $S$ の部分マスクから漸化的に計算可能であり、$\text{lowbit}$ を利用して差分更新を行うことで、状態ごとのコスト計算を $O(1)$ に削減できる。ポップカウント順に層別化してDPテーブルを更新すれば、空間計算量を $O(2^N \cdot N)$ から $O(2^N)$ へ圧縮できる。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_M = 23, MAX_S = 1 << 20;
int n, m, k, seq[100005];
int cnt[MAX_M][MAX_M], dp[MAX_S], pos_in_layer[MAX_S];
vector<int> layers[MAX_M];
int cost_table[2][MAX_S / 4][MAX_M];
inline int cost_in(int j, int i) { return k * cnt[i][j] + cnt[j][i]; }
inline int cost_out(int j, int i) { return -cnt[i][j] + k * cnt[j][i]; }
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> k;
for (int i = 0; i < n; ++i) { cin >> seq[i]; seq[i]--; }
for (int i = 1; i < n; ++i) cnt[seq[i-1]][seq[i]]++;
for (int s = 0; s < (1 << m); ++s) {
int pc = __builtin_popcount(s);
layers[pc].push_back(s);
pos_in_layer[s] = layers[pc].size() - 1;
}
int cur = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j) if (i != j)
cost_table[cur][0][i] += cost_out(j, i);
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int sz = 1; sz <= m; ++sz) {
cur ^= 1;
memset(cost_table[cur], 0, sizeof(cost_table[cur]));
for (int mask : layers[sz]) {
int lb = mask & -mask;
int bit = __builtin_ctz(lb);
int prev = mask ^ lb;
int p_idx = pos_in_layer[prev];
for (int i = 0; i < m; ++i) if (!(mask & (1 << i))) {
cost_table[cur][pos_in_layer[mask]][i] =
cost_table[cur^1][p_idx][i] - cost_out(bit, i) + cost_in(bit, i);
}
}
for (int mask : layers[sz]) {
for (int i = 0; i < m; ++i) if (mask & (1 << i)) {
int prev = mask ^ (1 << i);
dp[mask] = min(dp[mask], dp[prev] + sz * cost_table[cur^1][pos_in_layer[prev]][i]);
}
}
}
cout << dp[(1 << m) - 1] << '\n';
return 0;
}
セグメント木上の二分探索と木構造の辞書順最大化
親ノードの値が子ノード以上である制約下で、辞書順最大となる割り当てを求める。各ノード $u$ の部分木サイズ $S_u$ に対し、利用可能な値のうち $S_u$ 番目に大きい値を選択する。選択後、その値以下の利用可能数を $S_u$ 減少させる制約を区間加算で管理する。セグメント木上で区間最小値を維持し、二分探索により条件を満たす最大値を特定する。親の制約解除時は区間加算を逆操作することで、動的な制約管理を実現する。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500005;
int tree_min[MAX_N << 2], tree_tag[MAX_N << 2];
int n, vals[MAX_N], subtree_sz[MAX_N], ans[MAX_N];
double k_ratio;
vector<int> children[MAX_N];
vector<int> sorted_vals;
void apply(int p, int v) { tree_min[p] += v; tree_tag[p] += v; }
void push(int p) { if(tree_tag[p]) { apply(p<<1, tree_tag[p]); apply(p<<1|1, tree_tag[p]); tree_tag[p]=0; } }
void pull(int p) { tree_min[p] = min(tree_min[p<<1], tree_min[p<<1|1]); }
void update(int L, int R, int v, int p=1, int l=1, int r=sorted_vals.size()) {
if (L <= l && r <= R) return apply(p, v);
push(p); int mid = (l+r)>>1;
if (L <= mid) update(L, R, v, p<<1, l, mid);
if (R > mid) update(L, R, v, p<<1|1, mid+1, r);
pull(p);
}
int find_kth(int k, int p=1, int l=1, int r=sorted_vals.size()) {
if (l == r) return (tree_min[p] < k) ? l : l + 1;
push(p); int mid = (l+r)>>1;
if (tree_min[p<<1] < k) return find_kth(k, p<<1, l, mid);
return find_kth(k, p<<1|1, mid+1, r);
}
void dfs_sz(int u) {
subtree_sz[u] = 1;
for (int v : children[u]) { dfs_sz(v); subtree_sz[u] += subtree_sz[v]; }
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k_ratio;
map<int, int> freq;
for (int i = 1; i <= n; ++i) { cin >> vals[i]; freq[vals[i]]++; }
for (auto [v, c] : freq) { sorted_vals.push_back(v); update(sorted_vals.size(), sorted_vals.size(), c); }
for (int i = 1; i <= n; ++i) children[(int)floor(i / k_ratio)].push_back(i);
dfs_sz(0);
for (int i = 1; i <= n; ++i) {
int p = (int)floor(i / k_ratio);
if (p) update(1, ans[p], subtree_sz[i]);
ans[i] = find_kth(subtree_sz[i]) - 1;
update(1, ans[i], -subtree_sz[i]);
cout << sorted_vals[ans[i]-1] << (i==n?'\n':' ');
}
return 0;
}
隣接リストのヒューリスティックマージ
出辺集合が同一の頂点を併合する操作は、DSUと隣接リストのヒューリスティックマージで効率的に処理できる。併合時にサイズが小さい方の隣接リストを大きい方へ移動し、移動先の出辺数が2以上になれば処理キューに追加する。各辺は併合のたびに所属するリストのサイズが少なくとも2倍になるため、同一辺の走査回数は $O(\log N)$ に抑えられる。全体計算量は $O((N+M)\log N)$ となり、重複除去を明示的に行わなくても十分高速である。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200005;
vector<int> out_edges[MAX_N], members[MAX_N];
int dsu_parent[MAX_N], color_id[MAX_N];
bool in_queue[MAX_N];
queue<int> proc_q;
void unite_sets(int a, int b) {
a = dsu_parent[a]; b = dsu_parent[b];
if (a == b) return;
if (members[a].size() > members[b].size()) swap(a, b);
for (int v : members[a]) dsu_parent[v] = b;
members[b].insert(members[b].end(), members[a].begin(), members[a].end());
out_edges[b].insert(out_edges[b].end(), out_edges[a].begin(), out_edges[a].end());
members[a].clear(); out_edges[a].clear();
if (!in_queue[b] && out_edges[b].size() > 1) { proc_q.push(b); in_queue[b] = true; }
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
out_edges[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
dsu_parent[i] = i; members[i].push_back(i);
if (out_edges[i].size() > 1) { proc_q.push(i); in_queue[i] = true; }
}
while (!proc_q.empty()) {
int u = proc_q.front(); proc_q.pop(); in_queue[u] = false;
for (size_t i = 1; i < out_edges[u].size(); ++i) unite_sets(out_edges[u][0], out_edges[u][i]);
}
int colors = 0;
for (int i = 1; i <= n; ++i) {
int root = dsu_parent[i];
if (!color_id[root]) color_id[root] = ++colors;
}
for (int i = 1; i <= n; ++i) cout << color_id[dsu_parent[i]] << '\n';
return 0;
}
部分集合包除原理による文字列一致数え上げ
長さ4の文字列ペアについて、ちょうど $d$ 箇所で異なる組の数を求める。まず、特定の位置集合 $T$ をワイルドカード化した場合の一致ペア数 $f(T)$ をマップで集計する。$f(T)$ は「$T$ に含まれる位置以外で一致するペア数」を表す。部分集合包除原理（またはメビウス反転）を適用し、$g(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|} f(T)$ と計算することで、正確に $S$ の位置で異なるペア数が得られる。計算量は $O(N \cdot 2^L + 3^L)$ （$L=4$）で十分小さい。
実装例
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int n, target_diff;
string strs[50005];
i64 f[16], g[16];
i64 count_matches(int mask) {
map<string, int> freq;
string tmp;
for (int i = 0; i < n; ++i) {
tmp = strs[i];
for (int b = 0; b < 4; ++b) if (mask >> b & 1) tmp[b] = '?';
freq[tmp]++;
}
i64 res = 0;
for (auto [_, c] : freq) res += (i64)c * (c - 1) / 2;
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> target_diff;
for (int i = 0; i < n; ++i) cin >> strs[i];
for (int m = 0; m < 16; ++m) f[m] = count_matches(m);
i64 ans = 0;
for (int m = 0; m < 16; ++m) {
for (int s = m; ; s = (s - 1) & m) {
int diff_bits = __builtin_popcount(m ^ s);
g[m] += (diff_bits & 1 ? -1 : 1) * f[s];
if (s == 0) break;
}
if (__builtin_popcount(m) == target_diff) ans += g[m];
}
cout << ans << '\n';
return 0;
}
二分探索と木DPによる予算配分問題
完全二分木において、根から葉へのパスの最小値を辞書順最大化する問題。答えを二分探索し、チェック関数内で木DPを実行する。各ノードで「左部分木のコスト + min(辺重み, 右部分木のコスト)」を計算し、根のコストが予算 $K$ 以下か判定する。値が確定したら、その葉から根へ遡りながら残予算を再分配する。右子へ進む場合は親の辺重みと左子コストの大小関係に応じて予算を補正し、部分問題へ再帰する。
実装例
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAX_N = 200005;
const i64 INF = 1e18;
i64 dp_cost[MAX_N], weight[MAX_N];
int n, ans_seq[MAX_N], seq_len;
i64 budget;
bool is_leaf(int u) { return u >= (1 << n); }
void compute_dp(int u, i64 threshold) {
if (is_leaf(u)) { dp_cost[u] = (weight[u] <= threshold ? INF : 0); return; }
compute_dp(u << 1, threshold);
compute_dp(u << 1 | 1, threshold);
dp_cost[u] = dp_cost[u << 1] + min(dp_cost[u << 1 | 1], weight[u]);
}
void solve_tree(int u, int depth) {
if (is_leaf(u)) { ans_seq[++seq_len] = weight[u]; return; }
vector<i64> candidates;
int range = 1 << (n - depth + 1);
for (int i = 0; i < range; ++i) candidates.push_back(weight[(u << (n - depth + 1)) + i]);
sort(candidates.begin(), candidates.end());
int l = 0, r = candidates.size() - 1, best = -1;
while (l <= r) {
int mid = (l + r) >> 1;
compute_dp(u, candidates[mid]);
if (dp_cost[u] <= budget) { best = mid; l = mid + 1; }
else r = mid - 1;
}
i64 chosen = candidates[best];
ans_seq[++seq_len] = chosen;
compute_dp(u, chosen);
budget -= dp_cost[u];
int leaf_pos = -1;
for (int i = 0; i < range; ++i) if (weight[(u << (n - depth + 1)) + i] == chosen) { leaf_pos = (u << (n - depth + 1)) + i; break; }
for (int cur = leaf_pos; cur != u; cur >>= 1) {
if (cur & 1) budget += dp_cost[cur ^ 1];
else {
if (dp_cost[cur >> 1] == dp_cost[cur] + dp_cost[cur ^ 1]) budget += dp_cost[cur ^ 1];
else if (dp_cost[cur] + dp_cost[cur ^ 1] - dp_cost[cur >> 1] <= budget) budget += weight[cur >> 1];
}
solve_tree(cur ^ 1, depth + 1);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
while (T--) {
cin >> n >> budget; seq_len = 0;
for (int i = 1; i < (1 << (n + 1)); ++i) cin >> weight[i];
solve_tree(1, 1);
for (int i = 1; i <= seq_len; ++i) cout << ans_seq[i] << (i==seq_len?'\n':' ');
}
return 0;
}
木上パス交差の数え上げと差分法
木上の2パスが辺を共有するかを判定するには、LCAと差分配列を組み合わせる。パス $(u, v)$ を $u \to \text{LCA}$ と $v \to \text{LCA}$ に分割し、各辺に $+1$ を加算する。全パス処理後、DFSで根方向へ累積和を計算すると、各辺を通過するパス数が得られる。交差するパス対の総数は、各辺について $\binom{\text{count}}{2}$ を合計し、LCAが同一の場合の重複計上を補正することで正確に算出できる。計算量は $O((N+M)\log N)$。
実装例
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAX_N = 200005;
vector<int> tree_adj[MAX_N];
int depth[MAX_N], up[MAX_N][20], diff[MAX_N];
int path_u[MAX_N], path_v[MAX_N], path_lca[MAX_N];
map<pair<int,int>, int> lca_freq;
void dfs_init(int u, int p) {
up[u][0] = p; depth[u] = depth[p] + 1;
for (int i = 1; i < 20; ++i) up[u][i] = up[up[u][i-1]][i-1];
for (int v : tree_adj[u]) if (v != p) dfs_init(v, u);
}
int get_lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int i = 19; i >= 0; --i) if (depth[up[a][i]] >= depth[b]) a = up[a][i];
if (a == b) return a;
for (int i = 19; i >= 0; --i) if (up[a][i] != up[b][i]) { a = up[a][i]; b = up[b][i]; }
return up[a][0];
}
int lift(int u, int target_depth) {
for (int i = 19; i >= 0; --i) if (depth[up[u][i]] > target_depth) u = up[u][i];
return u;
}
void dfs_accum(int u, int p) {
for (int v : tree_adj[u]) if (v != p) { dfs_accum(v, u); diff[u] += diff[v]; }
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
tree_adj[u].push_back(v); tree_adj[v].push_back(u);
}
dfs_init(1, 0);
for (int i = 0; i < m; ++i) {
cin >> path_u[i] >> path_v[i];
path_lca[i] = get_lca(path_u[i], path_v[i]);
diff[path_u[i]]++; diff[path_v[i]]++;
diff[path_lca[i]] -= 2;
lca_freq[{min(path_u[i], path_v[i]), max(path_u[i], path_v[i])}]++; // simplified key
}
dfs_accum(1, 0);
i64 ans = 0;
for (int i = 2; i <= n; ++i) ans += (i64)diff[i] * (diff[i] - 1) / 2;
for (auto [_, c] : lca_freq) ans -= (i64)c * (c - 1) / 2;
cout << ans << '\n';
return 0;
}
輪郭線DPとミニマックス法
グリッド上の交互着手ゲームは、盤面の境界形状をビットマスクで表現する輪郭線DP（Broken Profile DP）で解ける。右上から左下への境界線を $0$（横）と $1$（縦）で符号化し、状態遷移は $01 \to 10$ の反転に対応する。各状態で先手はスコア最大化、後手は最小化を選択するミニマックス法をメモ化再帰で実装する。状態数は $\binom{N+M}{N}$ 程度に抑えられ、$O(2^{N+M})$ で最適手が求まる。
実装例
#include <bits/stdc++.h>
using namespace std;
const int MAX_S = 1 << 20;
const int INF_VAL = 1e9;
int grid_a[12][12], grid_b[12][12];
int memo[MAX_S];
int rows, cols;
int minimax(int mask, int turn) {
if (memo[mask] != INF_VAL) return memo[mask];
memo[mask] = turn ? INF_VAL : -INF_VAL;
int r = 0, c = cols;
for (int i = rows + cols - 1; i > 0; --i) {
if (mask >> i & 1) r++;
else c--;
if (!((mask >> i) & 1) && ((mask >> (i - 1)) & 1)) {
int next_mask = mask ^ (1 << i) ^ (1 << (i - 1));
int val = minimax(next_mask, turn ^ 1);
if (!turn) memo[mask] = max(memo[mask], val + grid_a[r][c]);
else memo[mask] = min(memo[mask], val - grid_b[r][c]);
}
}
return memo[mask];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> rows >> cols;
for (int i = 0; i < rows; ++i) for (int j = 0; j < cols; ++j) cin >> grid_a[i][j];
for (int i = 0; i < rows; ++i) for (int j = 0; j < cols; ++j) cin >> grid_b[i][j];
fill(memo, memo + MAX_S, INF_VAL);
int start_mask = ((1 << rows) - 1) << cols;
memo[start_mask] = 0;
cout << minimax((1 << rows) - 1, 0) << '\n';
return 0;
}