AtCoder NoviStepsを埋めてみる(18) 連想配列（Dictionary）1Q 以上の続きです。今回はSortedSetです。
Contents
SortedSetとは？
SortedSetは並べ替えられた順序で維持されるオブジェクトのコレクションを表します。SortedSetを使うことで「集合に含まれている値の最小値を求めよ」「集合に含まれている要素のうち x 以上である最小の値を求めよ」などの処理が高速にできるようになります。
集合に含まれている値の最小値と最大値
集合に含まれている値の最小値と最大値はこれで取得できます。
注意点
SortedSet は空のときに SortedSet.Max や SortedSet.Min が 0 を返します。本当に最大値や最小値が 0 であるときと区別できるように番兵を追加しておきましょう。
|
1 2 3 |
// 番兵として long.MinValue, long.MaxValue を追加しておくこと long min = sortedSet.Min; long max = sortedSet.Max; |
集合に含まれている要素のうち x 以上である最小の値
集合に含まれている要素のうち x 以上である最小の値や x 以下である最大の値はこれで取得できます。
注意点
SortedSet.GetViewBetween(min, max) メソッドは min 以上、max 以下の値を返します。第一引数より第二引数が小さいと例外が発生するので注意が必要です。
SortedSet.GetViewBetween(min, max).Min や SortedSet.GetViewBetween(min, max).Max は高速ですが、SortedSet.GetViewBetween(min, max).Count は時間がかかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// 番兵として long.MinValue, long.MaxValue を追加しておくこと // x 以上である最小の値 static long UpperMin(SortedSet<long> sortedSet, long x) { return sortedSet.GetViewBetween(x, long.MaxValue).Min; } // x 以下である最大の値 static long LowerMax(SortedSet<long> sortedSet, long x) { return sortedSet.GetViewBetween(long.MinValue, x).Max; } |
集合に含まれている要素のうち x にもっとも近い値
集合に含まれている要素のうち x にもっとも近い値と差の絶対値を返すメソッドを示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// 番兵として long.MinValue, long.MaxValue を追加しておくこと static (long value, long diff) DiffMin(SortedSet<long> sortedSet, long x) { long value = long.MaxValue; long diff = long.MaxValue; long upperMin = UpperMin(sortedSet, x); if (upperMin < long.MaxValue) { value = upperMin; diff = Math.Abs(upperMin - x); } long lowerMax = LowerMax(sortedSet, x); if (lowerMax > long.MinValue && diff > Math.Abs(lowerMax - x)) { value = lowerMax; diff = Math.Abs(lowerMax - x); } return (value: value, diff: diff); } |
集合に含まれている要素のうち min 以上 max 以下を削除
集合に含まれている要素のうち min 以上 max 以下を削除して削除された要素を返すメソッドを示します。
|
1 2 3 4 5 6 7 8 9 |
static List<long> RemoveRange(SortedSet<long> sortedSet, long min, long max) { List<long> res = new List<long>(); var view = sortedSet.GetViewBetween(min, max); foreach (var item in view) res.Add(item); view.Clear(); return res; } |
A55 – Set
問題の概要
以下の 3 種類のクエリを高速に処理するプログラムを実装せよ。
クエリ 1：整数 x を追加する（既に存在する値が追加されることはない）。
クエリ 2：整数 x を取り除く（存在しない値が削除されることはない）。
クエリ 3：整数 x 以上で最小の値を出力する（該当する値がないときは -1）。
上記で実装した UpperMin メソッドを使えば簡単にできます。
|
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 |
class Program { // UpperMin メソッドは上記定義のとおり static void Main() { int Q = int.Parse(Console.ReadLine()); var sortedSet = new SortedSet<long>(); // 番兵 sortedSet.Add(long.MaxValue); sortedSet.Add(long.MinValue); for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; int x = query[1]; if (t == 1) sortedSet.Add(x); if (t == 2) sortedSet.Remove(x); if (t == 3) { long min = UpperMin(sortedSet, x); if(min < long.MaxValue) Console.WriteLine(min); else Console.WriteLine(-1); } } } } |
B55 – Difference
問題の概要
以下の 2 種類のクエリを高速に処理するプログラムを実装せよ。
クエリ 1：整数 x を追加する。
クエリ 2：整数 x とすでに追加されている値の差の絶対値の最小値を出力する。
集合に含まれている要素のうち x 以上である最小の値との絶対値と x 以下である最大の値との絶対値を比較して小さいほうを出力すればよいです。
|
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 |
using System.Text.RegularExpressions; class Program { // DiffMin メソッドは上記定義のとおり static void Main() { int Q = int.Parse(Console.ReadLine()); var sortedSet = new SortedSet<long>(); sortedSet.Add(long.MinValue); sortedSet.Add(long.MaxValue); for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; int x = query[1]; if (t == 1) sortedSet.Add(x); else if (t == 2) { (long value, long diff) res = DiffMin(sortedSet, x); if(res.diff < long.MaxValue) Console.WriteLine(res.diff); else Console.WriteLine(-1); } } } } |
D – Cutting Woods
問題の概要
長さ L メートルの直線状の木材がある。
木材の左端から x メートルの地点には目印として線 x が引かれている。
Q 個のクエリが与えられる。
クエリ 1: x がある地点で木材を 2 つに切る。
クエリ 2: x を含む木材を選び、その長さを出力する。
SortedSetに切られた地点の座標を格納して x 以上である最小の値と x 以下である最大の値との差を出力すればよいです。最初にもともとの木材の両端の座標である 0 と L を忘れずに格納しておきます。
|
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 |
class Program { // UpperMin、LowerMax メソッドは上記定義のとおり static void Main() { int[] lq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int L = lq[0]; int Q = lq[1]; SortedSet<long> sortedSet = new SortedSet<long>(); sortedSet.Add(0); sortedSet.Add(L); for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; long x = query[1]; if (t == 1) sortedSet.Add(x); if (t == 2) { long right = UpperMin(sortedSet, x); long left = LowerMax(sortedSet, x); Console.WriteLine(right - left); } } } } |
D – Permutation Subsequence
問題の概要
(1, 2, …, N) を並び替えて得られる数列 P が与えられる。
長さ K の正整数列 I であって、以下の条件を共に満たすものを良い添字列と定義する。
1 ≦ I[1] < I[2] < … < I[K] <= N （1-based indexing）
(P[I[1]], P[I[2]], ..., P[I[K]]) はある連続する K 個の整数を並び替えることで得られる。
すべての良い添字列における I[K] - I[1] の最小値を求めよ。
数列 P から値と index のペアをつくり、値でソートします。
最初に値が 1 から K までの index を SortedSet に格納して最大値 - 最小値を求めて ans に代入します。そのあと 値が 1 の index を削除して 値が K + 1 の index を追加して最大値 - 最小値を求め、小さければこの値で ans を更新します。これを繰り返し最終的な ans が求めるべき解です。
|
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 |
class Program { static void Main() { int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nk[0]; int K = nk[1]; int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<(int, int)> pairs = new List<(int, int)> (); for (int i = 0; i < N; i++) pairs.Add((P[i], i)); pairs = pairs.OrderBy(_ => _.Item1).ToList(); var sortedSet = new SortedSet<int>(); for (int i = 0; i < K; i++) sortedSet.Add(pairs[i].Item2); int ans = sortedSet.Max - sortedSet.Min; for (int i = K; i < N; i++) { sortedSet.Remove(pairs[i - K].Item2); sortedSet.Add(pairs[i].Item2); ans = Math.Min(ans, sortedSet.Max - sortedSet.Min); } Console.WriteLine(ans); } } |
C – Max – Min Query
問題の概要
整数の多重集合 S がある。はじめ S は空である。
Q 個のクエリが与えられる。
クエリ 1 : S に x を 1 個追加する。
クエリ 2 : S から x を min(c, (S に含まれる x の個数)) 個削除する。
クエリ 3 : (S の最大値) – (S の最小値) を出力する。
多重集合を扱う場合はSortedSetで種類を、Dictionary でその個数を管理するとうまくいきます。
|
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 |
class Program { static void Main() { int Q = int.Parse(Console.ReadLine()); SortedSet<int> sortedSet = new SortedSet<int>(); Dictionary<int, int> dic = new Dictionary<int, int>(); for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = query[0]; if (t == 1) { int x = query[1]; if(!sortedSet.Contains(x)) { sortedSet.Add(x); dic.Add(x, 0); } dic[x]++; } if (t == 2) { int x = query[1]; int c = query[2]; if (sortedSet.Contains(x)) { dic[x] -= c; if (dic[x] <= 0) { dic.Remove(x); sortedSet.Remove(x); } } } if (t == 3) Console.WriteLine(sortedSet.Max - sortedSet.Min); } } } |
D – Linear Probing
問題の概要
N = 2^20 項からなる数列 A がある。初期状態はすべての要素が -1 である。
Q 個のクエリが与えられる。
クエリ 1 :
整数 h を x で定める。
A[h % N] ≠ -1 である間、h の値を 1 増やすことを繰り返す。
A[h % N] = x を代入する。
クエリ 2 :
A[x % N] の値を出力せよ。
A[i] == -1 である i を SortedSet に格納しておけば x で更新する index をすぐに知ることができます。
|
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 |
class Program { // UpperMin メソッドは上記定義のとおり static void Main() { int Q = int.Parse(Console.ReadLine()); int N = (int)Math.Pow(2, 20); long[] A = new long[N]; SortedSet<int> sortedSet = new SortedSet<int>(); // A[i] == -1 である index for (int i = 0; i < N; i++) { A[i] = -1; sortedSet.Add(i); } for (int i = 0; i < Q; i++) { string[] query = Console.ReadLine().Split(); int t = int.Parse(query[0]); long x = long.Parse(query[1]); if (t == 1) { long h = x % N; // h 以上で最小の idx を探す。ないなら 0 以上で最小の idx long idx = UpperMin(sortedSet, h); if (idx == long.MaxValue) idx = UpperMin(sortedSet, 0); sortedSet.Remove(idx); A[idx] = x; } if (t == 2) Console.WriteLine(A[x % N]); } } } |
