AtCoder NoviStepsを埋めてみる(5) 順列全探索の続きです。今回は再帰全探索です。
Contents
C – Concat (X-th)
問題の概要
N 個の文字列 S[i] が与えられる。
文字列 f(A[0], …, A[K – 1]) を A[0] + … + A[K – 1] と定める。
N ^ K 個の数列すべてについての f(A[0], …, A[K – 1]) を辞書順に並べたとき、小さい方から X 番目の文字列を求めよ。
f(A[0], …, A[K – 1]) を全パターン求めて辞書順にソートして X 番目がなにかを調べればよいです。
以下のコードでは再帰呼び出しをして重複順列を生成し、f を求めています。
|
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 |
class Program { static void Main() { (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } (int N, int K, int X) = ReadInt3(); List<string> S = new List<string>(); for (int i = 0; i < N; i++) S.Add(Console.ReadLine()); int[] arr = new int[K]; List<string> T = new List<string>(); Dfs(0); T = T.OrderBy(_ => _).ToList(); Console.WriteLine(T[X - 1]); void Dfs(int depth) { for (int i = 0; i < N; i++) { arr[depth] = i; if (depth < K - 1) Dfs(depth + 1); else Check(); } } void Check() { string t = ""; foreach (int idx in arr) t += S[idx]; T.Add(t); } } } |
D – Goin’ to the Zoo
問題の概要
動物園が N 園あり、動物園 i の入園料は C[i] 円である。そこには合わせて M 種類の動物がいる。
動物 i は K[i] 個の動物園 A[i, 0], …,A[i, K[i] – 1] で見ることができる。
すべての動物を 2 度以上ずつ見るために必要な入園料の合計の最小値を求めよ。
すべての動物を 2 回見るのであれば 3 回以上同じ動物園に行くのは意味がありません。どの動物園の訪問回数も 0 ～ 2 回になります。
そこで各要素が 0 ～ 2 である重複順列を生成して全探索をします。すべての動物を 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 55 56 57 58 59 60 61 62 |
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[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // 動物園 i に行くと見ることができる動物のリスト List<int>[] B = new List<int>[N]; for (int i = 0; i < N; i++) B[i] = new List<int>(); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int j = 1; j < vs.Length; j++) B[vs[j] - 1].Add(i); } int[] arr = new int[N]; long ans = long.MaxValue; Dfs(0); Console.WriteLine(ans); void Dfs(int depth) { for (int i = 0; i <= 2; i++) { arr[depth] = i; if (depth < N - 1) Dfs(depth + 1); else Check(); } } void Check() { // すべての動物を 2 回以上見ることができるかチェック int[] counts = new int[M]; long cost = 0; for (int i = 0; i < N; i++) { int cnt = arr[i]; // 動物園 i に何回行くか？ cost += 1L * C[i] * cnt; foreach (var item in B[i]) counts[item] += cnt; } if (counts.All(_ => _ >= 2)) ans = Math.Min(ans, cost); } } } |
D – Keep Distance
問題の概要
整数 N と M が与えられる。
以下の条件をすべて満たす長さ N の整数列 を辞書順にすべて出力せよ。
1 ≦ A[i] ≦ M
A[i – 1] + 10 ≦ A[i]
A[i – 1] + 10 ≦ A[i] という条件を満たすものを全列挙しようとすると無駄な数列も列挙してしまうため、実行時間制限に間に合わせることは難しいです。
A[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 |
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[] arr = new int[N]; List<string> ans = new List<string>(); Dfs(0); Console.WriteLine(ans.Count); foreach (var str in ans) Console.WriteLine(str); void Dfs(int depth) { for (int i = (depth == 0 ? 1 : arr[depth - 1] + 10); i <= M - 10 * (N - depth - 1); i++) { arr[depth] = i; if (depth < N - 1) Dfs(depth + 1); else ans.Add(string.Join(" ", arr)); } } } } |
C – 321-like Searcher
問題の概要
各桁を上から見ると狭義単調減少になっている正整数を 321-like Number と定義する。
K 番目に小さい 321-like Number を求めよ。
ただし 1桁の正整数はすべて 321-like Number である。
各桁が狭義単調減少になっている正整数で最大のものは 9876543210 です。10桁しかないので深さ優先探索をすれば求めることができます。
|
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 |
class Program { static void Main() { int K = int.Parse(Console.ReadLine()); List<int> list = new List<int>(); List<long> values = new List<long>(); Dfs(0); values = values.OrderBy(_ => _).ToList(); Console.WriteLine(values[K - 1]); void Dfs(int depth) { int first = list.Count == 0 ? 1 : 0; int last = list.Count == 0 ? 9 : list.Last() - 1; for (int i = first; i <= last; i++) { list.Add(i); long v = long.Parse(string.Join("", list)); values.Add(v); Dfs(depth + 1); list.RemoveAt(list.Count - 1); } } } } |
C – Many Requirements
問題の概要
正整数 N , M , Q と Q 組の 整数の組 (a[i], b[i], c[i], d[i]) が与えられる。
以下の条件を満たす数列 A を考える。
A は、長さ N の正整数列である。
広義単調増加であり、1 ≦ A[i] ≦ M。
この数列の得点を、以下のように定める。
A[b[i]] – A[a[i]] = c[i] を満たすような i についての d[i] の総和。
A の得点の最大値を求めよ。
再帰全探索で 1 ≦ A[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 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 |
class Program { static void Main() { (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } (int, int, int, int) ReadInt4() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2]), int.Parse(vs[3])); } (int N, int M, int Q) = ReadInt3(); int[] A = new int[Q]; int[] B = new int[Q]; int[] C = new int[Q]; int[] D = new int[Q]; for (int i = 0; i < Q; i++) { (int a, int b, int c, int d) = ReadInt4(); a--; b--; A[i] = a; B[i] = b; C[i] = c; D[i] = d; } int[] arr = new int[N]; long ans = 0; Dfs(0); Console.WriteLine(ans); void Dfs(int depth) { for (int i = depth == 0 ? 1 : arr[depth - 1]; i <= M; i++) { arr[depth] = i; if (depth < N - 1) Dfs(depth + 1); else Check(); } } void Check() { long score = 0; for (int i = 0; i < Q; i++) { if (arr[B[i]] - arr[A[i]] == C[i]) score += D[i]; } ans = Math.Max(ans, score); } } } |
D – Lunlun Number
問題の概要
ルンルン数を以下のように定義する。
最上位の桁が 0 ではない正整数 である。
隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下 である。
小さい方から K 番目のルンルン数を求めよ。
K の最大値は 10^5 であるが、ルンルン数は何桁まで調べればよいのでしょうか？
「入出力例 4」をみると入力 100000 に対し、出力は 3234566667 となっています。つまり 10 桁まで調べればよいことがわかります。10桁で隣り合う 2 つの桁の差の絶対値が 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 |
class Program { static void Main() { int K = int.Parse(Console.ReadLine()); List<int> list = new List<int>(); HashSet<long> set = new HashSet<long>(); Dfs(0); var ans = set.OrderBy(_ => _).ToArray(); Console.WriteLine(ans[K - 1]); void Dfs(int depth) { int start = depth == 0 ? 1 : Math.Max(0, list.Last() - 1); int end = depth == 0 ? 9 : Math.Min(9, list.Last() + 1); for (int i = start; i <= end; i++) { list.Add(i); string s = string.Join("", list.ToArray()); long v = long.Parse(s); set.Add(v); if (depth < 10 - 1) Dfs(depth + 1); list.RemoveAt(list.Count - 1); } } } } |
C – Make Takahashi Happy
問題の概要
H 行 W 列のマス目がある。
上から i 行目、左から j 列目のマスには、整数 A[i, j] が書かれている。
現在位置から右または下に隣接するマスに移動することを繰り返して、(0, 0) から (H – 1, W – 1) まで移動する。
そのとき通ったマス（始点と終点を含む）に書かれた整数がすべて異なる移動経路は何通りあるか求めよ。
再帰全探索で右または下に隣接するマスに移動する経路を全探索します。途中でかつて通ったマスと同じ値が書かれているマスがあったらそれ以降は調べるだけ無駄なので探索を打ち切ります。 (H – 1, W – 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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } (int H, int W) = ReadInt2(); int[][] grid = new int[H][]; for (int i = 0; i < H; i++) grid[i] = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); HashSet<int> set = new HashSet<int>(); int ans = 0; Dfs(0, 0); Console.WriteLine(ans); void Dfs(int r, int c) { if (set.Contains(grid[r][c])) return; set.Add(grid[r][c]); if (r + 1 < H) Dfs(r + 1, c); if (c + 1 < W) Dfs(r, c + 1); if (r == H - 1 && c == W - 1) ans++; set.Remove(grid[r][c]); } } } |
D – Count Simple Paths
問題の概要
H 行 W 列のマス目がある。
ある空きマスを出発し、上下左右に隣接するマスへの移動を K 回行う方法であって、障害物のあるマスを通らず、同じマスを 2 回以上通らないようなものの個数を数えよ。
再帰全探索をするのですが、Dfsメソッドの引数としてこれまでに何回移動したかを表す引数を渡すことにします。また再帰処理を繰り返しているときに一度訪問したマスを再度訪問しないように seen に訪問したマスの番号を格納しています。
|
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() { (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } (int H, int W, int K) = ReadInt3(); char[][] grid = new char[H][]; for (int i = 0; i < H; i++) grid[i] = Console.ReadLine().ToArray(); HashSet<int> seen = new HashSet<int>(); int ans = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.') Dfs(r, c, 0); } } Console.WriteLine(ans); void Dfs(int r, int c, int move) { seen.Add(r * W + c); (int, int)[] diff = [(0, 1), (0, -1), (1, 0), (-1, 0)]; for (int i = 0; i < 4; i++) { int nr = r + diff[i].Item1; int nc = c + diff[i].Item2; if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc] == '.' && !seen.Contains(nr * W + nc)) { if (move + 1 < K) Dfs(nr, nc, move + 1); else ans++; } } seen.Remove(r * W + c); } } } |
D – Paid Walk
問題の概要
N 頂点 M 辺の有向グラフがある。i 番目の辺は頂点 U[i] から頂点 V[i] へ向かう辺で、コストは C[i] である。
このグラフには自己ループや多重辺があるかもしれない。また各頂点の出次数は 4 以下である。
次の条件をみたす頂点 v をすべて求めよ。
頂点 1 から頂点 v への経路であって、次の条件をともにみたすものが存在する。
ちょうど L 回辺を通る。同じ辺を複数回通る場合は、通るたびにカウントする。
通った辺のコストの総和が S 以上 T 以下である。
再帰全探索をするのですが、Dfsメソッドの引数としてこれまでに何回移動したか、通った辺のコストの総和を表す引数を渡すことにします。
|
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 |
class Program { static void Main() { (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = vs[0]; int M = vs[1]; int L = vs[2]; long S = vs[3]; long T = vs[4]; List<(int, int)>[] G = new List<(int, int)>[N]; for (int i = 0; i < N; i++) G[i] = new List<(int, int)>(); for (int i = 0; i < M; i++) { (int u, int v, int w) = ReadInt3(); u--; v--; G[u].Add((v, w)); } List<int> ans = new List<int>(); Dfs(0, 0, 0); ans = ans.Distinct().OrderBy(_ => _).ToList(); Console.WriteLine(string.Join(" ", ans)); void Dfs(int cur, int move, long sum) { foreach (var edge in G[cur]) { int next = edge.Item1; if (move + 1 < L) Dfs(next, move + 1, sum + edge.Item2); else if (S <= sum + edge.Item2 && sum + edge.Item2 <= T) ans.Add(next + 1); } } } } |
E – Count Simple Paths
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
各頂点の次数は 10 以下である。
頂点 1 を始点とする単純パス(同じ頂点を複数回通らないパス)の個数を K としたとき、min(K, 10^6) を求めよ。
パスを再帰全探索するのですが、途中でパスの個数が 10^6 を超えたら処理をうちきり 10^6 を出力します。
|
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 |
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(); List<int>[] G = new List<int>[N]; for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; G[u].Add(v); G[v].Add(u); } int ans = 0; int ans_max = 1000000; HashSet<int> seen = new HashSet<int>(); Dfs(0, 0); Console.WriteLine(Math.Min(ans, ans_max)); void Dfs(int cur, int cnt) { if (ans >= ans_max) return; seen.Add(cur); ans++; foreach (var next in G[cur]) { if (!seen.Contains(next)) Dfs(next, cnt + 1); } seen.Remove(cur); } } } |
D – 薄氷渡り
問題の概要
H 行 W 列のマス目がある。
ある空きマスを出発し、上下左右に隣接するマスへの移動を繰り返す方法であって、障害物のあるマスを通らず、同じマスを 2 回以上通らないパスのなかで最長のパスの長さを求めよ。
再帰全探索をするのですが、Dfsメソッドの引数としてこれまでに何回移動したかを表す引数を渡す、再帰処理を繰り返しているときに一度訪問したマスを再度訪問しないように seen に訪問したマスの番号を格納するのは D – Count Simple Paths と同じです。最長のパスの長さを問われているので移動に成功したら移動回数で ans を更新します。
|
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 |
class Program { static void Main() { (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } int W = int.Parse(Console.ReadLine()); int H = int.Parse(Console.ReadLine()); int[][] grid = new int[H][]; for (int i = 0; i < H; i++) grid[i] = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); HashSet<int> seen = new HashSet<int>(); int ans = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == 1) Dfs(r, c, 1); } } Console.WriteLine(ans); void Dfs(int r, int c, int move) { seen.Add(r * W + c); ans = Math.Max(ans, move); (int, int)[] diff = [(0, 1), (0, -1), (1, 0), (-1, 0)]; for (int i = 0; i < 4; i++) { int nr = r + diff[i].Item1; int nc = c + diff[i].Item2; if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc] == 1 && !seen.Contains(nr * W + nc)) Dfs(nr, nc, move + 1); } seen.Remove(r * W + c); } } } |
