経路圧縮 + size 併合。連結判定 / グループ分け / Kruskal。union は併合したら true。
init 0 1 2 3 4 (各自が根) u(0,1) 0──1 2 3 4 u(2,3) 0──1 2──3 4 u(1,2) 0──1──2──3 4 same(0,3)=T size=4 find: 根まで辿り親を直付け(経路圧縮)
class UnionFind {
int[] par, sz;
UnionFind(int n) {
par = new int[n]; sz = new int[n];
for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; }
}
int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); }
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (sz[ra] < sz[rb]) { int t = ra; ra = rb; rb = t; }
par[rb] = ra; sz[ra] += sz[rb]; return true;
}
boolean same(int a, int b) { return find(a) == find(b); }
int size(int x) { return sz[find(x)]; }
}
点加算・前方和を O(log N)。転倒数は「右より小さい既出要素の総数」で求まる。
idx は (i & -i) 幅を管理 add(i,v): x += x & -x で上る sum(i): x -= x & -x で下り a[0..i] の和 区間 [l,r] = sum(r) - sum(l-1) 転倒数: 後ろから add しつつ sum(a[i]-1)
class BIT {
int n; long[] t;
BIT(int n) { this.n = n; t = new long[n + 1]; }
void add(int i, long v) { for (int x = i + 1; x <= n; x += x & -x) t[x] += v; }
long sum(int i) { // a[0..i]
long s = 0;
for (int x = i + 1; x > 0; x -= x & -x) s += t[x];
return s;
}
}
static long inversions(int[] a) {
int mx = 0; for (int x : a) mx = Math.max(mx, x);
BIT bit = new BIT(mx + 1); long res = 0;
for (int i = a.length - 1; i >= 0; i--) {
if (a[i] > 0) res += bit.sum(a[i] - 1);
bit.add(a[i], 1);
}
return res;
}
優先度キューで未確定のうち最小距離の頂点を順に確定。負辺があると使えない(→Bellman-Ford)。
(0)──5──▶(1) start = 0 │ ▲ init dist=[0, ∞, ∞] 2 1 pop0 1=5 2=2 →[0,5,2] ▼ │ pop2 1=2+1=3 →[0,3,2] (2)───────┘ pop1 settled 0▶1:5 0▶2:2 2▶1:1 ans [0,3,2]
// g[v] = list of {to, cost} static long[] dijkstra(List<long[]>[] g, int s) { long[] dist = new long[g.length]; Arrays.fill(dist, Long.MAX_VALUE / 4); dist[s] = 0; PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0])); pq.add(new long[]{0, s}); while (!pq.isEmpty()) { long[] t = pq.poll(); long d = t[0]; int v = (int) t[1]; if (d > dist[v]) continue; // 古い距離は捨てる for (long[] e : g[v]) { int to = (int) e[0]; long c = e[1]; if (d + c < dist[to]) { dist[to] = d + c; pq.add(new long[]{dist[to], to}); } } } return dist; }
4 近傍を距離 +1 で push。壁 # と訪問済みは skip。最短手数 = 到達時の dist。
grid (#=壁) dist from S S . . # 0 1 2 # . # . . 1 # 3 4 . . . G 2 3 4 5 4近傍↑↓←→を BFS → G = 5
static int[][] gridBfs(char[][] grid, int sy, int sx) {
int h = grid.length, w = grid[0].length;
int[][] dist = new int[h][w];
for (int[] row : dist) Arrays.fill(row, -1);
int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1};
dist[sy][sx] = 0;
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[]{sy, sx});
while (!q.isEmpty()) {
int[] c = q.poll(); int y = c[0], x = c[1];
for (int d = 0; d < 4; d++) {
int ny = y + dy[d], nx = x + dx[d];
if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
if (grid[ny][nx] == '#' || dist[ny][nx] != -1) continue;
dist[ny][nx] = dist[y][x] + 1;
q.add(new int[]{ny, nx});
}
}
return dist;
}
答えの単調性(F..FT..T)で二分。ok=満たす側, ng=満たさない側の初期値を渡す。
pred 単調: F F F T T T
ng ──┬── ok m=(ok+ng)/2
lowerBound: a[i] >= x の最小 i
upperBound: a[i] > x の最小 i
[1 3 3 5 7] x=3 → lower=1 upper=3 個数=2
// pred(ok)=true, pred(ng)=false となる初期値を渡す static long bisect(long ok, long ng, java.util.function.LongPredicate pred) { while (Math.abs(ok - ng) > 1) { long m = ok + (ng - ok) / 2; // 溢れ対策 if (pred.test(m)) ok = m; else ng = m; } return ok; } static int lowerBound(long[] a, long x) { // a[i] >= x の最小 i int lo = -1, hi = a.length; while (hi - lo > 1) { int m = (lo + hi) >>> 1; if (a[m] >= x) hi = m; else lo = m; } return hi; } static int upperBound(long[] a, long x) { // a[i] > x の最小 i int lo = -1, hi = a.length; while (hi - lo > 1) { int m = (lo + hi) >>> 1; if (a[m] > x) hi = m; else lo = m; } return hi; }
累積和で区間和を O(1)。逆操作のいもす法は「区間加算を大量 → 最後に復元」。
a = [1 2 3 4 5]
sum = [0 1 3 6 10 15] (1個ずれ)
区間 [l,r) = sum[r] - sum[l] [1,4)=9
いもす: add(l,r,v)= diff[l]+=v; diff[r]-=v
最後に累積和で復元
static long[] prefixSum(long[] a) { // s[i]=a[0..i-1]; [l,r)=s[r]-s[l]
long[] s = new long[a.length + 1];
for (int i = 0; i < a.length; i++) s[i + 1] = s[i] + a[i];
return s;
}
class Imos {
long[] diff;
Imos(int n) { diff = new long[n + 1]; }
void add(int l, int r, long v) { diff[l] += v; diff[r] -= v; } // a[l..r-1]+=v
long[] build() {
long[] res = new long[diff.length - 1]; long acc = 0;
for (int i = 0; i < res.length; i++) { acc += diff[i]; res[i] = acc; }
return res;
}
}
modpow は繰返し二乗法。modinv はフェルマー(m素数で a^(m-2))。nCr は階乗逆元の前計算。
modpow(a,e): e を 2 進で繰返し二乗 a^13 = a^8 · a^4 · a^1 (13 = 1101) modinv(a) = a^(m-2) mod m (m 素数) nCr = fact[n]·inv[r]·inv[n-r] 前計算 O(n)
static final long MOD = 998244353L; // or 1_000_000_007L static long modpow(long a, long e, long m) { long b = a % m, r = 1; while (e > 0) { if ((e & 1) == 1) r = r * b % m; b = b * b % m; e >>= 1; } return r; } static long modinv(long a, long m) { return modpow(a, m - 2, m); } // m は素数 class Comb { long m; long[] fact, inv; Comb(int maxN, long m) { this.m = m; fact = new long[maxN + 1]; inv = new long[maxN + 1]; fact[0] = 1; for (int i = 1; i <= maxN; i++) fact[i] = fact[i - 1] * i % m; inv[maxN] = modpow(fact[maxN], m - 2, m); for (int i = maxN; i >= 1; i--) inv[i - 1] = inv[i] * i % m; } long nCr(int n, int r) { if (r < 0 || r > n) return 0; return fact[n] * inv[r] % m * inv[n - r] % m; } }
isPrime[i] を一括計算。i*i から消すのがポイント。約数/素因数のクエリが多いなら最小素因数表へ。
2 3 4 5 6 7 8 9 10 ... 2の倍数除外 → 3の → 5の → ... 消す開始は i*i (それ未満は既出) 残り = 素数 例) ~20: 2 3 5 7 11 13 17 19
static boolean[] sieve(int n) { // isPrime[i]
boolean[] p = new boolean[n + 1];
Arrays.fill(p, 2, n + 1, true);
for (int i = 2; (long) i * i <= n; i++)
if (p[i]) for (int j = i * i; j <= n; j += i) p[j] = false;
return p;
}
gcd は互除法。lcm は先に割って溢れ防止。extGcd は ax+by=gcd の (x,y) も求める(mod 逆元・不定方程式)。
gcd(a,b) = gcd(b, a%b), gcd(a,0)=a gcd(12,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)=6 lcm = a / gcd · b (先に割る) extGcd: ax + by = gcd の x,y も返す
static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
static long lcm(long a, long b) { return a / gcd(a, b) * b; }
// ax + by = gcd; 返り値 {g, x, y}
static long[] extGcd(long a, long b) {
if (b == 0) return new long[]{a, 1, 0};
long[] r = extGcd(b, a % b);
return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
}
容量ごとの最大価値。0-1 は重さを逆順ループ(各品物1回)。部分和は価値の代わりに可否を持つ。
品物(w,v), 容量cap. dp[w]=容量wの最大価値 for 品物: for w = cap .. wi (逆順!): dp[w] = max(dp[w], dp[w-wi] + vi) 逆順=各品物1回。正順だと無制限個 部分和: dp[s] = s を作れるか (bool)
// 0-1: 各品物 1 個まで static long knapsack01(int[] w, long[] v, int cap) { long[] dp = new long[cap + 1]; for (int i = 0; i < w.length; i++) for (int j = cap; j >= w[i]; j--) // 重さ逆順 dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); return dp[cap]; } static boolean subsetSum(int[] a, int target) { boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int x : a) for (int s = target; s >= x; s--) if (dp[s - x]) dp[s] = true; return dp[target]; }
非再帰・抽象化。op はモノイド(結合的 + 単位元 unit)。min/max/和などを区間で。
[5 3 7 1 9] を min セグ木に
[1] ← 全体 min
[3] [9]
[3][7] [9][∞]
[5][3][7][1][9]
update(i,v): 葉→根 query[l,r): 両端から畳む
// op はモノイド(結合的 + 単位元 unit). 例: min/max/和 class SegTree<T> { int size = 1; T unit; java.util.function.BinaryOperator<T> op; Object[] t; SegTree(int n, T unit, java.util.function.BinaryOperator<T> op) { this.unit = unit; this.op = op; while (size < n) size *= 2; t = new Object[2 * size]; Arrays.fill(t, unit); } @SuppressWarnings("unchecked") T at(int i) { return (T) t[i]; } void update(int i, T v) { int x = i + size; t[x] = v; for (x >>= 1; x >= 1; x >>= 1) t[x] = op.apply(at(2 * x), at(2 * x + 1)); } T query(int l, int r) { // [l, r) T res = unit; int lo = l + size, hi = r + size; while (lo < hi) { if ((lo & 1) == 1) res = op.apply(res, at(lo++)); if ((hi & 1) == 1) res = op.apply(res, at(--hi)); lo >>= 1; hi >>= 1; } return res; } }
値の大小を保ったまま 0..k-1 に詰める。BIT/セグ木に乗せる前処理、値の種類数。
a = [100 50 100 7] sort & distinct = [7 50 100] (→ 0 1 2) comp = [ 2 1 2 0] 逆引き: 圧縮値 i → vals[i] が元の値
// 値の大小を保ち 0..k-1 に圧縮。圧縮後配列を返す(元の値は sorted distinct)
static int[] compress(long[] a) {
long[] vals = Arrays.stream(a).distinct().sorted().toArray();
HashMap<Long, Integer> idx = new HashMap<>();
for (int i = 0; i < vals.length; i++) idx.put(vals[i], i);
int[] res = new int[a.length];
for (int i = 0; i < a.length; i++) res[i] = idx.get(a[i]);
return res;
}
全辺を n-1 回緩和。負辺 OK。n 回目でも更新できれば負閉路。Dijkstra が使えない時に。
全辺を n-1 回 緩和(relax) dist[t] = min(dist[t], dist[f] + cost) n 回目でも更新 → 負閉路あり 始点から到達する負閉路だけが検出対象
// edges: each {from, to, cost}. 負閉路があれば null static long[] bellmanFord(int n, long[][] edges, int s) { long INF = Long.MAX_VALUE / 4; long[] dist = new long[n]; Arrays.fill(dist, INF); dist[s] = 0; for (int it = 0; it < n - 1; it++) for (long[] e : edges) { int f = (int) e[0], t = (int) e[1]; if (dist[f] != INF && dist[f] + e[2] < dist[t]) dist[t] = dist[f] + e[2]; } for (long[] e : edges) { // 負閉路 int f = (int) e[0], t = (int) e[1]; if (dist[f] != INF && dist[f] + e[2] < dist[t]) return null; } return dist; }
中継点 k を全部試す DP。V≤500 まで。負辺 OK(負閉路は dist[v][v]<0 で検出)。
中継点 k = 0..n-1 を全部試す dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 隣接行列(辺なし=INF, 対角0)を渡し in-place 更新 ループ順は k, i, j の順 (k が最外)
// 全点対最短路。dist は隣接行列(辺なし=INF, 対角0) を in-place 更新
static void warshallFloyd(long[][] dist) {
long INF = Long.MAX_VALUE / 4; int n = dist.length;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++) {
if (dist[i][k] == INF) continue;
for (int j = 0; j < n; j++)
if (dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
入次数 0 をキューから取り出し、辺を消しながら並べる。全頂点出せなければ閉路。
入次数0をキューへ → 取り出しつつ出る辺を消す (消した先の入次数が0になったら追加) 全頂点出れば順序確定 / 出きらねば閉路 辞書順最小が要るなら queue → 優先度付き
// Kahn 法。g: 隣接リスト(有向). 閉路があれば null
static List<Integer> topoSort(List<Integer>[] g) {
int n = g.length; int[] indeg = new int[n];
for (int v = 0; v < n; v++) for (int to : g[v]) indeg[to]++;
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int v = q.poll(); order.add(v);
for (int to : g[v]) if (--indeg[to] == 0) q.add(to);
}
return order.size() == n ? order : null;
}
辺を cost 昇順に見て、端点が別グループなら採用(Union-Find)。全部つなぐ最小コスト。
辺を cost 昇順にソート 端点が別グループなら採用(UnionFind で併合) 採用辺が n-1 本で全域木 完成 ※ Union-Find のスニペットが必要
// edges: each {cost, u, v}. UnionFind 必要。非連結なら -1
static long kruskal(int n, long[][] edges) {
Arrays.sort(edges, (a, b) -> Long.compare(a[0], b[0]));
UnionFind uf = new UnionFind(n); long total = 0; int used = 0;
for (long[] e : edges)
if (uf.union((int) e[1], (int) e[2])) { total += e[0]; used++; }
return used == n - 1 ? total : -1;
}
窓 [left,right] を右に伸ばし、条件を破ったら左を詰める。単調性が前提(非負配列など)。
[left,right] 窓を右へ伸ばし、破ったら左を詰める 和<=k 最大長: 超えたら left++ で縮める 和>=k 個数: 初めて満たせば右端以降は全部OK 単調性(伸ばすと悪化/縮めると改善)が必要
// 和が k 以下の連続区間の最大長 (a は非負) static int longestAtMost(long[] a, long k) { int best = 0, left = 0; long sum = 0; for (int right = 0; right < a.length; right++) { sum += a[right]; while (sum > k) { sum -= a[left]; left++; } best = Math.max(best, right - left + 1); } return best; } // 和が k 以上の連続区間の総数 (a は非負) static long countAtLeast(long[] a, long k) { int n = a.length, right = 0; long count = 0, sum = 0; for (int left = 0; left < n; left++) { while (right < n && sum < k) { sum += a[right]; right++; } if (sum < k) break; count += n - right + 1; sum -= a[left]; } return count; }
bit 全探索で選ぶ/選ばない 2ⁿ 通り(n≤20)。next permutation で全順列(n≤10)。
bit全探索: mask 0..2^n-1, i bit目で i 番目採用 for mask: for i: if (mask>>i & 1) use i 順列: 末尾から増加位置を探し交換→反転 012 021 102 120 201 210 (n! 通り)
// bit 全探索: for (int mask = 0; mask < (1<<n); mask++) { (mask>>i & 1) ... } // 辞書順で次の順列に in-place。なければ false static boolean nextPermutation(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; if (i < 0) return false; int j = a.length - 1; while (a[j] <= a[i]) j--; int t = a[i]; a[i] = a[j]; a[j] = t; for (int lo = i + 1, hi = a.length - 1; lo < hi; lo++, hi--) { int s = a[lo]; a[lo] = a[hi]; a[hi] = s; } return true; }
LIS は末尾最小値を二分探索で更新。LCS・編集距離は 2 次元 DP 表。
LIS: tail[k] = 長さ k+1 の増加列の末尾の最小値 各 x を lower_bound で 置換 or 追加 → 長さが答え LCS/編集距離: dp[i][j] を表で 一致なら \+1 / 不一致は周囲の最小から
// LIS (最長増加部分列) O(N log N) static int lis(int[] a) { ArrayList<Integer> tail = new ArrayList<>(); for (int x : a) { int p = Collections.binarySearch(tail, x); if (p < 0) p = -(p + 1); if (p == tail.size()) tail.add(x); else tail.set(p, x); } return tail.size(); } // LCS (最長共通部分列) O(NM) static int lcs(String s, String t) { int n = s.length(), m = t.length(); int[][] dp = new int[n + 1][m + 1]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) dp[i + 1][j + 1] = s.charAt(i) == t.charAt(j) ? dp[i][j] + 1 : Math.max(dp[i][j + 1], dp[i + 1][j]); return dp[n][m]; } // 編集距離 (Levenshtein) O(NM) static int editDistance(String s, String t) { int n = s.length(), m = t.length(); int[][] dp = new int[n + 1][m + 1]; for (int i = 0; i <= n; i++) dp[i][0] = i; for (int j = 0; j <= m; j++) dp[0][j] = j; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { int c = s.charAt(i - 1) == t.charAt(j - 1) ? 0 : 1; dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + c); } return dp[n][m]; }
p=2 から割り続ける素因数分解。約数は d と n/d をペアで集める。素数判定も同様。
factorize: p=2.. (p*p<=v) の間割り続ける 残った v>1 は最大の素因数 360 = 2^3 · 3^2 · 5 divisors: d*d<=n, n%d==0 で d と n/d を集める 12 の約数 = 1 2 3 4 6 12
// 素因数分解 {素因数: 指数} O(√N) static Map<Long, Integer> factorize(long n) { Map<Long, Integer> res = new LinkedHashMap<>(); long v = n; for (long p = 2; p * p <= v; p++) while (v % p == 0) { res.merge(p, 1, Integer::sum); v /= p; } if (v > 1) res.merge(v, 1, Integer::sum); return res; } // 約数列挙 (ソート済み) O(√N) static List<Long> divisors(long n) { List<Long> small = new ArrayList<>(), large = new ArrayList<>(); for (long d = 1; d * d <= n; d++) if (n % d == 0) { small.add(d); if (d != n / d) large.add(n / d); } for (int i = large.size() - 1; i >= 0; i--) small.add(large.get(i)); return small; } static boolean isPrime(long n) { if (n < 2) return false; for (long d = 2; d * d <= n; d++) if (n % d == 0) return false; return true; }
訪問済み集合を bit で持つ DP。N≤16 程度。全頂点を回って戻る最小コスト等。
dp[S][v] = 訪問済み集合 S で今 v にいる最小コスト
0 から出発: dp[{0}][0] = 0
S に未訪問 to を足して遷移
最後に全訪問+0へ戻る最小。N<=16 (2^16·16^2)
// bitDP 巡回セールスマン O(2^N N^2). N<=16
static long tsp(long[][] dist) {
long INF = Long.MAX_VALUE / 4; int n = dist.length, full = 1 << n;
long[][] dp = new long[full][n];
for (long[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0;
for (int s = 0; s < full; s++) for (int v = 0; v < n; v++) {
if (dp[s][v] == INF) continue;
for (int to = 0; to < n; to++) {
if ((s >> to & 1) == 1) continue;
int ns = s | (1 << to);
if (dp[s][v] + dist[v][to] < dp[ns][to]) dp[ns][to] = dp[s][v] + dist[v][to];
}
}
long res = INF;
for (int v = 1; v < n; v++)
if (dp[full - 1][v] != INF) res = Math.min(res, dp[full - 1][v] + dist[v][0]);
return res;
}
文字列を多項式ハッシュに。mod 2⁶¹-1 で衝突回避。部分文字列の一致判定が O(1)。
h[i] = s[0..i-1] の多項式ハッシュ (base 進数) get(l,r) = h[r] - h[l]·base^(r-l) (mod 2^61-1) 部分文字列が等しい ⇔ ハッシュ一致 (O(1)) base はランダム、mod は 2^61-1 が安全
// ローリングハッシュ (mod 2^61-1)。部分文字列比較 O(1) class RollingHash { static final long MOD = (1L << 61) - 1; static final long BASE = 1_000_003L; long[] h, pw; RollingHash(String s) { int n = s.length(); h = new long[n + 1]; pw = new long[n + 1]; pw[0] = 1; for (int i = 0; i < n; i++) { h[i + 1] = mul(h[i], BASE) + s.charAt(i); if (h[i + 1] >= MOD) h[i + 1] -= MOD; pw[i + 1] = mul(pw[i], BASE); } } static long mul(long a, long b) { // a*b mod (2^61-1) long hi = Math.multiplyHigh(a, b), lo = a * b; long r = (hi << 3) + (lo >>> 61) + (lo & MOD); if (r >= MOD) r -= MOD; return r; } long get(int l, int r) { // [l, r) long res = h[r] - mul(h[l], pw[r - l]); if (res < 0) res += MOD; return res; } }
ccw(外積で回転方向)が基礎。線分交差・凸包・面積。誤差は EPS で比較、整数なら Long で。
ccw(a,b,c): 外積の符号で回転方向 1:反時計 -1:時計 0/±2:一直線上 線分交差: 互いに相手を挟む ⇔ 交差 凸包(Andrew): x昇順→下側→上側 cross<EPS で pop (左折だけ残す=反時計回り)
static final double EPS = 1e-9;
static double[] sub(double[] a, double[] b) { return new double[]{a[0]-b[0], a[1]-b[1]}; }
static double cross(double[] a, double[] b) { return a[0]*b[1] - a[1]*b[0]; }
static double dot(double[] a, double[] b) { return a[0]*b[0] + a[1]*b[1]; }
// 1:反時計 -1:時計 2:c-a-b -2:a-b-c 0:線分ab上
static int ccw(double[] a, double[] b, double[] c) {
double[] ab = sub(b, a), ac = sub(c, a);
double cr = cross(ab, ac);
if (cr > EPS) return 1;
if (cr < -EPS) return -1;
if (dot(ab, ac) < -EPS) return 2;
if (dot(ab, ab) < dot(ac, ac) - EPS) return -2;
return 0;
}
static boolean segIntersect(double[] a, double[] b, double[] c, double[] d) {
return ccw(a,b,c)*ccw(a,b,d) <= 0 && ccw(c,d,a)*ccw(c,d,b) <= 0;
}
// 凸包(反時計回り) O(N log N)
static List<double[]> convexHull(List<double[]> ps) {
List<double[]> s = new ArrayList<>(ps);
s.sort((p,q) -> p[0]!=q[0] ? Double.compare(p[0],q[0]) : Double.compare(p[1],q[1]));
int n = s.size();
if (n <= 2) return s;
double[][] h = new double[2 * n][]; int k = 0;
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(sub(h[k-1], h[k-2]), sub(s.get(i), h[k-1])) < EPS) k--;
h[k++] = s.get(i);
}
for (int i = n - 2, lower = k + 1; i >= 0; i--) {
while (k >= lower && cross(sub(h[k-1], h[k-2]), sub(s.get(i), h[k-1])) < EPS) k--;
h[k++] = s.get(i);
}
List<double[]> res = new ArrayList<>();
for (int i = 0; i < k - 1; i++) res.add(h[i]);
return res;
}
static double polygonArea(List<double[]> poly) { // 反時計回りで正
double s = 0; int n = poly.size();
for (int i = 0; i < n; i++) s += cross(poly.get(i), poly.get((i + 1) % n));
return s / 2;
}
左頂点から増加路を DFS で探す。割り当て問題、最大マッチング = 最小頂点被覆(König)。
左→右の辺。各左頂点から増加路を DFS 右が空 or その相手を押し出せれば マッチ確定 最大マッチング数 = 最小頂点被覆 (König の定理) used[] を頂点ごとにリセットして探索
// 増加路 DFS O(VE)。左 n, 右 m
class BipartiteMatching {
int n, m; List<Integer>[] g; int[] matchR;
@SuppressWarnings("unchecked")
BipartiteMatching(int n, int m) {
this.n = n; this.m = m;
g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
matchR = new int[m]; Arrays.fill(matchR, -1);
}
void addEdge(int u, int v) { g[u].add(v); }
boolean dfs(int u, boolean[] used) {
for (int v : g[u]) {
if (used[v]) continue;
used[v] = true;
if (matchR[v] == -1 || dfs(matchR[v], used)) { matchR[v] = u; return true; }
}
return false;
}
int solve() {
int res = 0;
for (int u = 0; u < n; u++) if (dfs(u, new boolean[m])) res++;
return res;
}
}
BFS でレベル分けし、レベル順に DFS で流す。最大流・最小カット・二部マッチングに。
BFS でレベル(最短距離)を付ける → レベルが増える辺だけ DFS で流す 逆辺(rev)に流量を戻し増加路を表現。繰り返す 最大流 = 最小カット。「同時不可の最小除去」に
// Dinic 最大流 O(V^2 E)。各辺 {to, cap, rev}
class Dinic {
int n; int[] level, iter; List<long[]>[] g;
@SuppressWarnings("unchecked")
Dinic(int n) {
this.n = n; g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
level = new int[n]; iter = new int[n];
}
void addEdge(int from, int to, long cap) {
g[from].add(new long[]{to, cap, g[to].size()});
g[to].add(new long[]{from, 0, g[from].size() - 1});
}
void bfs(int s) {
Arrays.fill(level, -1); level[s] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>(); q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
for (long[] e : g[v])
if (e[1] > 0 && level[(int) e[0]] < 0) { level[(int) e[0]] = level[v] + 1; q.add((int) e[0]); }
}
}
long dfs(int v, int t, long f) {
if (v == t) return f;
for (; iter[v] < g[v].size(); iter[v]++) {
long[] e = g[v].get(iter[v]); int to = (int) e[0];
if (e[1] > 0 && level[v] < level[to]) {
long d = dfs(to, t, Math.min(f, e[1]));
if (d > 0) { e[1] -= d; g[to].get((int) e[2])[1] += d; return d; }
}
}
return 0;
}
long maxFlow(int s, int t) {
long flow = 0;
while (true) {
bfs(s);
if (level[t] < 0) return flow;
Arrays.fill(iter, 0);
long f;
while ((f = dfs(s, t, Long.MAX_VALUE / 4)) > 0) flow += f;
}
}
}