現在、AtCoderに挑戦しているのですが、なかなかレーティングが上がりません。2026年に念願の緑色コーダーに昇格できたのですが、茶落ちしてしまい、現在はこんな状態です。
現状打開のためにAtCoder NoviStepsに収録されている問題をやってみることにします。アルゴリズムやデータ構造別に良問がまとまっていて学習には最適です。
記念すべき初回は「貪欲法」です。
貪欲法とは、最適化問題において、1 ステップ先のことのみを考えて最適化する判断を繰り返して、解を作り上げていく方法です。簡単な問題もありますが、難しい問題もあります。
ここではAtCoder NoviSteps内で3Q以下に分類されている問題を解いてみます。問題数が多いので全部はやりません。簡単すぎる問題はスルーします。難しすぎる問題はそもそも解けません。
Contents
B – Addition and Multiplication
B – Addition and Multiplication
問題の概要は以下のとおりです。
最初 変数 X は 1 である。X を2倍にするか K を足す操作を N 回繰り返す。操作後の X の最小値は何か？
これはXを2倍にした場合とKを足した場合とではどちらが大きくなるかを比較して小さくなる方法でXを更新していけばよいです。NとKの値はそんなに大きくないのでオーバーフローを気にする必要はありません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int K = int.Parse(Console.ReadLine()); int X = 1; for (int i = 0; i < N; i++) X = Math.Min(X * 2, X + K); Console.WriteLine(X); } } |
こんな問題ばっかりなら簡単なのですが、実際にはそうはいきません。
C – 最高のピザ (Best Pizza)
問題の概要は以下のとおり。
1 ドルあたりのカロリーが最大となるようなピザを注文したい。
生地の値段は A ドルでありトッピングは N 種類あるが値段はいずれも B ドルである。
生地のカロリーは C calであり、各トッピングのカロリーは D[i] calである。
同じ種類のトッピングを複数乗せることはできない。
トッピングを乗せるのであればカロリーが高い順に乗せていきたいです。そこでカロリーが高い順にソートして生地の上に次々と乗せていきます。その都度 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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); string[] vs = Console.ReadLine().Split(); int A = int.Parse(vs[0]); int B = int.Parse(vs[1]); int C = int.Parse(Console.ReadLine()); int[] D = new int[N]; for (int i = 0; i < N; i++) D[i] = int.Parse(Console.ReadLine()); D = D.OrderByDescending(_ => _).ToArray(); int sum_cost = A; int sum_cal = C; int ans = sum_cal / sum_cost; foreach (var d in D) { sum_cal += d; sum_cost += B; ans = Math.Max(ans, sum_cal / sum_cost); } Console.WriteLine(ans); } } |
014 – We Used to Sing a Song Together（★3）
014 – We Used to Sing a Song Together（★3）
問題の概要は以下のとおり。
長さ N の非負整数列 A と B が与えられる。
B を並べ替えたものを C としたとき、A[i] – C[i]の絶対値の総和の最小値を求めよ。
これは両者をソートして前から順番に差の絶対値を計算して総和を出力するだけでよいです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Array.Sort(A); Array.Sort(B); long ans = 0; for (int i = 0; i < N; i++) ans += Math.Abs(A[i] - B[i]); Console.WriteLine(ans); } } |
C – Robot Factory
問題の概要は以下のとおり。
自然数の数列 H と B が与えられる。
H[i] ≦ B[i] になるようなペアを K 個以上つくることができるか調べよ。
H と B をソートして先頭からみていきます。H[i] ≦ B[i] となるのであればペアを作ってしまい、できないのであれば B[i]が小さすぎるので捨ててしまって次の要素をみることにします（お互いソートされているのでH[i]以降はH[i]と同じかもっと大きい値しかない。B[i]のペアになりうる要素は絶対に見つからない）。比較対象がなくなったらペアの数を調べます。
比較するときに H と B のインデックスがズレていくのでHを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 |
class Program { static void Main() { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); int K = int.Parse(vs[2]); int[] H = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Array.Sort(H); Array.Sort(B); Queue<int> qH = new Queue<int>(H); int cnt = 0; foreach (var b in B) { if (qH.Count == 0) break; if (b >= qH.Peek()) { qH.Dequeue(); cnt++; if (cnt == K) { Console.WriteLine("Yes"); return; } } } Console.WriteLine("No"); } } |
C – Security 2
問題の概要は以下のとおり。
操作 A： 数字の文字列の最後に 0 が追加される
操作 B: 文字列の数字がひとつ増える（ただし 9 に 1 加算した場合は 0 とする）
文字列 S が与えられる。空文字列に対して A, B の操作を繰り返して S と一致させたい。操作の回数を最小化するのであれば何回になるだろうか？
一見ややこしそうだが、あることに気づけば簡単です。
S[i] と S[i + 1]の差を diff[i]（ただし負数になる場合は10を足して非負数化する）と定義すると操作 B の前と後では diff の値は変わりません。そこで 0 を追加したらdiff[i]回だけ 操作 B をおこない、そのあと 0 を追加する処理を繰り返します。最後まできたら最後の位の値の回数だけ 操作 B をおこないます。これで操作 B をおこなう回数の合計値がわかります。また操作 A の回数は S の長さと同じなので、両者をあわせた回数が解となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Program { static void Main() { char[] S = Console.ReadLine().ToArray(); int ToInt(char ch) { return ch - '0'; } int ans = S.Length; for (int i = 0; i < S.Length - 1; i++) { int diff = ToInt(S[i]) - ToInt(S[i + 1]); if (diff < 0) diff += 10; ans += diff; } ans += ToInt(S.Last()); Console.WriteLine(ans); } } |
A – ストーブ (Stove)
問題の概要は以下のとおり。
部屋に客がいるときは必ずストーブがついている状態にしたい。
ストーブがついている時間の合計を最小化したいが、ストーブをつけることができる回数には制限がある。
ストーブがついている時間の合計の最小値は？
ストーブをつけることができる回数は K 回までという制限があるが、これは逆にいうと最初の客が来て最後の客が帰るまでのあいだにストーブが消えている時間帯が(K – 1)個あってもよいことを意味しています。
そこで最初の客が来て最後の客が帰るまでの時間を計算し、ここから客がいない時間帯のうち長いものから(K – 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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int K = int.Parse(vs[1]); int[] T = new int[N]; for (int i = 0; i < N; i++) T[i] = int.Parse(Console.ReadLine()); int ans = T[N - 1] + 1 - T[0]; // 最初の客が来て最後の客が帰るまでの時間 List<int> intervals = new List<int>(); for (int i = 0; i < N - 1; i++) intervals.Add(T[i + 1] - (T[i] + 1)); intervals = intervals.OrderByDescending(_ => _).ToList(); ans -= intervals.Take(K - 1).Sum(); Console.WriteLine(ans); } } |
C – 次のアルファベット
問題の概要は以下のとおり。
英小文字のみからなる文字列 S がある。
このなかから1文字だけ選んで次の文字（’z’の次は’a’）に変える処理を K 回繰り返す。
辞書順で最小の文字列は何か？
辞書順で最小の文字列にしたいのであれば先頭から’a’にできる部分はそのようにしてしまえばよいです。逆にできない場合は現状維持をすべきです。ちょうど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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); char[] S = Console.ReadLine().ToArray(); int K = int.Parse(Console.ReadLine()); // a にするために必要な回数を求める int F(char ch) { if (ch == 'a') return 0; return 'a' + 26 - ch; } for (int i = 0; i < S.Length; i++) { int f = F(S[i]); if (K >= f) { K -= f; S[i] = 'a'; } } if (K > 0) { K %= 26; int last = S.Last(); last += K; if (last > 'z') last -= 26; S[S.Length - 1] = (char)last; } Console.WriteLine(new string(S)); } } |
B – 島と橋
問題の概要は以下のとおり。
島の数 N と 島民の数である整数列 A が与えられる。
すべての島に同じ人数の住人が住むようにしたい。
橋をいくつ架ける必要があるか？
島民の総和が 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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int sum = A.Sum(); if (sum % N != 0) // 不可能 { Console.WriteLine(-1); return; } int v = sum / N; int ans = 0; for (int i = 0; i < N - 1; i++) { if (A[i] != v) { int diff = A[i] - v; A[i] = v; A[i + 1] += diff; // 一時的にA[i+1]が負数になってもかまわないので移動させる ans++; } } Console.WriteLine(ans); } } |
C – 民族大移動
問題の概要は以下のとおりです。
N 個の街と、K 種類の民族が存在する。
i 番目の民族は街 S[i] に住んでいる。
D 日間かけて民族大移動がおこなわれる。i 番目の民族の移動先は街 T[i] である。
移動可能なのは i日目に移動可能なのは L[i] から R[i] 番目の連続する街の間だけである。
各民族について目的地に到着できる最も早い日は移動開始から何日目？
目的地に向かって移動可能であれば移動できるところまで移動して問題ありません。目的地にもっと接近できるけどあえてしないことで得られるメリットはありません。以下のコードでACできます。
|
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 |
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, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); int a = int.Parse(vs[0]); int b = int.Parse(vs[1]); int c = int.Parse(vs[2]); return (a, b, c); } (int N, int D, int K) = ReadInt3(); int[] L = new int[D]; int[] R = new int[D]; for (int i = 0; i < D; i++) { (int l, int r) = ReadInt2(); L[i] = l; R[i] = r; } int[] S = new int[K]; int[] T = new int[K]; for (int i = 0; i < K; i++) { (int s, int t) = ReadInt2(); S[i] = s; T[i] = t; } int[] ans = new int[K]; for (int d = 0; d < D; d++) { for (int i = 0; i < K; i++) { if (S[i] == T[i]) // すでに移動完了 continue; if (L[d] <= S[i] && S[i] <= R[d]) { if (L[d] <= T[i] && T[i] <= R[d]) { // 移動完了 S[i] = T[i]; ans[i] = d + 1; } else if (T[i] < L[d]) // 左に移動する S[i] = L[d]; else if (R[d] < T[i]) // 右に移動する S[i] = R[d]; } } } foreach (var v in ans) Console.WriteLine(v); } } |
次回は貪欲法のなかでやや難しめの問題にも挑戦してみることにします。
