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 52 53 |
// Set クラスは上記定義のとおり 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 71 72 |
// Set クラスは上記定義のとおり 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 64 65 |
// Multiset クラスは上記定義のとおり 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 71 72 |
// Multiset クラスは上記定義のとおり 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 55 56 |
// Multiset クラスは上記定義のとおり 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 – White Pawn
問題の概要
行と列にそれぞれ 0 から 2N までの番号が付いた (2N + 1)×(2N + 1) のマス目があり、(X[i] ,Y[i]) に N 個の黒いポーンが置かれている。
また (0, N) に白いポーンが 1 つ置かれている。
白いポーンが(i, j) にあるとき、以下のように動かすことができる。
(i + 1, j) に黒いポーンがない場合、(i + 1, j) へ移動できる。
(i + 1, j + 1) に黒いポーンがある場合、(i + 1, j + 1) へ移動できる。
(i + 1, j – 1) に黒いポーンがある場合、(i + 1, j – 1) へ移動できる。
この操作を繰り返した結果、(2N, Y) に白のポーンが置かれている状態にできるような Y の値としてあり得るものの個数を求めよ。
チェスを知らない人にはわかりにくい問題ですが、わかる人にはルールどおりに白いポーンを動かしたらたどり着ける 2N 行目のマスは何通りあるかを問うているだけという問題です。
白いポーンが存在することができる列の集合を S とすると、最初は S = {N} です。
黒のポーンを行ごとにまとめ、上の行からみていきます。黒いポーンがある列を col としたとき、S のなかに col + 1, col – 1 がある場合は col を追加します。また col が S のなかにある場合は col を取り除きます。この処理は同時におこなわなければならないので、追加する col を格納する集合 T を用意して S から取り除くべき col を取り除いたあと T を追加するという処理を繰り返します。
|
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 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>(); for (int i = 0; i < M; i++) { int[] rc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int r = rc[0]; int c = rc[1]; if (!dic.ContainsKey(r)) dic.Add(r, new List<int>()); dic[r].Add(c); } SortedSet<int> set = new SortedSet<int>(); set.Add(N); var pairs = dic.OrderBy(_ => _.Key).ToArray(); foreach (var pair in pairs) { List<int> add = new List<int>(); foreach (var c in pair.Value) { if (set.Contains(c + 1)) add.Add(c); if (set.Contains(c - 1)) add.Add(c); } foreach (var c in pair.Value) set.Remove(c); foreach (var c in add) set.Add(c); } Console.WriteLine(set.Count); } } |
E – Smart Infants
問題の概要
AtCoder に参加している幼児が N 人、幼稚園が 2×10^5 校ある。
幼児 i のレートは A[i] であり、はじめ幼稚園 B[i] に所属している。
これから Q 回にわたって、幼児 C[j] の所属を幼稚園 D[j] に変更する。
幼児が一人以上いるような幼稚園それぞれについて園内で最もレートの高い幼児のレートを求め、その最小値として得られる値を「平等さ」と定義する。
Q 回それぞれの平等さを求めよ。
各幼稚園にいる幼児たちのレートの最大値を取得できるように Multiset の配列を定義し、ここに幼児たちのレートを Add していきます。必要なのは最大値の最小値なのでここで得られた最大値を別に定義した Multiset に追加しておきます。このとき幼児がいない幼稚園であれば解に影響しない値（long.MaxValueであれば最小値には影響しない）を最大値として返すようにしておきます。
転園によって最大値が変更されるのは 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 |
// Multiset クラスは上記定義のとおり class Program { static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int schoolCount = 20 * 10000; Multiset[] sets = new Multiset[schoolCount]; for (int i = 0; i < schoolCount; i++) sets[i] = new Multiset(); Dictionary<int, int> schools = new Dictionary<int, int>(); // その幼児はどの幼稚園にいるか int[] R = new int[N]; for (int i = 0; i < N; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0]; int b = ab[1] - 1; sets[b].Add(a); schools.Add(i, b); R[i] = a; } long GetMax(int i) { // 空の場合は long.MinValue が返されるのでこの場合は解に影響しない long.MaxValue を返す long max = sets[i].Max(); return (max != long.MinValue ? max : long.MaxValue); } Multiset maxes = new Multiset(); for (int i = 0; i < schoolCount; i++) maxes.Add(GetMax(i)); for (int i = 0; i < Q; i++) { int[] cd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int c = cd[0] - 1; int d = cd[1] - 1; // 転園元から R[c] を除去。除去の前後の最大値を取得しておく long oldMax1 = GetMax(schools[c]); sets[schools[c]].Remove(R[c]); long newMax1 = GetMax(schools[c]); // 転園先に R[c] を追加。追加の前後の最大値を取得しておく long oldMax2 = GetMax(d); sets[d].Add(R[c]); schools[c] = d; long newMax2 = GetMax(d); // 更新前の値を除去して更新後の値を追加する。これで最大値の最小値が得られる。 maxes.Remove(oldMax1); maxes.Remove(oldMax2); maxes.Add(newMax1); maxes.Add(newMax2); Console.WriteLine(maxes.Min()); } } } |
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 50 51 |
// Set クラスは上記定義のとおり 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); } } |
C – 合コン大作戦
問題の概要
N 人の男性と M 人の女性で合コンをすることになった。
男性の年収は A[i] 円であり、年収が B[i] 円以上の女性とカップルになりたいと考えている。
また、女性の年収は C[j] 円であり、年収が D[j] 円以上の男性とカップルになりたいと考えている。
男女のカップルは何組できるだろうか？
言うまでもなく同じ人が 2 つ以上のカップルに含まれていてはならない。
男女をいっしょにして男性は収入で、女性は相手に希望している年収で降順ソートします。このとき値が同じであれば男性が先になるようにソートします。
集合 S を用意して、値が大きい順に見ていきます。男性なら S にいれ、女性であれば S から男性を探します。これで女性が希望する年収の男性は S のなかに存在するので、あとは女性の年収が男性が希望する年収以上であるかが問題になります。
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 |
// Multiset クラスは上記定義のとおり class Program { class Data { public Data(int income, int desired, bool isMale) { Income = income; Desired = desired; IsMale = isMale; } public int Income = 0; public int Desired = 0; public bool IsMale = false; } static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nm[0]; int M = nm[1]; List<Data> datas = new List<Data>(); for (int i = 0; i < N; i++) { int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = ab[0]; int b = ab[1]; datas.Add(new Data(a, b, true)); } for (int i = 0; i < M; i++) { int[] cd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int c = cd[0]; int d = cd[1]; datas.Add(new Data(c, d, false)); } datas = datas.OrderByDescending(_ => _.IsMale ? _.Income : _.Desired).ThenByDescending(_ => _.IsMale).ToList(); int ans = 0; Multiset set = new Multiset(); foreach (Data data in datas) { if (data.IsMale) set.Add(data.Desired); else { int f = data.Income; List<long> lowers = set.Lowers(f, 1); if (lowers.Count == 1) { set.Remove(lowers[0]); ans++; } } } Console.WriteLine(ans); } } |
