は？「計算結果がK番目に大きくなる組を求める」？ 何を言っているの？と思うかもしれませんが、こういうことです。
Contents
D – Cake 123
問題の趣旨は「配列 A, B, C が与えられる。A[i] + B[j] + C[k] が大きい順に K 個出力せよ」というものです。
ただし配列の長さは最大 1,000 なので全パターン（10億通り）試して上位 K 個を取るという解法は使えません。
こんなときに使えるのが優先度付きキュー（priority queue）です。優先度付きキューは格納するデータに優先度を設定して優先度の値が小さい順に取り出すことができるデータ構造です。取り出すことができるのは先頭の値だけですが、全体をソートするときの時間計算量が O(NlogN) であることに対して優先度付きキューであれば O(logN) であることが魅力です。
まず配列 A, B, C を降順（値が大きい順）にソートします。すると A[i] + B[j] + C[k] が一番大きくなるのは A[0] + B[0] + C[0] です。
では二番目に大きいものは何でしょうか？ A[1] + B[0] + C[0]、 A[0] + B[1] + C[0]、A[0] + B[0] + C[1] のどれかです。ここでは仮に二番目に大きなものを A[1] + B[0] + C[0] とします。すると三番目に大きなものは A[2] + B[0] + C[0]、A[1] + B[1] + C[0]、A[1] + B[0] + C[1] のどれかになります。
このようにどれかひとつの配列の添字をひとつだけ進めたものを優先度付きキューに格納していきます。そして格納したデータを取り出したらそのデータを元にそのどれかひとつの配列の添字をひとつだけ進めたものを優先度付きキューに格納していくという処理を繰り返します。これを K 回繰り返せばこの問題に正解することができます。
注意する点として優先度付きキューに一度格納した添字で生成されたデータを格納しないようにすることです。これは HashSet を使えば解決できそうです。
|
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 |
class Program { static void Main() { (int, int, int, int) ReadInt4() { int[] arr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); return (arr[0], arr[1], arr[2], arr[3]); } long[] ReadLongArray() => Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); (int X, int Y, int Z, int K) = ReadInt4(); long[] A = ReadLongArray(); long[] B = ReadLongArray(); long[] C = ReadLongArray(); // 降順にソート Array.Sort(A); Array.Reverse(A); Array.Sort(B); Array.Reverse(B); Array.Sort(C); Array.Reverse(C); PriorityQueue<(int, int, int, long), long> pq = new PriorityQueue<(int, int, int, long), long>(); HashSet<string> set = new HashSet<string>(); // 優先度付きキューに格納してよいのであれば格納する void Enqueue(int a, int b, int c) { if (a >= X || b >= Y || c >= Z) // 配列外アクセスのチェック return; long v = A[a] + B[b] + C[c]; string key = $"{a},{b},{c}"; if (!set.Contains(key)) // すでに格納しているものであれば何もしない { pq.Enqueue((a, b, c, v), -v); // 値が大きい順に取得したいので優先度の符号を反転 set.Add(key); } } Enqueue(0, 0, 0); // 一番大きなデータ for (int i = 0; i < K; i++) { var tp = pq.Dequeue(); // i 番目に大きな値とそのときの添字が取得できる Console.WriteLine(tp.Item4); // 次に大きな値になるのは a, b, c のどれかひとつを進めたものである Enqueue(tp.Item1 + 1, tp.Item2, tp.Item3); Enqueue(tp.Item1, tp.Item2 + 1, tp.Item3); Enqueue(tp.Item1, tp.Item2, tp.Item3 + 1); } } } |
E – Set Meal
もう一題解いてみます。
食べ合わせが悪くならない組み合わせ以外でもっとも価格が高くなる定食の値段を求めよという問題です。
これも価格がもっとも高くなるものを求め、食べ合わせが悪い場合は配列の添字をそれぞれひとつずつズラしていけば解を得ることができます。
ソートするともとの添字がわからなくなってしまい、食べ合わせができなくなるので Pairクラスを定義してもともとの添字と値のペアを作ってます。あとは前述の問題と同じです。PriorityQueue を Dequeue することで価格が大きな順でメニューの組み合わせを得ることができるので、ここからもとの添字を取得して食べ合わせの確認をおこないます。問題ない組み合わせが見つかったらそれが解です。
|
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 |
class Program { class Pair { public Pair(int idx, long v) { Index = idx; Value = v; } public int Index = 0; public long Value = 0; } static void Main() { (int, int) ReadInt2() { int[] arr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); return (arr[0], arr[1]); } (int, int, int) ReadInt3() { int[] arr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); return (arr[0], arr[1], arr[2]); } long[] ReadLongArray() => Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); (int N, int M, int L) = ReadInt3(); long[] A = ReadLongArray(); long[] B = ReadLongArray(); List<Pair> pairsA = new List<Pair>(); for (int i = 0; i < N; i++) pairsA.Add(new Pair(i, A[i])); List<Pair> pairsB = new List<Pair>(); for (int i = 0; i < M; i++) pairsB.Add(new Pair(i, B[i])); pairsA = pairsA.OrderByDescending(_ => _.Value).ToList(); pairsB = pairsB.OrderByDescending(_ => _.Value).ToList(); HashSet<string> ng = new HashSet<string>(); for (int i = 0; i < L; i++) { (int a, int b) = ReadInt2(); a--; b--; ng.Add($"{a},{b}"); } PriorityQueue<(int, int, long), long> pq = new PriorityQueue<(int, int, long), long>(); HashSet<string> set = new HashSet<string>(); void Enqueue(int a, int b) { if (a >= N || b >= M) return; long v = pairsA[a].Value + pairsB[b].Value; string key = $"{a},{b}"; if (!set.Contains(key)) { pq.Enqueue((a, b, v), -v); set.Add(key); } } Enqueue(0, 0); long ans = 0; while (true) { var tp = pq.Dequeue(); string key = $"{pairsA[tp.Item1].Index},{pairsB[tp.Item2].Index}"; if (ng.Contains(key)) { Enqueue(tp.Item1 + 1, tp.Item2); Enqueue(tp.Item1, tp.Item2 + 1); } else { ans = tp.Item3; break; } } Console.WriteLine(ans); } } |
