AtCoder NoviStepsを埋めてみる(1) 貪欲法 3Q以下の続きです。ちょっと難しめの問題を考えます。
Contents
082 – Interval Scheduling Problem
082 – Interval Scheduling Problem
問題の概要は以下のとおりです。
N 本の映画が上映されます。i 番目の映画は時刻 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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); int a = int.Parse(vs[0]); int b = int.Parse(vs[1]); return (a, b); } int N = int.Parse(Console.ReadLine()); PriorityQueue<(int, int), int> pq = new PriorityQueue<(int, int), int>(); for (int i = 0; i < N; i++) { (int l, int r) = ReadInt2(); pq.Enqueue((l, r), r); } int ans = 0; int cur_time = 0; while (pq.Count > 0) { while(pq.Count > 0) { if (cur_time > pq.Peek().Item1) pq.Dequeue(); else break; } if (pq.Count > 0) { var lr = pq.Dequeue(); cur_time = lr.Item2; ans++; } } Console.WriteLine(ans); } } |
079 – Two by Two（★3）
問題の概要は以下のとおりです。
H×W の 二次元配列 A が与えられる。
A[x, y], A[x + 1, y], A[x, y + 1], A[x + 1, y + 1]の値を 1 増やすか減らすかの処理を繰り返すことで、A を B に一致させることは可能か？ 可能ならば最小の操作回数は？
A[0, 0]からみていきA[x, y]とB[x, y]に違いがあれば同じになるようにA[x, y], A[x + 1, y], A[x, y + 1], A[x + 1, y + 1]の値を同時に更新します。この方法で B と一致するならその回数を出力します。この方法で一致させることができないならどうやっても一致させることはできないので”No”を出力します。オーバーフローに注意。
|
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 |
class Program { static void Main() { string[] vs1 = Console.ReadLine().Split(); int H = int.Parse(vs1[0]); int W = int.Parse(vs1[1]); long[,] A = new long[H, W]; for (int r = 0; r < H; r++) { int[] vs2 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int c = 0; c < W; c++) A[r, c] = vs2[c]; } long[,] B = new long[H, W]; for (int r = 0; r < H; r++) { int[] vs2 = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int c = 0; c < W; c++) B[r, c] = vs2[c]; } long ans = 0; for (int r = 0; r < H - 1; r++) { for (int c = 0; c < W - 1; c++) { if (A[r, c] != B[r, c]) { long diff = B[r, c] - A[r, c]; A[r, c] += diff; A[r, c + 1] += diff; A[r + 1, c] += diff; A[r + 1, c + 1] += diff; ans += Math.Abs(diff); } } } // 処理がすべて終わったら本当に A と B が一致しているかチェックする for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (A[r, c] != B[r, c]) { Console.WriteLine("No"); return; } } } Console.WriteLine("Yes"); Console.WriteLine(ans); } } |
D – Take ABC 2
問題の概要
A, B, C の 3 種類の文字のみからなる文字列 S が与えられる。
S[i] = A, S[j] = B, S[k] = C（ただし i ＜ j ＜ k） を満たす(i, j, k) の組を選び、この文字を取り除く。
残った文字を元の順序を保ったまま左に詰める。
この処理は最大何回繰り返すことができるだろうか？
(i, j, k) の組は大小関係のみを満たしていればよく、連続している必要はありません。なので、最初に見つけた’A’、そのあとにある最初に見つけた’B’、さらにそのあとにある最初に見つけた’C’を削除するという処理を繰り返せばよいです。
問題はどうやってこの処理をおこなうかです。まず文字 ‘A’,’B’,’C’のインデックスをQueueに格納します（qA, qB, qC）。そして’B’のインデックス（idx_b）を取り出します。もしqAに格納されている最小値が idx_b よりも大きければこの idx_b は使いようがありません。なのでこれは捨ててしまって次の idx_b について調べます。
また qC に格納されている idx のなかで idx_b より小さいものも使えません。idx_b はループを繰り返すたびに大きくなっていくので置いておいても使い道はないので qC.Peek() < idx_b である限り qC に格納されている値は捨ててしまいます。
こうして捨てられずに残った qA と qC の先頭の要素と idx_b が S[i] = A, S[j] = B, S[k] = C を満たす(i, j, k) の組です。これを数えればよいです。途中で Queue が空になったら終了です。
|
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 |
class Program { static void Main() { char[] S = Console.ReadLine().ToArray(); Queue<int> qA = new Queue<int>(); Queue<int> qB = new Queue<int>(); Queue<int> qC = new Queue<int>(); for (int i = 0; i < S.Length; i++) { char ch = S[i]; if (ch == 'A') qA.Enqueue(i); if (ch == 'B') qB.Enqueue(i); if (ch == 'C') qC.Enqueue(i); } int ans = 0; foreach (var idx_b in qB) { // 使える idx_a が存在しない。終了 if (qA.Count == 0) break; // idx_b より小さい idx_a が存在しない。この B は使えない if (qA.Peek() > idx_b) continue; // idx_b より小さい C は使えない while (qC.Count > 0 && qC.Peek() < idx_b) qC.Dequeue(); // 使える C が存在しない。終了 if (qC.Count == 0) break; // 使える idx_a, idx_c が見つかった int idx_a = qA.Dequeue(); int idx_c = qC.Dequeue(); ans++; } Console.WriteLine(ans); } } |
C – AtCoder Riko
問題の概要
長さ L の棒が何本かある。そのうちいくつか（0本や全部の場合もありうる）が２つに折れてしまった。
これによって棒は全部で N 本になり、i 本目の棒の長さは A[i]である。
L としてありうる長さをすべて求めよ（ただし必ず解がひとつ以上存在する入力しか与えられない）。
考えられるパターンとして、(1)棒はすべて折れてしまった。(2)折れずにそのままの棒が存在する のふたつがあります。
すべて折れてしまったのであれば棒の総数は偶数であり、一番長い棒と一番短い棒、二番目に長い棒と二番目に短い棒・・・の長さの合計が同じ値になるはずです。
折れずにそのままの棒が存在するのであれば、その棒はもっとも長い棒です。この棒を取り除いて(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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Array.Sort(A); // 長いものと短いものを組み合わせることで合計が target になるか調べる bool Check(int[] arr, int target) { int len = arr.Length; if (len % 2 == 0) { List<int> vs = new List<int>(); for (int i = 0; i < len; i++) { if (arr[i] + arr[len - 1 - i] != target) return false; } return true; } return false; } List<int> ans = new List<int>(); int ans1 = A[0] + A[N - 1]; // (1)の場合の仮の答え if (Check(A, ans1)) ans.Add(ans1); int max = A.Last(); // (2)の場合の仮の答え A = A.Where(_ => _ != max).ToArray(); if (Check(A, max)) ans.Add(max); ans = ans.OrderBy(_ => _).ToList(); Console.WriteLine(string.Join(" ", ans)); } } |
C – Alternated
問題の概要
文字 ‘A’, ‘B’ を N 個ずつ含む長さ 2N の文字列 S が与えられる。
S に対して隣り合う文字を入れ替える操作をおこなって同じ文字が隣り合う箇所がない状態にしたい。
操作回数の最小値を求めよ。
同じ文字が隣り合う箇所がない状態にするには “ABABAB…” とするか “BABABA…” とするしかありません。
‘A’の位置に着目して S のなかにある’A’の位置をリストに格納します。また “ABABAB…” としたときの’A’の位置と “BABABA…” としたときの’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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); char[] S = Console.ReadLine().ToArray(); List<int> A = new List<int>(); List<int> X = new List<int>(); List<int> Y = new List<int>(); for (int i = 0; i < N * 2; i++) { if(S[i] == 'A') A.Add(i); if(i % 2 == 0) X.Add(i); else Y.Add(i); } long x_sum = 0; long y_sum = 0; for (int i = 0; i < N; i++) { x_sum += Math.Abs(A[i] - X[i]); y_sum += Math.Abs(A[i] - Y[i]); } Console.WriteLine(Math.Min(x_sum, y_sum)); } } |
D – Get Many Stickers
問題の概要は以下のとおり。
最初、中身が入ったコーラが N 本ある。
空き瓶を中身が入ったコーラに交換してくれる店が M 箇所にある。i 番目の店では A[i] 本の空き瓶と引き換えに B[i] 本のコーラと記念のシール 1 枚をもらうことができる。
シールをできるだけたくさん集めたい。最大で何枚集めることができるだろうか？
シールをたくさんもらいたいのであれば空き瓶を交換するときに所持する瓶の総数ができるだけ減らないようにすべきです。そこで交換する店は A[i] – B[i] が小さく、A[i]が現在所持する空き瓶以下のものを選び続けるべきです。
N が大きいので交換するたびに N から A[i] – B[i] を引き続けては実行制限時間以内に処理が終わりません。割り算をしてまとめて処理をしたいのですが、N から A[i] を引いた段階で N が負数にならないような交換方法を採用する必要があります。
そのために N から A[i]だけ引いたものを割り算してまとめて交換処理をしています。ただこの方法だと1本も交換できない場合があるのでその場合は普通に1回分ずつ交換の処理をしています。
|
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() { (long, long) ReadLong2() { string[] vs = Console.ReadLine().Split(); long a = long.Parse(vs[0]); long b = long.Parse(vs[1]); return (a, b); } (long N, long M) = ReadLong2(); PriorityQueue<(long, long), long> pq = new PriorityQueue<(long, long), long>(); for (int i = 0; i < M; i++) { (long a, long b) = ReadLong2(); pq.Enqueue((a, b), a - b); } long ans = 0; while (pq.Count > 0) { while (pq.Count > 0 && pq.Peek().Item1 > N) pq.Dequeue(); if (pq.Count > 0) { var tp = pq.Peek(); long diff = tp.Item1 - tp.Item2; // まとめて複数回分の交換ができるかもしれない // 割り算するまえに店にわたす瓶の数を引いて、交換途中でNが負数になるのを防ぐ long n = N - tp.Item1; long cnt = n / diff; ans += cnt; N -= tp.Item1 * cnt; N += tp.Item2 * cnt; // 普通に1回分の交換処理をする if (cnt == 0) { N -= diff; ans++; } } } Console.WriteLine(ans); } } |
C – Giant Domino
問題の概要
1 から N までの番号がついた N 個のドミノがある。ドミノ i の大きさは S[i] である。
ドミノが右に向けて倒れる時、そのすぐ右に置かれているドミノの大きさがその 2倍 以下であればそれも右に倒れる。
一番左に 1 番目のドミノ、一番右に N 番目のドミノを配置してすべてのドミノが倒れるようにしたい。
そのために必要なドミノの最小個数は何個だろうか？
左側においたドミノの2倍以下のもので、最大または N 番目のドミノを右に配置していけばよいです。
|
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 |
class Program { static void Main() { int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int ans = Solve(N, A); Console.WriteLine(ans); } int Solve(int N, int[] A) { // 中間のドミノをリストに格納してソートする // ただし A[0]以下のもの、A.Last 以上のもの、値が重複しているものは不要 List<int> vs = new List<int>(); for (int i = 1; i < N - 1; i++) { if(A[N - 1] > A[i] && A[0] < A[i]) vs.Add(A[i]); } vs = vs.Distinct().OrderBy(_ => _).ToList(); // 二分探索法で vs のなかから target 以下の最大の数を探す int Search(int target) { int ok = -1; int ng = vs.Count; while (Math.Abs(ok - ng) > 1) { var mid = (ok + ng) >> 1; if (vs[mid] <= target) ok = mid; else ng = mid; } if (ok >= 0) return vs[ok]; else return -1; } int cur = A[0]; int last = A[N - 1]; int ans = 1; // 現在のドミノの2倍以下の大きさのドミノで最大のものを取得し、これでcurを更新していく。 while (true) { // N 番ドミノをおくことができるなら置いて終了 if (cur * 2 >= last) { ans++; break; } int target = cur * 2; int res = Search(target); // cur の値を大きな値で更新できないということは // これより大きなドミノで置くことができるものは存在しないことを意味する //（つまり不可能） if (cur == res) { ans = -1; break; } cur = res; ans++; } return ans; } } } |
