AtCoder NoviStepsを埋めてみる(33) 最小費用流問題 負のコストが設定できる自作クラスの続きです。今回はセグメント木（segment tree）です。
セグメント木は「1 点更新」と「区間取得」を O(log N) の計算量で実行できるデータ構造です。区間最大値、区間最大値、区間和などを求める処理を高速でおこなうことができます。ac-library-csharp というライブラリには Segtree<T> クラスがあり、これを使えば簡単にセグメント木を構築することができます。今回はこれを使い倒すことにします。
参考： ac-library-csharpを使ってみる(セグメント木編)
A58 – RMQ (Range Maximum Queries)
A58 – RMQ (Range Maximum Queries)
問題の概要
長さ N の数列 A がある。最初はすべての要素が 0 である。
以下の 2 種類のクエリを処理せよ。クエリ 1：A[pos] の値を x に更新する。
クエリ 2：A[l], …, A[r -1] の最大値を答える。
1点更新、区間最大値取得ができる RangeMaxQuery クラスを定義しておきます。あとはこれを使えばクエリを処理することができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
using AtCoder; class RangeMaxQuery { struct OP : ISegtreeOperator<long> { long ISegtreeOperator<long>.Identity => long.MinValue; long ISegtreeOperator<long>.Operate(long x, long y) => Math.Max(x, y); } Segtree<long, OP> seg; public RangeMaxQuery(long[] arr) => seg = new Segtree<long, OP>(arr); public long this[int idx] { get { return seg[idx]; } set { seg[idx] = value; } } // 閉区間 [l, r] の最大値を求める public long Max(int l, int r) => seg.Prod(l, r + 1); } class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int Q) = (nq[0], nq[1]); RangeMaxQuery rmq = new RangeMaxQuery(new long[N]); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; if (t == 1) { int pos = vs[1] - 1; int x = vs[2]; rmq[pos] = x; } if (t == 2) { int l = vs[1] - 1; int r = vs[2] - 1; Console.WriteLine(rmq.Max(l, r - 1)); } } } } |
A59 – RSQ (Range Sum Queries)
問題の概要
長さ N の数列 A がある。最初はすべての要素が 0 である。
以下の 2 種類のクエリを処理せよ。クエリ 1：A[pos] の値を x に更新する。
クエリ 2：A[l], …, A[r -1] の合計値を答える。
今度は区間最大値ではなく区間和を求める問題です。RangeMaxQuery クラスを少し変更するだけで対応できます。本質的には OP.Operate(long x, long y) を変えただけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
using AtCoder; class RangeSumQuery { struct OP : ISegtreeOperator<long> { long ISegtreeOperator<long>.Identity => long.MinValue; long ISegtreeOperator<long>.Operate(long x, long y) => x + y; } Segtree<long, OP> seg; public RangeSumQuery(long[] arr) => seg = new Segtree<long, OP>(arr); public long this[int idx] { get { return seg[idx]; } set { seg[idx] = value; } } // 閉区間 [l, r] の合計値を求める public long Sum(int l, int r) => seg.Prod(l, r + 1); } class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int Q) = (nq[0], nq[1]); RangeSumQuery rsq = new RangeSumQuery(new long[N]); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; if (t == 1) { int pos = vs[1] - 1; int x = vs[2]; rsq[pos] = x; } if (t == 2) { int l = vs[1] - 1; int r = vs[2] - 1; Console.WriteLine(rsq.Sum(l, r - 1)); } } } } |
F – Range Xor Query
問題の概要
長さ N の整数列 A が与えられる。
Q 個のクエリを処理せよ。クエリ 1: A[X[i]] を A[X[i]] XOR Y[i] で更新する。
クエリ 2: A[X[i]], A[X[i] + 1], …, A[Y[i]] を出力する。
XOR もセグメント木で処理することができます。
セグメント木で扱える処理とはどのようなものなのでしょうか？ 結論からいうとモノイド（monoid）であれば扱うことが可能です。モノイドとは以下のようなものです。
結合律
S の任意の元 a, b, c に対して、(a・b)・c = a・(b・c)
単位元の存在
S の元 e が存在して、S の任意の元 a に対して e・a = a・e = a
例えば足し算であれば (a + b) + c = a + (b + c) なので結合法則が成り立ちます。また 0 + a = a + 0 = a なので 0 が単位元となります。掛け算も結合法則が成り立ち、1 が単位元となります。最大値や最小値もやはり結合法則が成り立ち、-∞ や ∞ が単位元となります。XOR も同様に単位元が 0 であるモノイドです。
すなわち結合律と単位元が存在するならセグメント木を使った処理が可能です。
OP 構造体の定義を少し変えれば対応できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
using AtCoder; class RangeXorQuery { struct OP : ISegtreeOperator<long> { long ISegtreeOperator<long>.Identity => 0; long ISegtreeOperator<long>.Operate(long x, long y) => x ^ y; } Segtree<long, OP> seg; public RangeXorQuery(long[] arr) => seg = new Segtree<long, OP>(arr); public long this[int idx] { get { return seg[idx]; } set { seg[idx] = value; } } // 閉区間 [l, r] の XOR を求める public long Xor(int l, int r) => seg.Prod(l, r + 1); } class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int Q) = (nq[0], nq[1]); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); RangeXorQuery rxq = new RangeXorQuery(A); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int t, int x, int y) = (vs[0], vs[1], vs[2]); if (t == 1) rxq[x - 1] ^= y; if (t == 2) Console.WriteLine(rxq.Xor(x - 1, y - 1)); } } } |
E – Set Meal
問題の概要
長さ N の整数列 A と 長さ M の整数列 B が与えられる。
さらにふたつの整数のペア(C[i], D[i]) L 組 が与えられる。A[i] + B[j] の最大値を求めよ。
ただし (i, j) = (C[k], D[k]) となるものは選んではならない。
この問題は優先度付きキュー（priority queue）を使えば解くことができます。大きい順に A[i] + B[j] を求め、(i, j) = (C[k], D[k]) でないものが見つかればそれが解となります。
参照：優先度付きキュー（priority queue）を使って計算結果がK番目に大きくなる組を求める
これとは別にセグメント木を使う解法もあります。
どのようにするかというと・・・
① 各 i に対して A[i] と合わせられない B の添字 の集合を取得しておく。
② セグ木 seg を B で初期化する。
③ A[i] と合わせられない B の添字 j を 0 で更新
④ seg の最大値を取得
⑤ 0 に変更した要素を元に戻し、i + 1 以降も同様に ③ ④ の処理をする。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// RangeMaxQuery クラスは上記定義のとおり class Program { static void Main() { int[] nml = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int M, int L) = (nml[0], nml[1], nml[2]); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long[] B = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); List<int>[] ng = new List<int>[N]; for (int i = 0; i < N; i++) ng[i] = new List<int>(); for (int i = 0; i < L; i++) { int[] cd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); ng[cd[0] - 1].Add(cd[1] - 1); } RangeMaxQuery rmq = new RangeMaxQuery(B); long ans = 0; for (int i = 0; i < N; i++) { List<(int, long)> olds = new List<(int, long)>(); // 元に戻せるように記憶 foreach (int idx in ng[i]) { olds.Add((idx, rmq[idx])); rmq[idx] = 0; } ans = Math.Max(ans, A[i] + rmq.Max(0, M - 1)); foreach (var old in olds) rmq[old.Item1] = old.Item2; } Console.WriteLine(ans); } } |
F – Rook Score
問題の概要
縦 10^9 マス、横 10^9 マスのマス目がある。
(R[i], C[i]) には正整数 X[i] が、他の 10^18 – N 個のマスには 0 が書かれている。あるマス (r, c) を選んだとき、これと行または列が同じ 2 × 10^9 – 1 個のマスに書かれた整数の総和を S と定義する。
S の最大値を求めよ。
前問の応用問題です。縦 10^9 マス、横 10^9 マスと大きいのですが、非 0 が書かれたマスは N 個だけなので座標圧縮すればなんとかなりそうです。
各行と各列の総和を計算し、非 0 が書かれたマスがある行 r を全探索します。各列の総和から (r, c) の値を引いたあと列の総和の最大値を求めます。この最大値と r 行の総和の合計が r 行のあるマスを選んだときの S の最大値であり、解の候補となります。すべての候補のなかから最大値を選べば、これが解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
using AtCoder; // RangeMaxQuery クラスは上記定義のとおり class Program { static void Main() { int N = int.Parse(Console.ReadLine()); // (r, c) を座標圧縮する List<(int, int, int)> RCX = new List<(int, int, int)>(); HashSet<int> setR = new HashSet<int>(); HashSet<int> setC = new HashSet<int>(); for (int i = 0; i < N; i++) { int[] rcx = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); RCX.Add((rcx[0], rcx[1], rcx[2])); setR.Add(rcx[0]); setC.Add(rcx[1]); } int[] arrR = setR.ToArray(); int[] arrC = setC.ToArray(); Dictionary<int, int> dicR = new Dictionary<int, int>(); Dictionary<int, int> dicC = new Dictionary<int, int>(); for (int i = 0; i < arrR.Length; i++) dicR.Add(arrR[i], i); for (int i = 0; i < arrC.Length; i++) dicC.Add(arrC[i], i); // 座標圧縮された (r, c, x) が得られた List<(int, int, int)> CompressedRCX = new List<(int, int, int)>(); for (int i = 0; i < N; i++) CompressedRCX.Add((dicR[RCX[i].Item1], dicC[RCX[i].Item2], RCX[i].Item3)); long[] sumRs = new long[arrR.Length]; long[] sumCs = new long[arrC.Length]; // 各行に存在する非 0 のマスの列番号とその値のタプルのリスト List<(int, int)>[] cxByR = new List<(int, int)>[arrR.Length]; for (int i = 0; i < arrR.Length; i++) cxByR[i] = new List<(int, int)>(); for (int i = 0; i < N; i++) { int r = CompressedRCX[i].Item1; int c = CompressedRCX[i].Item2; int x = CompressedRCX[i].Item3; sumRs[r] += x; sumCs[c] += x; cxByR[r].Add((c, x)); } RangeMaxQuery rmq = new RangeMaxQuery(sumCs); long ans = 0; for (int r = 0; r < arrR.Length; r++) { foreach (var pair in cxByR[r]) rmq[pair.Item1] -= pair.Item2; ans = Math.Max(ans, sumRs[r] + rmq.Max(0, arrC.Length - 1)); foreach (var pair in cxByR[r]) rmq[pair.Item1] += pair.Item2; } Console.WriteLine(ans); } } |
