整数が格納されているリストがあります。ここから a 以上 b 以下の整数を削除するのであれば、以下のコードでできます。
|
1 2 |
List<int> list = new List<int>(); list = list.Where(_ => _ < 100 || _ > 1000).ToList(); |
しかしリストが長く、何度も削除する処理が繰り返される場合、時間がかかります。要素を削除すると抜けた部分を詰める処理が必要になるので、そのぶん遅くなってしまうのです。
要素が削除されることでリストのサイズが小さくなってくれれば終盤の処理は速くなってくれるかもしれませんが、以下のような処理の場合それもあまり期待できません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Random r = new Random(); int maxValue = 10000 * 10000; List<int> list = new List<int>(); for (int i = 0; i < 10 * 10000; i++) list.Add(r.Next(maxValue)); for (int i = 0; i < 10000; i++) { int min = r.Next(maxValue); int max = min + 100; list = list.Where(_ => _ < min || _ > max).ToList(); } Console.WriteLine(list.Count); |
今回はリストのなかからある区間の値を削除する処理を何度も繰り返さなければならないとき、処理をいかにして高速化するかを考えます。
Contents
RemovableMinMaxListクラスを自作する
まずリストに格納されている値をソートします。そして削除する値の区間が [min, max] であるとすれば、リストのなかで削除する部分のIndexがどうなるかを調べます。これは二分探索法を使えば O(log N)（Nはリストの長さ）でわかります。
削除する区間のIndexがわかったらその部分を実際に削除するかわりにその部分に印をつけます。残った部分がなにか知りたいときだけ残っている要素はなにか、削除された要素はなにかを返すようにします。imos法を使えば削除する区間の開始部分と終了部分に印をつける処理は O(1)、残っている要素と削除された要素を全列挙する処理は O(N) でできます。
ここでは ac-library-csharp を使っています。
コンストラクタ
コンストラクタで引数が渡されたらソートして long型のリストに格納します。Imosは要素に対して何回削除処理がおこなわれたかをカウントするときに必要になります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class RemovableMinMaxList { List<long> A = new List<long>(); int[] Imos = new int[0]; public RemovableMinMaxList(IEnumerable<int> list) { A = list.OrderBy(_ => _).Select(_ => (long)_).ToList(); Imos = new int[A.Count + 10]; } public RemovableMinMaxList(IEnumerable<long> list) { A = list.OrderBy(_ => _).ToList(); Imos = new int[A.Count + 1]; } } |
削除する区間の開始点と終了点に印をつける
[min, max]を削除するときは二分探索法でA[x]がmin以上になる最小のx、A[y]がmaxを超える最小の y を探します。x から y – 1 までが削除する区間です。なのでImos[x]++;Imos[y]– とします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class RemovableMinMaxList { public void RemoveMinMax(long min, long max) { int ok = A.Count; int ng = -1; int idxMin = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] >= min; }); int idxMax = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] > max; }); Imos[idxMin]++; Imos[idxMax]--; } } |
結果を取得する処理
結果を取得する処理を示します。Imosの累積和を計算します。このときの各要素の値がその要素が削除された回数です。この値が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 |
public class RemovableMinMaxList { public (List<long> Result, List<long> Removed) GetResult() { int[] sums = new int[Imos.Length + 1]; for (int i = 0; i < Imos.Length; i++) sums[i + 1] = sums[i] + Imos[i]; sums = sums.Skip(1).ToArray(); // 最初によぶんな要素が追加されてしまったので取り除く List<long> result = new List<long>(); List<long> removed = new List<long>(); for (int i = 0; i < A.Count; i++) { if (sums[i] > 0) removed.Add(A[i]); // 消えている else result.Add(A[i]); // 残っている } return (Result: result, Removed: removed); } } |
使ってみる
問題の趣旨は以下のとおりです。
XY平面上には最大20万個の家がある。
サンタクロースがXY平面上を上下または左右に最大20万回移動する。
サンタクロースがすべての移動を完了したときサンタクロースの座標とサンタクロースが通過した家の個数を求めよ。
数直線上ではなくXY平面上なのでちょっと面倒ですが、X成分とY成分にわけて考えるとよさそうです。
X座標が同じ家のリストとY座標が同じ家のリストをつくり、サンタクロースが上下に移動するときは前者の対応するリストのなかからMin(移動開始Y座標, 移動終了Y座標)からMax(移動開始Y座標, 移動終了Y座標)までの要素を取り除き、左右に移動するときは後者の対応するリストのなかからMin(移動開始X座標, 移動終了X座標)からMax(移動開始X座標, 移動終了X座標)までの要素を取り除きます。
最後にX座標が同じ家のリストから取り除かれた要素を調べて、これに対応する要素をY座標が同じ家のリストから取り除きます。最終的に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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
class Program { class House { public House(int x, int y) { X = x; Y = y; } public int X = 0; public int Y = 0; } static void Main() { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); int X = int.Parse(vs[2]); int Y = int.Parse(vs[3]); List<House> houses = new List<House>(); for (int i = 0; i < N; i++) { vs = Console.ReadLine().Split(); int x = int.Parse(vs[0]); int y = int.Parse(vs[1]); houses.Add(new House(x, y)); } // ① X座標が同じ家のリストとY座標が同じ家のリストをつくる var groupByX = houses.GroupBy(_ => _.X).ToArray(); var groupByY = houses.GroupBy(_ => _.Y).ToArray(); Dictionary<long, RemovableMinMaxList> removableMinMaxListsX = new Dictionary<long, RemovableMinMaxList>(); Dictionary<long, RemovableMinMaxList> removableMinMaxListsY = new Dictionary<long, RemovableMinMaxList>(); foreach (var group in groupByX) removableMinMaxListsX.Add(group.Key, new RemovableMinMaxList(group.Select(_ => _.Y))); foreach (var group in groupByY) removableMinMaxListsY.Add(group.Key, new RemovableMinMaxList(group.Select(_ => _.X))); // ② サンタクロースの動きに合わせてリストから要素を取り除く long curX = X; long curY = Y; for (int i = 0; i < M; i++) { vs = Console.ReadLine().Split(); string d = vs[0]; int v = int.Parse(vs[1]); if (d == "U") { long old = curY; curY += v; if (removableMinMaxListsX.ContainsKey(curX)) removableMinMaxListsX[curX].RemoveMinMax(Math.Min(old, curY), Math.Max(old, curY)); } if (d == "D") { long old = curY; curY -= v; if (removableMinMaxListsX.ContainsKey(curX)) removableMinMaxListsX[curX].RemoveMinMax(Math.Min(old, curY), Math.Max(old, curY)); } if (d == "L") { long old = curX; curX -= v; if (removableMinMaxListsY.ContainsKey(curY)) removableMinMaxListsY[curY].RemoveMinMax(Math.Min(old, curX), Math.Max(old, curX)); } if (d == "R") { long old = curX; curX += v; if (removableMinMaxListsY.ContainsKey(curY)) removableMinMaxListsY[curY].RemoveMinMax(Math.Min(old, curX), Math.Max(old, curX)); } } // ③ X座標が同じ家のリストから取り除かれた要素を取得する List<(long X, long Y)> list = new List<(long X, long Y)>(); foreach (var pair in removableMinMaxListsX) { var ret = removableMinMaxListsX[pair.Key].GetResult(); foreach (long y in ret.Removed) list.Add((X: pair.Key, Y: y)); } // ④ ③で取り除かれた要素をY座標が同じ家のリストから取り除く foreach (var p in list) removableMinMaxListsY[p.Y].RemoveMinMax(p.X, p.X); // ⑤ Y座標が同じ家のリストから取り除かれた要素の個数を数える。これが答え。 int ans = 0; foreach (var pair in removableMinMaxListsY) { var ret = removableMinMaxListsY[pair.Key].GetResult(); foreach (long x in ret.Removed) ans++; } Console.WriteLine($"{curX} {curY} {ans}"); } } |
機能を拡張する
自作したRemovableMinMaxListですが、リストを標榜しているのにランダムアクセスができません。削除されていない要素がいくつあるのか、先頭から i 番目の要素の値は何なのかがわかるようなものをつくることはできないのでしょうか？
そうだ！セグ木で殴ろう！
遅延評価型セグメント木の準備
遅延評価型のセグメント木を用意してすべての要素を 1 で初期化します。そして区間[min, max]を削除するときはセグメント木の区間[minIndex, maxIndex]を0で更新します。こうすることでセグメント木の区間[a, b]の総和を調べることで対応する区間の値で削除されていない値の個数を調べることができるようになり、これを二分探索することで削除されていない要素のうち先頭から i 番目がなにかも知ることができます。
リスト内の削除されていない要素の数を知りたいので、Operate(int x, int y) でセグメント木の各要素のうち 1 である要素の数を数えます。これは x + y でできます。
要素を削除する場合、区間にtrueを作用させます。なので作用の単位元 FIdentity は falseです。区間に true を作用させたらその要素の値は 0、それ以外のときは現状維持なので Mapping(bool f, int x) は f ? 0 : x、また区間Aへの作用と区間Bへの作用が重なったときは true を優先させたいので Composition(bool nf, bool cf) は nf | cf です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public class RemovableMinMaxList { List<long> A = new List<long>(); int N = 0; LazySegtree<int, bool, OP> seg = new LazySegtree<int, bool, OP>(0); struct OP : ILazySegtreeOperator<int, bool> { bool ILazySegtreeOperator<int, bool>.FIdentity => false; int ISegtreeOperator<int>.Identity => 0; bool ILazySegtreeOperator<int, bool>.Composition(bool nf, bool cf) => nf | cf; int ILazySegtreeOperator<int, bool>.Mapping(bool f, int x) => f ? 0 : x; int ISegtreeOperator<int>.Operate(int x, int y) => x + y; } } |
コンストラクタ
コンストラクタを示します。セグメント木に全要素が 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 |
public class RemovableMinMaxList { public RemovableMinMaxList(IEnumerable<int> list) { A = list.OrderBy(_ => _).Select(_ => (long)_).ToList(); N = A.Count; int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = 1; seg = new LazySegtree<int, bool, OP>(arr); } public RemovableMinMaxList(IEnumerable<long> list) { A = list.OrderBy(_ => _).ToList(); N = A.Count; int[] arr = new int[N]; for (int i = 0; i < N; i++) arr[i] = 1; seg = new LazySegtree<int, bool, OP>(arr); } } |
要素の数を取得する
リスト内にある削除されずに残っている要素の数、リスト内にある min 以上 max 以下の値の個数を取得する処理を示します。二分探索法で対応するindexを求め、セグメント木のその区間の総和を求めれば取得できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class RemovableMinMaxList { public int Count { get => seg.AllProd; } public int GetCount(long min, long max) { int ok = N; int ng = -1; int idxMin = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] >= min; }); int idxMax = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] > max; }); return seg.Prod(idxMin, idxMax); } } |
削除処理
リスト内の[min, max]を削除する処理を示します。前述のとおり二分探索法で削除する区間のindexを求めてセグメント木の区間に削除されたことを意味する true を作用させています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class RemovableMinMaxList { public void RemoveMinMax(int min, int max) { RemoveMinMax((long)min, (long)max); } public void RemoveMinMax(long min, long max) { int ok = N; int ng = -1; int idxMin = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] >= min; }); int idxMax = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] > max; }); seg.Apply(idxMin, idxMax, true); } } |
引数で指定された値をひとつだけ削除する処理を示します。
まず引数で指定された値がリスト内にどれだけ残っているかを調べます。0 なら何もする必要はありません。存在する場合は後ろにあるものから削除します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public class RemovableMinMaxList { public bool Remove(int v) { return Remove((long)v); } public bool Remove(long v) { int cnt = GetCount(v, v); if (cnt == 0) return false; int ok = N; int ng = -1; int idx = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] >= v; }); if (idx < A.Count && A[idx] == v) seg[idx + cnt - 1] = 0; return true; } } |
先頭から i 番目の要素はなにか？
削除されていない要素のうち先頭から i 番目の要素がなにかを求める処理を示します。
リストの区間[0, x]で削除されていない要素の数が i + 1 になるような最小の x を求めます。これはセグメント木に対して二分探索をしかければ求めることができます。A[x] が求めるべき値です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public class RemovableMinMaxList { public long this[int index] { get { int ok = N; int ng = -1; int idx = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return seg.Prod(0, mid + 1) >= index + 1; }); return A[idx]; } } } |
v は先頭から何番目か？
引数で指定された値はリスト内に残されている値のなかで先頭から何番目にあるかを取得する処理を示します。これも二分探索法とセグメント木の合せ技で取得可能です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public class RemovableMinMaxList { public int IndexOf(long v) { int ok = N; int ng = -1; int idx = AtCoder.StlFunction.BinarySearch(ok, ng, mid => { return A[mid] >= v; }); if (idx < A.Count && A[idx] == v && seg[idx] == 1) return seg.Prod(0, idx); else return -1; } } |
削除された要素と削除されずに残った要素を取得する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class RemovableMinMaxList { public (List<long> Result, List<long> Removed) GetResult() { List<long> result = new List<long>(); List<long> removed = new List<long>(); for (int i = 0; i < A.Count; i++) { if (seg[i] == 0) removed.Add(A[i]); // 消えている else if (seg[i] == 1) result.Add(A[i]); // 残っている } return (Result: result, Removed: removed); } } |
