AtCoder NoviStepsを埋めてみる(2) 貪欲法 2Q問題の続きです。ちょっと難しめの問題を考えます。
Contents
E – Divide Graph
問題の概要
N 頂点 M 辺からなる単純連結無向グラフ G が与えられる。
辺 i は頂点 U[i] と頂点 V[i] を結んでいて辺の重みは 2 の i乗 である。
G の連結成分の個数がちょうど 2 になるように、G の辺のうちいくつかを選んで削除する。
そのとき削除される辺の重みの総和の最小値は？ 998244353 で割ったときの余りを答えよ。
辺のないグラフを構築して辺の重みが大きい順に辺をつないでいきます。ただし辺を繋ぐことで全体が連結になってしまう場合はその辺は繋ぎません。この処理は UnionFind木を使えばできます。
辺の重みは 2 の i乗 なので、辺 i の重みは i – 1 番目以前のすべての辺の重みの総和よりも大きいです。なので上記の方法で正しい解を得ることができます。
Dsuクラスは ac-library-csharp のものを使っています。
|
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 |
using AtCoder; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); int[] U = new int[M]; int[] V = new int[M]; for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; U[i] = u; V[i] = v; } Dsu dsu = new Dsu(N); HashSet<int> set = new HashSet<int>(); for (int i = M - 1; i >= 0; i--) { int u = U[i]; int v = V[i]; if (!dsu.Same(u, v)) // 2つの頂点が同一連結成分にないなら... { // 連結前の連結成分の大きさの和が N になるのであれば、 // 連結することで連結成分数が 1 になってしまう // この場合は削除する辺なので指数をSetに格納する // そうでないならそのまま辺を繋ぐ if (dsu.Size(u) + dsu.Size(v) == N) set.Add(i + 1); else dsu.Merge(u, v); } } long temp = 1; long ans = 0; long mod = 998244353; // 2 の i乗 を順次求めて必要であれば加算していく // 2 の i乗 の総和を mod で割った余りは // (2 の i乗 を mod で割った余りの総和) を mod で割った余りと考えてよい for (int i = 1; i <= M; i++) { temp *= 2; temp %= mod; if (set.Contains(i)) ans += temp; } Console.WriteLine(ans % mod); } } |
D – Match, Mod, Minimize 2
長さ N の非負整数列 A, B と 正整数 M が与えられる。
A をならべかえて (A[i] + B[i]) Mod M の総和を最小化したい。
最小値はなにか？
Mod M を考慮しなくてよいのであればどのように並べ替えても総和は変わりません。また A[i], B[i] は M 未満なので A[i] + B[i] が M を超えることはあってもその 2 倍を超えることはありません。
A[i] + B[i] が M を超えることで M だけ総和が減少します。この問題は
長さ N の非負整数列 A, B と 正整数 M が与えられる。
A をならべかえて (A[i] + B[i]) ≧ M となるペアをできるだけたくさん作りたい。
この個数は？
という問題を解ければ解くことができます。
|
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 |
class Program { static void Main() { int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long[] B = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long ans = Solve(N, M, A, B); Console.WriteLine(ans); } long Solve(int N, int M, long[] A, long[] B) { A = A.OrderBy(_ => _).ToArray(); Queue<long> qB = new Queue<long>(B.OrderByDescending(_ => _)); long cnt = 0; foreach (long v in A) { if (qB.Count > 0 && qB.Peek() + v >= M) { qB.Dequeue(); cnt++; } } return A.Sum() + B.Sum() - M * cnt; } } } |
E – Simultaneous Kagamimochi
長さ N の整数列 A が与えられる。すべての要素が 1 以上であり、すでに昇順でソートされている。
A[i] * 2 ≦ A[j] となるペアをできるだけたくさん作りたい。
ぜんぶでいくつできるだろうか？
A[0] とペアにできるもので最小であるものを探し、次にペアとなっていない最小のものから…と同じことを繰り返すのは残念ですが、嘘解法です。
以下のコードでは出題ページにある 3 つの入出力例 では正しい解を返しますが、提出してみると WA になります。
嘘解法
|
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 |
class Program { class Mochi { public Mochi(int v) { V = v; } public int V = 0; public bool Done = false; } static void Main() { int N = int.Parse(Console.ReadLine()); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); List<Mochi> M = new List<Mochi>(); foreach (int v in A) M.Add(new Mochi(v)); int ans = 0; int bottom_idx = 0; foreach (var top in M) { if (top.Done) continue; for (int i = bottom_idx; i < N; i++) { bottom_idx = i + 1; if (!M[i].Done && top.V * 2 <= M[i].V) { top.Done = true; M[i].Done = true; ans++; break; } } } Console.WriteLine(ans); } } |
正しい解法は以下のとおりです。
K 個のペアが作れるときは 上位 K 個 と下位 K 個を組み合わせればできる。
K の最大値が問題の解なので、これを二分探索法で探す。
二分探索法の処理は ac-library-csharp の StlFunction.BinarySearch メソッドを使っています。
|
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 |
using AtCoder; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); int ok = 0; int ng = N / 2 + 1; int ans = StlFunction.BinarySearch(ok, ng, mid => Check(mid)); Console.WriteLine(ans); // 上位 K 個 と下位 K 個を組み合わせてペアをつくることができるか調べる bool Check(int k) { if (k * 2 > N) return false; // N に対して作ろうとしているペアが多すぎる。できるわけがない。 for (int i = 0; i < k; i++) { if (A[i] * 2 > A[N - k + i]) return false; } return true; } } } |
E – Takahashi is Slime 2
問題の概要
縦 H 行横 W 列のマス目があり、マス(i,j) には強さ S[i, j] のスライムがいる。
マス(P,Q) にいるスライムは自身の強さの 1 / X 倍未満のものを選んで吸収し、その強さだけ強くなる。
また吸収されたスライムがいた部分は吸収したスライムによって埋められる。
このような処理を繰り返した場合、最初にマス(P, Q)にいたスライムの強さの最大値はどうなるだろうか？
一度接したスライムは吸収しない限り接し続けることと、自身の強さが減少することはないことから、吸収できるスライムはすべて吸収してしまってかまいません。このような処理は接しているスライムのうち、最も強さの小さいスライムを吸収し続けることで実現できます。PriorityQueue を使いましょう。
注意点として 一度 PriorityQueue に格納したマスは再度格納してはならないことと、自身の強さの 1 / X 倍未満かどうかを判定するときにそのまま割り算してしまうと誤差で WA になる場合があることです。
long a = 9007199254740993;
long b = 16384;
long c = 549755813888;
このとき 1.0 * a / b を計算すると c と一致しますが、実は両者は同じではありません。両辺に b を掛けてから a と c * b を比較すると 1 違うことがわかります。
なので割り算ではなく掛け算で比較します。このとき乗算に伴うオーバーフローが予想されますが、すべてのスライムの強さの総和は Math.Pow(10, 18) を超えないので、吸収できるか判定対象となるスライムの強さ × X が Math.Pow(10, 18) を超える場合は吸収できないことがわかります。
|
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 |
using System.Diagnostics; class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } long[] ReadLongArray() => Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); (int H, int W, int X) = ReadInt3(); (int P, int Q) = ReadInt2(); P--; Q--; long[,] grid = new long[H, W]; for (int r = 0; r < H; r++) { long[] vs = ReadLongArray(); for (int c = 0; c < W; c++) grid[r, c] = vs[c]; } // 周囲のマスを取得する List<(int, int)> GetNexts(int r, int c) { List<(int, int)> res = new List<(int, int)>(); if (r > 0) res.Add((r - 1, c)); if (r < H - 1) res.Add((r + 1, c)); if (c > 0) res.Add((r, c - 1)); if (c < W - 1) res.Add((r, c + 1)); return res; } // マスの位置から一意の文字列を取得する（同じマスを何度も PriorityQueue に格納させないため） string GetKey(int r, int c) => $"{r},{c}"; PriorityQueue<(int, int), long> pq = new PriorityQueue<(int, int), long>(); long ans = grid[P, Q]; HashSet<string> set = new HashSet<string>(); set.Add(GetKey(P, Q)); var nexts = GetNexts(P, Q); foreach (var next in nexts) { pq.Enqueue((next.Item1, next.Item2), grid[next.Item1, next.Item2]); set.Add(GetKey(next.Item1, next.Item2)); } while (pq.Count > 0) { var cur = pq.Dequeue(); // 除算に伴う誤差で落ちるケースがある // if (grid[cur.Item1, cur.Item2] >= (double)ans / X) // break; // 両辺に X を掛けて比較する // grid の値をすべて足しても Math.Pow(10, 18)を超えることはないので // 超えてしまう場合は条件を満たさない。 if (1.0 * grid[cur.Item1, cur.Item2] * X > Math.Pow(10, 18)) break; if (grid[cur.Item1, cur.Item2] * X >= ans) break; ans += grid[cur.Item1, cur.Item2]; nexts = GetNexts(cur.Item1, cur.Item2); foreach (var next in nexts) { if (!set.Contains(GetKey(next.Item1, next.Item2))) { pq.Enqueue((next.Item1, next.Item2), grid[next.Item1, next.Item2]); set.Add(GetKey(next.Item1, next.Item2)); } } } Console.WriteLine(ans); } } |
C – Socks 2
問題の概要
i 番目の組は色 i の靴下 2 枚からなる N 組の靴下がある。
配列 A で与えられる色の靴下を 1 枚ずつなくしてしまった。
残りの靴下でペアを作りたいが 2 枚の色の差の総和ができるだけ小さくなるようにしたい。
差の総和の最小値は？ 残りの靴下が奇数枚の場合、1枚は使われることはない。
残りの靴下の色が格納されている昇順でソートされた配列 B をつくります（同じ色が 2 枚ある場合は同じ値を 2 回格納する）。
B の長さが偶数の場合は隣り合う要素の差の総和を計算すればそれが解となります。奇数の場合はどれか 1 枚を除外して同じように差の総和を計算すればいいのですが、この処理はどうやって高速化すればいいでしょうか？
まず先頭から隣り合う要素の差を計算して、その累積和を計算します。次に後方からも同じように後方からの累積和を計算します。あとは両者の組み合わせから 1 枚だけ取り除いた 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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int K) = ReadInt2(); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); HashSet<int> set = new HashSet<int>(A); List<int> B = new List<int>(); for (int i = 1; i <= N; i++) { B.Add(i); if (!set.Contains(i)) B.Add(i); } if (B.Count % 2 == 0) { long ans = 0; for (int i = 0; i < B.Count; i += 2) ans += B[i + 1] - B[i]; Console.WriteLine(ans); } else { // 先頭からの差の累積和 List<long> sums1 = new List<long>(); sums1.Add(0); for (int i = 0; i + 1 < B.Count; i += 2) sums1.Add(sums1.Last() + B[i + 1] - B[i]); // 最後尾からの差の累積和 List<long> sums2 = new List<long>(); sums2.Add(0); for (int i = B.Count - 1; i - 1 >= 0; i -= 2) sums2.Add(sums2.Last() + B[i] - B[i - 1]); sums2.Reverse(); long ans = long.MaxValue; for (int i = 0; i < sums1.Count; i++) ans = Math.Min(ans, sums1[i] + sums2[i]); Console.WriteLine(ans); } } } |
E – Takahashi Quest
問題の概要
N 個の出来事がおきる。
t[i] = 1 のとき、タイプ x[i] のポーションを 1 つ発見する。
このときはこれを拾うか何もしないかの選択をする。
t[i] = 2 のとき、タイプ x[i] の敵と遭遇する。
もしタイプ x[i] のポーションを持っている場合、それを 1 つ消費することで敵を倒すことができる。
持っていない場合は敵に敗北する。
すべての敵を倒すことはできるだろうか？ できない場合は -1 を出力せよ。
できる場合は途中で持っているポーションの個数の最大値 K を最小化しようとしたとき、その値は何になるだろうか？ また t[i] = 1 のすべてのときにポーションを拾うかどうかについて出力せよ。
ポーションを見つけたとき、それを使用するかどうかはそのときにはわかりません。そこで敵に遭遇したときに過去に遡って必要なポーションを見つけたときはこれを手に入れるようにします。また手持ちのポーションは少ないほうがよいので過去に遡るときは現在に一番近い時間にします。
各種類のポーションをみつけた時刻をスタックに格納すれば、現在にもっとも近い時間がわかります。各時間においてポーションの増減を記録する配列（ポーションを拾う：1, ポーションを使う：-1, なにもしない：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 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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); Stack<int>[] stacks = new Stack<int>[N]; for (int i = 0; i < N; i++) stacks[i] = new Stack<int>(); int[] T = new int[N]; int[] X = new int[N]; for (int i = 0; i < N; i++) { string[] vs = Console.ReadLine().Split(); T[i] = int.Parse(vs[0]); X[i] = int.Parse(vs[1]) - 1; } int[] diffs = new int[N]; for (int i = 0; i < N; i++) { int t = T[i]; int x = X[i]; if (t == 1) stacks[x].Push(i); if (t == 2) { if (stacks[x].Count > 0) { int pop = stacks[x].Pop(); diffs[pop] = 1; // ポーションを拾うべき時刻 diffs[i] = -1; // いま使ったので -1 } else { Console.WriteLine(-1); return; } } } int K = 0; int cnt = 0; for (int i = 0; i < N; i++) { cnt += diffs[i]; K = Math.Max(K, cnt); } // タイプ 1 のクエリのときだけなので負数が格納されている要素は不要 diffs = diffs.Where(_ => _ >= 0).ToArray(); Console.WriteLine(K); Console.WriteLine(string.Join(" ", diffs)); } } |
D – Printing Machine
問題の概要
N 個の商品がベルトコンベア上を流れている。ベルトコンベアには印字機が取り付けられており、商品 i は今から T[i] μs後に印字機の範囲に入り、その D[i] μs後に印字機の範囲から出る。
この印字機は、1 μs おきにその範囲内にある商品 1 つに一瞬で印字ができる（印字機の範囲に入る瞬間や範囲から出る瞬間を含む）。この印字機は最大で何個の商品に印字することができるだろうか？
印字機の範囲内に複数の商品がある場合、範囲外へ出る時刻が迫っているものから印字すべきです。そこでそのようなシミュレーションをおこないます。T の範囲が最大で 10^18, 印字機の範囲内にある時間も 10^18 ですが、印字機の範囲内に商品がない場合は時刻を先に進めてしまえばシミュレーション可能です。
|
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 N = int.Parse(Console.ReadLine()); // 入る時刻が同じものをまとめる Dictionary<long, List<long>> dic = new Dictionary<long, List<long>>(); for (int i = 0; i < N; i++) { string[] vs = Console.ReadLine().Split(); long s = long.Parse(vs[0]); long t = s + long.Parse(vs[1]); if(!dic.ContainsKey(s)) dic.Add(s, new List<long>()); dic[s].Add(t); } // 入る時間順に Queue に格納する Queue<KeyValuePair<long, List<long>>> q = new Queue<KeyValuePair<long, List<long>>>(dic.OrderBy(_ => _.Key)); // 印字機の範囲内に入ったものを出る時刻が早い順に格納する PriorityQueue<long, long> pq = new PriorityQueue<long, long>(); int ans = 0; long t_max = (long)Math.Pow(10, 18) * 2; for (long cur = 0; cur <= t_max; cur++) { // この時刻に範囲内に入る商品がある if (q.Count > 0 && q.Peek().Key == cur) { var vs = q.Dequeue().Value; foreach (var t in vs) pq.Enqueue(t, t); } // 範囲内に商品がないなら範囲内に入る商品が出現する時刻まで現在時刻をすすめる if (pq.Count == 0 && q.Count > 0) { var d = q.Dequeue(); cur = d.Key; var vs = d.Value; foreach (var t in vs) pq.Enqueue(t, t); } // 範囲内にある商品は存在しないし、これから範囲内に入る商品も存在しない（終了） if (pq.Count == 0 && q.Count == 0) break; // すでに印字機の範囲外に出たものは PriorityQueue から取り除く while (pq.Count > 0 && pq.Peek() < cur) pq.Dequeue(); // 印字可能な商品に印字する（印字は1回だけなので PriorityQueue から取り除く） if (pq.Count > 0) { pq.Dequeue(); ans++; } } Console.WriteLine(ans); } } |
F – Vouchers
問題の概要
N 個の商品が売られていて 商品の定価は P[i] 円です。
M 枚のクーポンがあり、i 枚目のクーポンは定価が L[i] 円以上の商品に対して使うことができ、定価より D[i] 円安く買うことができる。
複数の商品に同じクーポンを使ったり、同じ商品に複数のクーポンを使うことはできない。
すべての商品を買うのに必要な最小の金額は？
値段の安い順に商品を見ていき、使えるクーポンがあるならばその中で最も D[i] が大きいクーポンを使用して商品を買えばよいです。PriorityQueue を使えば解けます。
|
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, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int N, int M) = ReadInt2(); int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] L = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] D = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); List<(int, int)> vs = new List<(int, int)> (); for (int i = 0; i < N; i++) vs.Add((P[i], 0)); for (int i = 0; i < M; i++) vs.Add((L[i], D[i])); vs = vs.OrderBy(_ => _.Item1).ThenByDescending(_ => _.Item2).ToList(); long minus = 0; PriorityQueue<int, int> pq = new PriorityQueue<int, int>(); foreach (var pair in vs) { if (pair.Item2 > 0) pq.Enqueue(pair.Item2, - pair.Item2); else if(pq.Count > 0) minus += pq.Dequeue(); } long ans = 0; for (int i = 0; i < N; i++) ans += P[i]; Console.WriteLine(ans - minus); } } |
