AtCoder NoviStepsを埋めてみる(19) SortedSet 2Q以下の続きです。今回もSortedSetです。
再掲
|
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 |
// 番兵として 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 にもっとも近い値と差の絶対値を返す 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 以下を削除し削除された要素を返す 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; } |
Contents
E – Sparse Range
問題の概要
長さ N の整数列 A と正整数 D が与えられる。
以下の条件をともに満たす整数の組 (L, R) の個数を求めよ。
条件: L ≦ i < j ≦ R を満たすすべての整数の組 (i, j) について | A[i] – A[j] | ≧ D
L を固定して R をどれだけ増やせるかを考えます。L ≦ i < j ≦ R を満たすすべての整数の組 (i, j) について | A[i] – A[j] | ≧ D が成立している状態で R を増やすことができる条件は { A[L], A[L + 1], A[L + 2], …, A[R] } のなかで A[R + 1] よりも小さいものすべてが A[R + 1] – R 以下であること、A[R + 1] よりも大きいものすべてが A[R + 1] + R 以上であることです。LowerMax と UpperMin で表すと (LowerMax(sortedSet, x) ≦ A[R + 1] – D || UpperMin(sortedSet, x) ≧ D + A[R + 1]) を満たすことです。
尺取法ですべての L に対して R が取りうる最大値を求めると条件満たすすべての整数の組 (i, j) の個数を得ることができます。
|
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 |
class Program { // UpperMin、LowerMax メソッドは上記定義のとおり static void Main() { int[] nd = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nd[0]; long D = nd[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long ans = 0; var sortedSet = new SortedSet<long>(); // 番兵 sortedSet.Add(long.MinValue); sortedSet.Add(long.MaxValue); int right = 0; for (int left = 0; left < N; left++) { while (right < N) { long x = A[right]; if (UpperMin(sortedSet, x) < D + x || LowerMax(sortedSet, x) > x - D) break; sortedSet.Add(x); right++; } ans += right - left; sortedSet.Remove(A[left]); } Console.WriteLine(ans); } } |
D – Neighbor Distance
数直線があり、最初は座標 0 に人 0 がひとりで立っている。
これから、人 1,2,…,N がこの順に到着し、数直線上に立つ。
このとき d[i] を「人 i に最も近い別の人までの距離」と定義する。
人が到着するたびに d の総和を求めよ。
人 i が到着することで d の総和に d[i] が加算されます。また人 i が到着することで 人 i に最も近い別の人から見た「最も近い人」が人 i に変わる場合があります。ひとり到着するごとに最大で 2 人ぶんの変更がおこなわれます。
よってその都度 d の総和を計算するのではなく、差分のみ計算すればよいことになります。
|
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 |
class Program { // UpperMin、LowerMax メソッドは上記定義のとおり static void Main() { int N = int.Parse(Console.ReadLine()); int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); SortedSet<long> sortedSet = new SortedSet<long>(); Dictionary<long, long> dic = new Dictionary<long, long>(); // 番兵 sortedSet.Add(long.MinValue); sortedSet.Add(long.MaxValue); long ans = 0; // 人 0 と 人 1 sortedSet.Add(0); sortedSet.Add(X[0]); dic.Add(0, X[0]); dic.Add(X[0], X[0]); ans += X[0] + X[0]; Console.WriteLine(ans); for (int i = 1; i < N; i++) { int x = X[i]; // 左の人をチェック long left = LowerMax(sortedSet, x); long leftDiff = long.MaxValue; if (left != long.MinValue) { leftDiff = Math.Abs(x - left); } // 右の人をチェック long right = UpperMin(sortedSet, x); long rightDiff = long.MaxValue; if (right != long.MaxValue) { rightDiff = Math.Abs(x - right); } // 人 i に最も近い別の人までの距離を求める dic.Add(x, Math.Min(leftDiff, rightDiff)); ans += Math.Min(leftDiff, rightDiff); // 左側にいる人から最も近い別の人までの距離が変更されたかもしれない if (left != long.MinValue && dic[left] > leftDiff) { ans -= dic[left]; ans += leftDiff; dic[left] = leftDiff; } // 右側にいる人から最も近い別の人までの距離が変更されたかもしれない if (right != long.MaxValue && dic[right] > rightDiff) { ans -= dic[right]; ans += rightDiff; dic[right] = rightDiff; } sortedSet.Add(x); Console.WriteLine(ans); } } } |
D – Santa Claus 2
問題の概要
2次元平面上の 座標(X[i] ,Y[i]) に家があり、座標(Sx ,Sy) にサンタクロースがいる。
サンタクロースは
D[i] = ‘U’ なら (x, y) から (x, y + C[i]) に直線で移動する。
D[i] = ‘D’ なら (x, y) から (x, y – C[i]) に直線で移動する。
D[i] = ‘L’ なら (x, y) から (x – C[i], y) に直線で移動する。
D[i] = ‘R’ なら (x, y) から (x + C[i], y) に直線で移動する。
行動を終えたあとにサンタクロースがいる点と、行動により通過または到達した家の数を求めよ。ただし、同じ家を複数回通過または到達してもそれらは重複して数えない。
X[i] ,Y[i] が大きいので2次元配列を定義することができません。Dictionary で対応します。X 座標と Y 座標ごとに同じ座標の家を SortedSet で管理します。そしてサンタクロースが通った家は削除します。
先に定義しておいた RemoveRange メソッドで削除される家の座標は取得できるので X, Y 両方の SortedSet から忘れずに削除します。
|
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 |
using System.Text.RegularExpressions; class Program { // RemoveRange メソッドは上記定義のとおり static void Main() { int[] nms = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nms[0]; int M = nms[1]; int sx = nms[2]; int sy = nms[3]; Dictionary<long, SortedSet<long>> X = new Dictionary<long, SortedSet<long>>(); Dictionary<long, SortedSet<long>> Y = new Dictionary<long, SortedSet<long>>(); for (int i = 0; i < N; i++) { int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = xy[0]; int y = xy[1]; if (!X.ContainsKey(x)) X.Add(x, new SortedSet<long>()); X[x].Add(y); if (!Y.ContainsKey(y)) Y.Add(y, new SortedSet<long>()); Y[y].Add(x); } long curX = sx; long curY = sy; int ans = 0; for (int i = 0; i < M; i++) { string[] dc = Console.ReadLine().Split(); char d = dc[0][0]; int c = int.Parse(dc[1]); if (d == 'U') { long oldY = curY; long newY = curY + c; if (X.ContainsKey(curX)) { List<long> res = RemoveRange(X[curX], oldY, newY); foreach (var idx in res) { Y[idx].Remove(curX); ans++; } } curY = newY; } if (d == 'D') { long oldY = curY; long newY = curY - c; if (X.ContainsKey(curX)) { List<long> res = RemoveRange(X[curX], newY, oldY); foreach (var idx in res) { Y[idx].Remove(curX); ans++; } } curY = newY; } if (d == 'L') { long oldX = curX; long newX = curX - c; if (Y.ContainsKey(curY)) { List<long> res = RemoveRange(Y[curY], newX, oldX); foreach (var idx in res) { X[idx].Remove(curY); ans++; } } curX = newX; } if (d == 'R') { long oldX = curX; long newX = curX + c; if (Y.ContainsKey(curY)) { List<long> res = RemoveRange(Y[curY], oldX, newX); foreach (var idx in res) { X[idx].Remove(curY); ans++; } } curX = newX; } } Console.WriteLine($"{curX} {curY} {ans}"); } } |
D – Cross Explosion
縦 H マス、横 W マスのグリッドがある。
はじめ、すべてのマスには壁が 1 個ずつ立てられている。
Q 個のクエリを順に処理した後に、残っている壁の個数を出力せよ。
クエリ: (R[i] ,C[i]) に爆弾を置いて壁を爆破する。
(R[i] ,C[i]) に壁が存在する場合は、その壁を破壊して処理を終了する。
(R[i] ,C[i]) に壁が存在しない場合は、そこから上下左右に見て最初に現れる壁を破壊する。
H × W が 4 * 10^5 なので2次元配列を定義してかんがえます。X 座標と Y 座標ごとに同じ座標にある壁を SortedSet で管理します。(R[i] ,C[i]) に壁が存在するときに破壊される壁はひとつだけ、そうでないときは最大 4 個です。上下左右に見て最初に現れる壁の座標は UpperMin、LowerMax メソッドで取得できます。
|
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 |
class Program { // UpperMin、LowerMax メソッドは上記定義のとおり static void Main() { int[] hwq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int H = hwq[0]; int W = hwq[1]; int Q = hwq[2]; SortedSet<long>[] R = new SortedSet<long>[H]; SortedSet<long>[] C = new SortedSet<long>[W]; for (int r = 0; r < H; r++) { R[r] = new SortedSet<long>(); for (int c = 0; c < W; c++) R[r].Add(c); R[r].Add(long.MinValue); // 番兵 R[r].Add(long.MaxValue); } for (int c = 0; c < W; c++) { C[c] = new SortedSet<long>(); for (int r = -1; r <= H; r++) C[c].Add(r); C[c].Add(long.MinValue); C[c].Add(long.MaxValue); } int ans = H * W; for (int i = 0; i < Q; i++) { int[] rc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int r = rc[0] - 1; int c = rc[1] - 1; if (R[r].Contains(c) && C[c].Contains(r)) { R[r].Remove(c); C[c].Remove(r); ans--; } else { long left = LowerMax(R[r], c); long right = UpperMin(R[r], c); long up = LowerMax(C[c], r); long down = UpperMin(C[c], r); if (left >= 0) { R[r].Remove(left); C[left].Remove(r); ans--; } if (right < W) { R[r].Remove(right); C[right].Remove(r); ans--; } if (up >= 0) { R[up].Remove(c); C[c].Remove(up); ans--; } if (down < H) { R[down].Remove(c); C[c].Remove(down); ans--; } } } Console.WriteLine(ans); } } |
E – Mex and Update
問題の概要
長さ N の数列 A が与えられる。
以下の Q 個のクエリを処理せよ。
クエリ:
A[i[k]] の値を x[k] に変更する。
その後、A に含まれない最小の非負整数を出力する。
A に含まれない非負整数を SortedSet に格納しておけば、各クエリごとにUpperMin メソッドを呼び出すことで A に含まれない最小の非負整数を取得できます。
|
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 |
class Program { // UpperMin メソッドは上記定義のとおり static void Main() { int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = nq[0]; int Q = nq[1]; int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] C = new int[N + 1]; // A のなかに存在する 0 から N までの値の個数 foreach (var v in A) { if(v <= N) C[v]++; } SortedSet<long> sortedSet = new SortedSet<long>(); for (int i = 0; i <= N; i++) { if (C[i] == 0) sortedSet.Add(i); } for (int i = 0; i < Q; i++) { int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int idx = query[0] - 1; int x = query[1]; int old = A[idx]; A[idx] = x; // 存在しない値を更新していく if (old <= N) { C[old]--; if (C[old] == 0) sortedSet.Add(old); } if (x <= N) { C[x]++; sortedSet.Remove(x); } Console.WriteLine(UpperMin(sortedSet, 0)); } } } |
D – LRUD Instructions
問題の概要
H 行 W 列のグリッドがあり、上から r[i] 行目、左から c[i] 列目にあるマスは壁である。
駒が(rs ,cs) に置かれている。Q 個のクエリが与えられるので処理せよ。
クエリ:
D[i] = ‘U’ なら (r, c) から (r – L[i], c) に直線で移動する。
D[i] = ‘D’ なら (r, c) から (r + L[i], c) に直線で移動する。
D[i] = ‘L’ なら (r, c) から (r, c – L[i]) に直線で移動する。
D[i] = ‘R’ なら (r, c) から (r, c + L[i]) に直線で移動する。
いずれも壁がある場合やグリッドの外には移動できず、その直前で停止する。
移動後の座標を出力せよ。
H, W の値が大きいので2次元配列を定義することはできません。Dictionary で壁がある行と列を管理し、SortedSet で壁の座標を管理します。
壁がある行と列の移動はLowerMax, 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 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 |
class Program { // LowerMax, UpperMin メソッドは上記定義のとおり static void Main() { int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int H = hw[0]; int W = hw[1]; int rs = hw[2]; int cs = hw[3]; Dictionary<long, SortedSet<long>> R = new Dictionary<long, SortedSet<long>>(); Dictionary<long, SortedSet<long>> C = new Dictionary<long, SortedSet<long>>(); int N = int.Parse(Console.ReadLine()); for (int i = 0; i < N; i++) { int[] rc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int r = rc[0]; int c = rc[1]; if (!R.ContainsKey(r)) { R.Add(r, new SortedSet<long>()); R[r].Add(0); // とりうる値は 1 以上 W 以下なので 0 と W + 1 に番兵を置く R[r].Add(W + 1); } R[r].Add(c); if (!C.ContainsKey(c)) { C.Add(c, new SortedSet<long>()); C[c].Add(0); // とりうる値は 1 以上 H 以下なので 0 と H + 1 に番兵を置く C[c].Add(H + 1); } C[c].Add(r); } long curR = rs; long curC = cs; int Q = int.Parse(Console.ReadLine()); for (int i = 0; i < Q; i++) { string[] dl = Console.ReadLine().Split(); char d = dl[0][0]; int l = int.Parse(dl[1]); if (d == 'U') { if (!C.ContainsKey(curC)) curR = Math.Max(curR - l, 1); else curR = Math.Max(curR - l, LowerMax(C[curC], curR) + 1); } if (d == 'D') { if (!C.ContainsKey(curC)) curR = Math.Min(curR + l, H); else curR = Math.Min(curR + l, UpperMin(C[curC], curR) - 1); } if (d == 'L') { if (!R.ContainsKey(curR)) curC = Math.Max(curC - l, 1); else curC = Math.Max(curC - l, LowerMax(R[curR], curC) + 1); } if (d == 'R') { if (!R.ContainsKey(curR)) curC = Math.Min(curC + l, W); else curC = Math.Min(curC + l, UpperMin(R[curR], curC) - 1); } Console.WriteLine($"{curR} {curC}"); } } } |
D – Draw Your Cards
問題の概要
1 から N が書かれた N 枚のカードが裏向きで積まれた山札があり、上から i 枚目のカードには整数 P[i] が書かれている。
この山札を使って、以下の操作を N ターン繰り返す。
操作:
山札の一番上のカードを引いて、そこに書かれた整数を X とする。
場に見えている表向きのカードであって書かれた整数が X 以上であるもののうち、書かれた整数が最小のものの上に、引いたカードを表向きで重ねる。
もし場にそのようなカードがなければ、引いたカードをどれにも重ねずに表向きで場に置く。
その後、表向きのカードが K 枚重ねられた山が場にあればその山のカードをすべて取り除く。
各カードについて、何ターン目に取り除かれるか、あるいは最後まで取り除かれないかを求めよ。
場に置かれているカードを SortedSet で管理します。新たに出されたカードを重ねることができるカードは UpperMin メソッドを呼び出せばわかります。
重なり合ったカードの関係性は ac-library-csharp というライブラリの Dsu クラスを使って管理します。カードを重ねるときに merge してカードが取り除かれたらターン数を代表元に保存します。最後にそれぞれのカードの代表元に記録された値をみれば、そのカードが何ターン目に取り除かれたか or 最後まで取り除かれなかったかがわかります。
|
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 |
using AtCoder; class Program { // UpperMin メソッドは上記定義のとおり 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(); P = P.Select(_ => _ - 1).ToArray(); // 1-based indexing から 0-based indexing へ Dsu dsu = new Dsu(N); int[] ans = new int[N]; Array.Fill(ans, -1); SortedSet<long> sortedSet = new SortedSet<long>(); sortedSet.Add(long.MaxValue); for (int i = 0; i < N; i++) { int v = P[i]; long upperMin = UpperMin(sortedSet, v); if (upperMin != long.MaxValue) // 重ねるカードがあるので重ねる { sortedSet.Remove(upperMin); // 上にカードを置かれたら見えなくなるので Remove する dsu.Merge(v, (int)upperMin); // 重ねられて同じグループになったので merge する } sortedSet.Add(v); // K 枚重なっているのであれば Remove して解を代表元に記録する if (dsu.Size((int)v) == K) { sortedSet.Remove(v); ans[dsu.Leader(v)] = i + 1; } } // 代表元を参照すれば解がわかる for (int i = 0; i < N; i++) Console.WriteLine(ans[dsu.Leader(i)]); } } |
D – Sequence Query
問題の概要
空の数列 A がある。
クエリが Q 個与えられるので処理せよ。
クエリ 1: A に x を追加する。
クエリ 2: A の x 以下の要素のうち、大きい方から k 番目の値を出力する。
クエリ 3: A の x 以上の要素のうち、小さい方から k 番目の値を出力する。
ただし k は 5 以下。k 番目の要素が存在しない場合は -1 を出力すること。
数列 A は多重集合なので SortedSet と Dictionary を併用します。
x 以上の要素を k 個取得するには、まず sortedSet.GetViewBetween(x, long.MaxValue).Take(k).ToList() を実行して x 以上の要素を k 種類取得します。そのあと数列 A 内に同じ値が複数存在するかもしれないので、dic を参照して小さい方から k 番目の値を取得します。
x 以下の要素を k 個取得するときもだいたい同じですが、大きい方から探さないといけないので sortedSet.GetViewBetween(0, x).Reverse().Take(k).ToList() と Reverse しなければなりません。
|
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 |
class Program { static void Main() { int Q = int.Parse(Console.ReadLine()); SortedSet<long> sortedSet = new SortedSet<long>(); sortedSet.Add(long.MinValue); // 番兵 sortedSet.Add(long.MaxValue); Dictionary<long, int> dic = new Dictionary<long, int>(); // A の x 以下の要素のうち、大きい方から k 番目の値を取得する long LowerMaxK(long x, int k) { var values = sortedSet.GetViewBetween(0, x).Reverse().Take(k).ToList(); List<long> ans = new List<long>(); foreach (var v in values) { if (v == long.MinValue) return -1; for (global::System.Int32 j = 0; j < dic[v]; j++) { ans.Add(v); if (ans.Count == k) return v; } } return -1; } // A の x 以上の要素のうち、小さい方から k 番目の値を取得する long UpperMinK(long x, int k) { var values = sortedSet.GetViewBetween(x, long.MaxValue).Take(k).ToList(); List<long> ans = new List<long>(); foreach (var v in values) { if (v == long.MaxValue) return -1; for (global::System.Int32 j = 0; j < dic[v]; j++) { ans.Add(v); if (ans.Count == k) return v; } } return -1; } for (int i = 0; i < Q; i++) { string[] query = Console.ReadLine().Split(); int t = int.Parse(query[0]); if (t == 1) { long x = long.Parse(query[1]); sortedSet.Add(x); if(!dic.ContainsKey(x)) dic.Add(x, 0); dic[x]++; } if (t == 2) Console.WriteLine(LowerMaxK(long.Parse(query[1]), int.Parse(query[2]))); if (t == 3) Console.WriteLine(UpperMinK(long.Parse(query[1]), int.Parse(query[2]))); } } } |
L – スーパーマーケット
問題の概要
スーパーマーケットには陳列棚があり、この陳列棚には商品を並べられる列が N 本あります。
列 i には K[i] 個の商品が手前から奥へと一列に並べられており、手前から j 番目の商品の消費期限は T[i, j] である（すべての商品の消費期限は相異なる）。
M 人の客が順番に商品を買う。
i 番目の客はすべての列について現在の時点で手前から A[i] 番目までにある商品のうち最も消費期限の値が大きいものを購入する（A[i] は 1 または 2 である）。
それぞれの客が購入した商品の消費期限の値を求めよ。
一番手前の商品しか買わない客と手前から二番目までの商品も買う客がいるのでちょっとややこしいです。
一番手前の商品の消費期限のみを格納した SortedSet と 手前から二番目の商品のみを格納した SortedSet のふたつを定義します。一番手前の商品が買われたらその列の手前から二番目の商品が一番手前にくるように操作しなければなりません。ふたつの SortedSet のあいだで適切な追加と削除の処理が必要です。
以下のようなクラスを定義します。商品が買われたときに ふたつの SortedSet のあいだで適切な追加と削除の処理をするためのものです。
|
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 Data { public int First = 0; public int Second = 0; Queue<int> Others = new Queue<int>(); public Data(int[] vs) { Others = new Queue<int>(vs); // 番兵 Others.Enqueue(0); Others.Enqueue(0); Others.Enqueue(0); First = Others.Dequeue(); Second = Others.Dequeue(); } // 商品が買われたら適切にデータを入れ替える public void Pop(long v, SortedSet<long> firstSet, SortedSet<long> secondSet) { if (v == First) { First = Second; Second = Others.Dequeue(); firstSet.Remove(v); firstSet.Add(First); secondSet.Remove(First); secondSet.Add(Second); } else { Second = Others.Dequeue(); secondSet.Remove(v); secondSet.Add(Second); } } } |
|
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 N = int.Parse(Console.ReadLine()); // 各列にある商品を管理する List<Data> datas = new List<Data>(); // その商品はどの列にあったものかすぐにわかるようにする Dictionary<long, int> dic = new Dictionary<long, int>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); vs = vs.Skip(1).ToArray(); datas.Add(new Data(vs)); foreach (int v in vs) dic.Add(v, i); } int M = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); SortedSet<long> firstSet = new SortedSet<long>(); SortedSet<long> secondSet = new SortedSet<long>(); firstSet.Add(0); secondSet.Add(0); // 最初に一番手前にある商品、二番目に手前にある商品を SortedSet に格納する for (int i = 0; i < N; i++) { firstSet.Add(datas[i].First); secondSet.Add(datas[i].Second); } // 客が買う商品がどれか調べる。商品が買われたら Data クラス内で自動的に入れ替えられる。 foreach (int v in A) { if (v == 1) { long res = firstSet.GetViewBetween(0, long.MaxValue).Max; Console.WriteLine(res); int col = dic[res]; datas[col].Pop(res, firstSet, secondSet); } else { long res1 = firstSet.GetViewBetween(0, long.MaxValue).Max; long res2 = secondSet.GetViewBetween(0, long.MaxValue).Max; if (res1 > res2) { Console.WriteLine(res1); int col = dic[res1]; datas[col].Pop(res1, firstSet, secondSet); } else { Console.WriteLine(res2); int col = dic[res2]; datas[col].Pop(res2, firstSet, secondSet); } } } } } |
