AtCoder NoviStepsを埋めてみる(20) SortedSet 1Qの続きです。今回もSortedSetです。
SortedSet を使った便利クラス？
SortedSet.GetViewBetweenメソッドで取得した要素が空の場合、Max, Min が 0 になってしまう問題があったので最初に番兵を追加していましたが、以下の方法で回避できます。
要は SortedSet.GetViewBetween(v, long.MaxValue).Take(cnt).ToList() とやることで v 以上の要素を cnt 個取得できるので cnt を 1 にすれば v 以上の最小の要素を取得できるのです（そのような要素が存在しない場合は返されるリストは空）。
|
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 |
class Set { SortedSet<long> SortedSet = new SortedSet<long>(); // 基本的なやつ public bool Add(long v) => SortedSet.Add(v); public bool Remove(long v) => SortedSet.Remove(v); public bool Contains(long v) => SortedSet.Contains(v); public int Count => SortedSet.Count; // 最大値と最小値 public long Min() => SortedSet.Count > 0 ? SortedSet.Min : long.MaxValue; public long Max() => SortedSet.Count > 0 ? SortedSet.Max : long.MinValue; // v 以下の値を cnt 個（あれば）取得する public List<long> Lowers(long v, int cnt) => SortedSet.GetViewBetween(long.MinValue, v).Reverse().Take(cnt).ToList(); // v 以上の値を cnt 個（あれば）取得する public List<long> Uppers(long v, int cnt) => SortedSet.GetViewBetween(v, long.MaxValue).Take(cnt).ToList(); // min 以上 max 以下の値が存在するかどうか調べる public bool Between(long min, long max) => SortedSet.GetViewBetween(min, max).Take(1).Count() == 1; // 集合に含まれている要素のうち x にもっとも近い値と差の絶対値を返す public (List<long> values, long diff) DiffMin(long x) { List<long> values = new List<long>(); long diff = long.MaxValue; var uppers = Uppers(x, 1); var lowers = Lowers(x, 1); if (uppers.Count == 1) { values.Add(uppers[0]); diff = Math.Abs(uppers[0] - x); } if (lowers.Count == 1) { if (diff > Math.Abs(lowers[0] - x)) { values.Clear(); values.Add(lowers[0]); diff = Math.Abs(lowers[0] - x); } else if (diff == Math.Abs(lowers[0] - x)) values.Add(lowers[0]); } return (values: values, diff: diff); } // 集合に含まれている要素のうち min 以上 max 以下を削除し削除された要素を返す public List<long> RemoveRange(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; } } |
また多重集合も扱えるように Multiset クラスも定義してみました。
|
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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
public class Multiset { SortedSet<long> SortedSet = new SortedSet<long>(); Dictionary<long, int> Counts = new Dictionary<long, int>(); int _count = 0; public Multiset() { } public void Add(long v) { if (!Counts.ContainsKey(v)) { SortedSet.Add(v); Counts.Add(v, 0); } Counts[v]++; _count++; } public void Remove(long v) { Counts[v]--; if (Counts[v] == 0) { SortedSet.Remove(v); Counts.Remove(v); } _count--; } public bool Contains(long value) { return SortedSet.Contains(value); } public int Count(long value) { if(!SortedSet.Contains(value)) return 0; else return Counts[value]; } public int Count() { return _count; } public long Max() { if (SortedSet.Count > 0) return SortedSet.Max; else return long.MinValue; } public long Min() { if (SortedSet.Count > 0) return SortedSet.Min; else return long.MaxValue; } // v 以下の値を cnt 個（あれば）取得する public List<long> Lowers(long value, int cnt) { var vs = SortedSet.GetViewBetween(long.MinValue, value).Reverse().Take(cnt).ToList(); List<long> res = new List<long>(); foreach (var v in vs) { for (int i = 0; i < Counts[v]; i++) { res.Add(v); if (res.Count == cnt) return res; } } return res; } // v 以上の値を cnt 個（あれば）取得する public List<long> Uppers(long value, int cnt) { var vs = SortedSet.GetViewBetween(value, long.MaxValue).Take(cnt).ToList(); List<long> res = new List<long>(); foreach (var v in vs) { for (int i = 0; i < Counts[v]; i++) { res.Add(v); if (res.Count == cnt) return res; } } return res; } // 集合に含まれている要素のうち x にもっとも近い値と差の絶対値を返す public (long value, long diff) DiffMin(long x) { long value = long.MaxValue; long diff = long.MaxValue; var uppers = Uppers(x, 1); var lowers = Lowers(x, 1); if (uppers.Count == 1) { value = uppers[0]; diff = Math.Abs(uppers[0] - x); } if (lowers.Count == 1 && diff > Math.Abs(lowers[0] - x)) { value = lowers[0]; diff = Math.Abs(lowers[0] - x); } return (value: value, diff: diff); } // 集合に含まれている要素のうち min 以上 max 以下を削除し削除された要素を返す public Dictionary<long, int> RemoveRange(long min, long max) { Dictionary<long, int> res = new Dictionary<long, int>(); var view = SortedSet.GetViewBetween(min, max); foreach (var v in view) { res.Add(v, Counts[v]); Counts.Remove(v); } view.Clear(); return res; } } |
E – Cover query
問題の概要
N 個のマスが左右一列に並んでいる。最初、すべてのマスは白く塗られている。
Q 個のクエリが与えられるので、順に処理せよ。
クエリ：L[i], R[i] 間のマスをすべて黒く塗る。そのあと N 個のマスのうち白く塗られているマスの個数を求めよ。
黒く塗られている部分を区間として考えます。
区間は半開区間 a 以上 b 未満 [a, b) で管理します。a を SortedSet で管理し、それと対応する b を Dictionary で管理します。すでに存在する区間と重複する区間が追加されるときはその区間を削除してから追加します。
まず [left, right) を追加するとき、この右側にこれと重複する区間があるか調べます。left 以上で right 以下の要素がすでに SortedSet 内に格納されていたら、この区間はこれから追加しようとしている区間と重複しています。この場合はこれらの区間はすべて取り除きます。そして取り除いた要素と対応する右側の座標が right よりも大きければこの値で right を更新します。
次に左側に [left, right) と重複する区間があるか調べます。SortedSet に格納されている値のなかで left 以下で最大のものを取得します。これに対応する右側の座標が left 以上であれば重複しています。これを取り除いて、その左右の座標と left, right を比較して外側にあるのであれば left, right を更新します。
最後に更新された left, right で 半開区間 [left, right) を追加します。
区間の削除と追加で白く塗られているマスの個数の変化量がわかるので、差分から白マスの個数を計算して出力します。
|
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 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; Set set = new Set(); Dictionary<long, long> dic = new Dictionary<long, long>(); List<long> ans = new List<long>(); long ans0 = N; for (int i = 0; i < Q; i++) { int[] lr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long left = lr[0]; long right = lr[1]; right++; // 閉区間を半開区間に // [left, right) 間の値を削除 List<long> vs1 = set.RemoveRange(left, right); foreach (var v in vs1) { ans0 += dic[v] - v; right = Math.Max(right, dic[v]); dic.Remove(v); } // [left, right) 間に右側がある値を削除 List<long> vs2 = set.Lowers(left, 1); if (vs2.Count > 0 && left <= dic[vs2[0]]) { ans0 += dic[vs2[0]] - vs2[0]; right = Math.Max(right, dic[vs2[0]]); left = Math.Min(left, vs2[0]); dic.Remove(vs2[0]); } set.Add(left); dic.Add(left, right); ans0 -= right - left; ans.Add(ans0); } foreach (var v in ans) Console.WriteLine(v); } } |
E – 1D Bucket Tool
問題の概要
1 から N の番号がついた N 個のマスが一列に並んでいる。最初、マス i は色 i で塗られている。
クエリが Q 個与えられるので、順に処理せよ。
クエリ 1： マス x と隣接している同じ色のマスをすべて色 c に塗り替える。
クエリ 2： 色 c で塗られているマスの個数を出力せよ。
同じ色で塗られているマスの固まりは半開区間で管理するとよさそうです。「最初はマス i は色 i で塗られている」ので [0, 1), [1, 2), [2, 3), … のようになっています。クエリ 1 で色が塗り替えられたら両隣の区間の色と比較して同じ色なら区間をマージします。クエリ 1 で塗り替えられるのは x とマージされている区間だけなので各色の増減を管理すればクエリ 2 に高速で対応できます。
|
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 |
class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; Set set = new Set(); Dictionary<long, (long, int)> dic = new Dictionary<long, (long, int)>(); int[] counts = new int[N + 1]; for (int i = 1; i <= N; i++) { set.Add(i); dic.Add(i, (i + 1, i)); counts[i] = 1; } List<int> ans = new List<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]; int c = query[2]; var lowers = set.Lowers(x, 2); // 自分自身とその前を探す var uppers = set.Uppers(x + 1, 1); // 自分自身ではなく次を探す long cur_left = lowers[0]; int old_color = dic[cur_left].Item2; dic[cur_left] = (dic[cur_left].Item1, c); counts[old_color] -= (int)(dic[cur_left].Item1 - cur_left); counts[c] += (int)(dic[cur_left].Item1 - cur_left); if (uppers.Count == 1 && dic[uppers[0]].Item2 == c) { // 右側にある区間を吸収する long next_left = uppers[0]; dic[cur_left] = (dic[next_left].Item1, c); set.Remove(next_left); dic.Remove(next_left); } if (lowers.Count == 2 && dic[lowers[1]].Item2 == c) { // 左側にある区間に吸収される long prev_left = lowers[1]; dic[prev_left] = (dic[cur_left].Item1, c); set.Remove(cur_left); dic.Remove(cur_left); } } if (t == 2) { int c = query[1]; ans.Add(counts[c]); } } foreach (var v in ans) Console.WriteLine(v); } } |
E – Best Performances
問題の概要
長さ N の数列 A があり、最初はすべての項が 0 である。
合計 Q 回のクエリを処理せよ。
（クエリ）A[X[i]] を Y[i] に更新する。値が大きいもの K 個の総和を出力せよ。
これは多重集合なので Set ではなく Multiset を使います（Multiset の定義は上記のとおり）。
ふたつの Multiset を定義します。片方は値が大きい要素 K 個 を格納するもの（larges）で、他方はそれ以外を格納するもの（others）です。値が更新されたら Multiset に格納されている古い値は削除して更新された値を格納します。
値の更新によって 値が大きい要素 K 個 の入れ替えが起きる場合があります。これは larges.Min() < others.Max() であるかどうかを調べるだけでよいです。larges.Min() < others.Max() のときはそれぞれの要素を削除して反対側の Multiset に格納しなおします。
larges に対する要素の削除と追加で値が大きいもの K 個の総和を高速に得ることができます。
|
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 |
class Program { static void Main() { int[] nkq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nkq[0]; int K = nkq[1]; int Q = nkq[2]; long[] A = new long[N]; Multiset larges = new Multiset(); Multiset others = new Multiset(); for (int i = 0; i < K; i++) larges.Add(0); for (int i = K; i < N; i++) others.Add(0); List<long> ans = new List<long>(); long sum = 0; for (int i = 0; i < Q; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = xy[0] - 1; int y = xy[1]; long old = A[x]; A[x] = y; // 更新される値はどちら側に格納されているのか？ if (larges.Contains(old)) { larges.Remove(old); larges.Add(y); sum += y - old; } else if (others.Contains(old)) { others.Remove(old); others.Add(y); } // 上位・下位の入れ替えが発生するかもしれない if (larges.Min() < others.Max()) { long large_min = larges.Min(); long others_max = others.Max(); larges.Remove(large_min); others.Remove(others_max); larges.Add(others_max); others.Add(large_min); sum += others_max - large_min; } ans.Add(sum); } foreach (var v in ans) Console.WriteLine(v); } } |
E – Least Elements
問題の概要
長さ N の整数列 A と整数 M, K が与えられる。
i = 1, …, N – M + 1 に対して、次の独立な問題を解け。
（問題）M 個の整数 A[i], A[i + 1], …, A[i + M – 1] を昇順に並べ替えたときの先頭 K 個の値の総和を求めよ。
E – Best Performances と似た問題です。ふたつの Multiset (smalls, others) を定義し、最初の K 個の要素は smalls に追加し、M 個までは
smalls.Max() ≦ A[i] であれば others に、そうでなければ smalls に追加してもっとも大きい要素は追い出して others にいれなおします。それ以降は A[i] を追加して A[i – M] を削除、smalls.Max() > others.Min() であるなら該当するものを入れ替えるという処理を繰り返せばよいです。
|
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 |
class Program { static void Main() { int[] nmk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nmk[0]; int M = nmk[1]; int K = nmk[2]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Multiset smalls = new Multiset(); Multiset others = new Multiset(); List<long> ans = new List<long>(); long sum = 0; for (int i = 0; i < M; i++) { if (smalls.Count() < K) { smalls.Add(A[i]); sum += A[i]; } else { if (smalls.Max() <= A[i]) { others.Add(A[i]); } else { smalls.Add(A[i]); long small_max = smalls.Max(); smalls.Remove(small_max); others.Add(small_max); sum += A[i] - small_max; } } } ans.Add(sum); for (int i = M; i < N; i++) { if (smalls.Contains(A[i - M])) { smalls.Remove(A[i - M]); smalls.Add(A[i]); sum += A[i] - A[i - M]; } else { others.Remove(A[i - M]); others.Add(A[i]); } if (smalls.Max() > others.Min()) { long small_max = smalls.Max(); long others_min = others.Min(); smalls.Remove(small_max); others.Add(small_max); others.Remove(others_min); smalls.Add(others_min); sum += others_min - small_max; } ans.Add(sum); } Console.WriteLine(string.Join(" ", ans)); } } |
E – Wrapping Chocolate
問題の概要
縦 A[i] 横 B[i] のチョコレートが N 枚、縦 C[i] 横 D[i] の箱が M 個 ある。
ひとつの箱にはひとつのチョコレートしか入れられない。箱より大きなサイズのチョコレートは入れられないという条件ですべてのチョコレートをすべて箱に入れることは可能か判定せよ。
チョコレートと箱を幅で降順ソートします。もし同じ幅なら箱が先にくるようにソートします。
あとは順番に見ていくのですが、それが箱だった場合は多重集合 S に高さを格納します。チョコレートだった場合は S のなかからチョコレートの高さ以上で最小のものを取り出してマッチングします。もし途中でマッチングさせることができなくなったら答えは “No” であり、最後まで処理を続けることができた場合は “Yes” です。
|
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 |
class Program { class Rect { public Rect(int h, int w, bool box) { H = h; W = w; Box = box; } public int H = 0; public int W = 0; public bool Box = false; } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] D = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<Rect> rects = new List<Rect>(); for (int i = 0; i < N; i++) rects.Add(new Rect(A[i], B[i], false)); for (int i = 0; i < M; i++) rects.Add(new Rect(C[i], D[i], true)); rects = rects.OrderByDescending(_ => _.W).ThenByDescending(_ => _.Box).ToList(); Multiset multiset = new Multiset(); bool yes = true; foreach (Rect rect in rects) { if (rect.Box) multiset.Add(rect.H); else { int h = rect.H; List<long> uppers = multiset.Uppers(h, 1); if (uppers.Count == 1) multiset.Remove(uppers[0]); else yes = false; } } Console.WriteLine(yes ? "Yes" : "No"); } } |
E – Simple String Queries
問題の概要
長さ N の英小文字から成る文字列 S が与えられます。
Q 個のクエリを処理せよ。
クエリ 1：S の X[i] 文字目を C[i] に変更する。
クエリ 2：S の L[i] 文字目から R[i] 文字目までの部分文字列に表れる文字が何種類あるかを出力せよ。
文字は 26 種類しかないので、’a’ から ‘z’ が出現する index を SortedSet に格納して L[i] 文字目から R[i] 文字目までに各文字が存在するかを調べます。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); char[] S = Console.ReadLine().ToArray(); Set[] sets = new Set[26]; for (int i = 0; i < 26; i++) sets[i] = new Set(); for (int i = 0; i < S.Length; i++) sets[(S[i] - 'a')].Add(i); int Q = int.Parse(Console.ReadLine()); List<int> ans = new List<int>(); for (int i = 0; i < Q; i++) { string[] query = Console.ReadLine().Split(); int t = int.Parse(query[0]); if (t == 1) { int x = int.Parse(query[1]) - 1; char old_char = S[x]; char new_char = query[2][0]; S[x] = new_char; sets[(old_char - 'a')].Remove(x); sets[(new_char - 'a')].Add(x); } if (t == 2) { int left = int.Parse(query[1]) - 1; int right = int.Parse(query[2]) - 1; int cnt = 0; for (int ch = 0; ch < 26; ch++) { if (sets[ch].Between(left, right)) cnt++; } ans.Add(cnt); } } foreach (var v in ans) Console.WriteLine(v); } } |
