ひとりで勝手にはじめた蟻本読書会 n! 通りの全探索 next_permutation 意外と奥が深い全探索 蟻本読書会の続きです。
貪欲法は近似アルゴリズムの最も基本的な考え方の一つである。近似アルゴリズムとは組合せ最適化問題の近似解を得るためのアルゴリズムであり、問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法です。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考することはありません。
そのため得られる解は最適解であるという保証はないのですが、部分問題の解法と単純なソートのみでプログラムを実装することが可能です。また厳密解（最適解）が求まる場合もあります。以下の硬貨の問題はそれに該当します。
使用する硬貨の枚数を最小にする問題
500円硬貨、100円硬貨、50円硬貨、10円硬貨、5円硬貨、1 円硬貨が十分な数だけある。
買い物をしてレジで 1000円札を 1 枚出した時、おつりに使われる硬貨の枚数を最小にする場合、何枚使用すればよいか求めるプログラムを作成せよ。
たとえば 380円の買い物をした場合はお釣りは620円である。この場合は500円硬貨と100円硬貨がそれぞれ1枚ずつ、10円硬貨が2枚必要になる。そのため “4” を出力することになる。
まず1000円札を 1 枚出した時のおつりがいくらになるのかを求めます。そしてお釣りから負数にならないようにしながら、500 を引くことができるなら可能な回数だけ 500 を引き、100 を引くことができるなら可能な回数だけ 100 を引き、50 を引くことができるなら可能な回数だけ 50 を引き、… と1円硬貨まで考えていきます。
ただこの方法は 500, 100, 50, 10, 5, 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 |
using System; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int n = 1000 - N; // 1000円払ったときのお釣りは？ int ans = 0; while (n >= 500) { n -= 500; ans++; } while (n >= 100) { n -= 100; ans++; } while (n >= 50) { n -= 50; ans++; } while (n >= 10) { n -= 10; ans++; } while (n >= 5) { n -= 5; ans++; } while (n >= 1) { n -= 1; ans++; } Console.WriteLine(ans); } } |
区間スケジューリング問題
実際にいくつかの予定があり、それらが重複している。重複することなく一つでも多くの予定を選びとりたい。そんな問題が出されたらどうすればよいでしょうか？
なにも知らないと「開始時刻が早い予定を優先的に選んでいく」ことで近似解を得てそれで妥協することが多いのではないでしょうか？ 競技プログラミングではこれではダメです。厳密解が出せる問題ではその答えを出さなければなりません。
では、どうするのがよいでしょうか？
正解は「終了時刻が早い予定を優先的に選んでいく」です。これが「あとにより多くの選択肢を残せるようにする」ことにつながり、最適解を得ることができるようになるのです。
N 個のタスクがあります。i 個目のタスクは A_i 日目の朝に始まり、B_i 日目の夜に終わります。あなたはこれらのタスクを自由に選んで実行することができます。ただし、同じ日に複数のタスクを行うことはできません。実行可能なタスクの個数の最大値を求めてください。
入力されるデータ
N
A_1 B_1
A_2 B_2
…
A_N B_N
（ただし 1 ≦ N ≦ 2×10^5, 1 ≦ A_i ≦ B_i ≦ 10^9）
タスクの開始日と終了日をオブジェクトに格納し、このオブジェクトのリストをつくります。そしてリストを終了日が早い順にソートします。最初に選択できるタスクを取得したら終了日を記憶しておきます。そして次のタスクの開始日が記憶しておいた終了日よりもあとであれば新たに取得し、終了日を記憶する処理を繰り返します。これを何回繰り返したかが求める答えとなります。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Task { public Task(int start, int end) { Start = start; End = end; } public int Start { get; } public int End { get; } } class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<Task> tasks = new List<Task>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); tasks.Add(new Task(vs[0], vs[1])); } tasks = tasks.OrderBy(_ => _.End).ToList(); int ans = 0; int end = 0; foreach (Task task in tasks) { if (end < task.Start) { end = task.End; ans++; } } Console.WriteLine(ans); } } |
東西一列に並んだ N 個の島と N – 1 本の橋があります。i 番目の橋は、西から i 番目の島と西から i + 1 番目の島を接続しています。
ある日、いくつかの島同士で争いが起こり、島の住人たちから M 個の要望がありました。
要望 i は「西から a i 番目の島と西から b i 番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしい」です。
あなたは橋をいくつか取り除くことでこれら M 個の要望全てを叶えることにしました。取り除く必要のある橋の本数の最小値を求めてください。
入力されるデータ
2 ≦ N ≦ 10^5
1 ≦ M ≦ 10^5
1 ≦ a_i ＜ b_i ≦ N
わかりにくいかもしれませんが、実は区間スケジューリング問題です。
解説によると「被らないように区間を取った時に取れる最大個数が答えになるのでは？という天啓！」とあります。
ひとつの橋を取り除くことで複数の要望に応えることができる場合があります。しかし「被らない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 |
using System; using System.Collections.Generic; using System.Linq; class Task { public Task(int start, int end) { Start = start; End = end; } public int Start { get; } public int End { get; } } class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } List<Task> tasks = new List<Task>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); tasks.Add(new Task(vs[0], vs[1])); } tasks = tasks.OrderBy(_ => _.End).ToList(); int ans = 0; int end = 0; foreach (Task task in tasks) { if (end <= task.Start) { end = task.End; ans++; } } Console.WriteLine(ans); } } |
辞書順最小の文字列をつくる
最大で長さが2000の’A’～’Z’からなる文字列が与えられる。文字列の先頭か後尾から一文字ずつとっていって、辞書順で最小の文字列を作る場合、生成される文字列はなにか？
入力が ACDBCB なら ABCBCD を出力する
文字列の先頭か後尾から一文字ずつとっていって、辞書順で最小の文字列を作るという問題です。辞書順最小なものを求めよと言われたときにとにかく先頭から順に最小になることを優先していけばよいです。
文字列の先頭か後尾から一文字ずつとっていっていく場合、どちらが辞書順で小さいか調べてそれを取っていけばいいのですが、同じ場合はどうすればよいのでしょうか？ この場合は次、次も同じならさらに次に取り出すことができるものを比較することになります。
ACDBCB なら 先頭 A と最後尾 D を比較するので A を取り、CDBCB が残ります。今度は 先頭 C と最後尾 B の比較なので B を取ります。残るのは CDBC です。今度は先頭と最後尾が両方とも C です。この場合、先頭の C を取ると DBC となり、次は D と C の選択となります。しかし CDBC から最後尾の C を取ると CDB となり次は C と B の選択となり、こちらのほうが辞書順で小さい文字列をつくることができることになります。C の次が D である先頭よりも C の次が B である最後尾から選択したほうがよいということになります。
では先頭と最後尾の文字が同じとき、どのようにして次の文字（これも同じ場合はさらに次の文字）を選択すればよいのでしょうか？
残された文字列を反転させた文字列をつくります。これと残された文字列を比較して、残された文字列のほうが辞書順で小さいときは先頭から、反転させた文字列のほうが辞書順で小さいときは最後尾から文字を取り出します。取り出した順に並べて得られる文字列は ABCBCD となります。
以下のコードだと計算量は O（n^2）になります。文字列の長さが最大で 2000 なので充分間に合います。
|
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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { List<char> chars = Console.ReadLine().ToList(); List<char> rets = new List<char>(); // chars の先頭か末尾から 1 文字取り除き、これを rets の末尾に追加する while (chars.Count > 0) { char first = chars.First(); char last = chars.Last(); if (first < last) { chars.RemoveAt(0); rets.Add(first); } if (first > last) { chars.RemoveAt(chars.Count - 1); rets.Add(last); } if (first == last) { // 先頭と末尾の文字が同じ場合は 残された文字列とそれを反転した文字を比較する List<char> temp = new List<char>(chars); // 反転した文字列を生成する temp.Reverse(); bool fromHead = true; for (int i = 0; i < chars.Count; i++) { if (chars[i] < temp[i]) { break; } if (chars[i] > temp[i]) { fromHead = false; break; } } if (fromHead) { chars.RemoveAt(0); rets.Add(first); } else { chars.RemoveAt(chars.Count - 1); rets.Add(last); } } } Console.WriteLine(new string(rets.ToArray())); } } |
C – Dubious Document 2
宝物が入ってそうな箱を見つけました。しかし鍵がかかっており、鍵を開けるためには英小文字からなる文字列 S が必要です。
また文字列 S ′を見つけ、これは文字列 S の 0 個以上 （S の長さ）個以内の文字が ? に置き換わった文字列であることも分かりました。条件1：文字列 S の中に連続する部分文字列として英小文字から成る文字列 T が含まれている。
条件2：S は、条件1を満たす文字列の中で辞書順最小の文字列である。そのとき、鍵となる文字列 S を出力しなさい。
ただし、そのような文字列 S が存在しない場合は代わりに UNRESTORABLE と出力しなさい。入力されるデータ
S ′
T
（ただし S ′は英小文字と ? から成る文字列、T は英小文字から成る文字列。
ともに文字列の長さは 1 以上 50 以下）
この問題の解き方
まず後ろの方から T に一致させられる部分文字列を探す。ただし ？ は比較対象外とする。
見つからなければ UNRESTORABLE。
見つかったら残りの ? はすべて 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 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { string S = Console.ReadLine(); // 文字列 S ′ string T = Console.ReadLine(); // 後ろの方から T に一致させられる部分文字列を探す for (int start = S.Length - T.Length; start >= 0; start--) { bool ok = true; for (int i = 0; i < T.Length; i++) { char s = S[start + i]; char t = T[i]; if(s == '?') continue; // '?' は比較対象外 if (s != t) { ok = false; break; } } if (ok) { // 条件をみたす部分文字列が見つかったらその部分を T に置き換える // それ以外の部分にある '?' はすべて 'a' に置き換える char[] vs = S.ToArray(); for (int i = 0; i < T.Length; i++) vs[start + i] = T[i]; S = new string(vs); S = S.Replace("?", "a"); break; } } // 処理が終わったとき鍵が見つかっていれば '?' が存在しない文字列を取得できているはず if(S.IndexOf("?") == -1) Console.WriteLine(S); else Console.WriteLine("UNRESTORABLE"); } } |
