AtCoder NoviStepsを埋めてみる(6) 再帰全探索 2Qまでの続きです。今回も再帰全探索です。
Contents
D – String Equivalence
問題の概要
英小文字からなる 2 つの文字列 s, t の長さが同じであり、任意の i,j に対し次のいずれかが成立するとき同型 であると定義する。
s[i] = s[j] かつ t[i] = t[j]
s[i] ≠ s[j] かつ t[i] ≠ t[j]
文字列 s は以下の条件を満たすとき 標準形 であるといいます。
任意の s と同型な文字列 t に対し、s ≦ t （辞書順での比較）が成立する。
例）zyxzx の標準形は abcac
整数 N が与えられる。長さ N の標準形の文字列をすべて辞書順で出力せよ。
文字追加するとき、
文字列が空のときは ‘a’ を追加
それ以外のとき、’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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<int> list = new List<int>(); Dfs(0); void Dfs(int depth) { int last = list.Count == 0 ? 0 : list.Max() + 1; for (int i = 0; i <= last; i++) { list.Add(i); if (list.Count < N) Dfs(depth + 1); else Console.WriteLine(new string(list.Select(_ => (char)((int)'a' + _)).ToArray())); list.RemoveAt(list.Count - 1); } } } } |
072 – Loop Railway Plan（★4）
問題の概要
H 行 W 列のグリッドがある、各マスは’,’のマスと’#’のマスのどちらかである。
ある’,’のマスを始点とし、始点と終点以外同じマスを通らず、上下左右で隣接する’,’のマスにのみ移動することを繰り返して始点に戻ってくる経路のなかで長さが最大の経路長を求めよ。
|
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() { string[] vs = Console.ReadLine().Split(); int H = int.Parse(vs[0]); int W = int.Parse(vs[1]); 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 = -1; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.') Dfs(r, c, r, c); } } Console.WriteLine(ans); void Dfs(int r, int c, int sr, int sc) { int key = r * W + c; if (seen.Contains(key)) return; seen.Add(key); int dr = Math.Abs(r - sr); int dc = Math.Abs(c - sc); if (((dr == 0 && dc == 1) || (dr == 1 && dc == 0)) && seen.Count > 2) ans = Math.Max(ans, seen.Count); if (r + 1 < H && grid[r + 1][c] == '.') Dfs(r + 1, c, sr, sc); if (r - 1 >= 0 && grid[r - 1][c] == '.') Dfs(r - 1, c, sr, sc); if (c + 1 < W && grid[r][c + 1] == '.') Dfs(r, c + 1, sr, sc); if (c - 1 >= 0 && grid[r][c - 1] == '.') Dfs(r, c - 1, sr, sc); seen.Remove(key); } } } |
D – Dance
問題の概要
2N 人の人で N 組のペアをつくる。
i と j がペアになったときの「相性」は A[i, j] である。
相性のビットごとの排他的論理和を最大化したい。最大値を求めよ。
N の最大値は 8 なので全体で16人いることになります。長さ 16 の順列を全探索することは実行時間制限以内にはできないので他の方法を考えます。
N 個のペアにわけるとして各人が問題になるのはどのペアに属するかではなく、自分とペアになるのはどの人なのかということです。
ペアの最初の人はまだ相手が決まっていない人であれば誰を選んでもよいです。なのでまだ相手が決まっていない番号が一番小さい人を選びます。その人の相手は残りのなかから全探索します。この方法なら 8 ペアであればすべての組み合わせを全探索することができます。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[,] mat = new int[N * 2, N * 2]; for (int r = 0; r < N * 2 - 1; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (global::System.Int32 i = 0; i < vs.Length; i++) { int c = r + 1 + i; mat[r, c] = vs[i]; mat[c, r] = vs[i]; } } int[] arr = new int[N * 2]; List<int> list = new List<int>(); // ペアが決まった人（indexが 2 * i と 2 * i + 1 がペアになる） bool[] use = new bool[N * 2]; // すでに選ばれたかどうか？ int ans = 0; Dfs(); Console.WriteLine(ans); void Dfs() { // 選ばれていない人たちを調べる List<int> no_use = new List<int>(); for (int i = 0; i < N * 2; i++) { if (!use[i]) no_use.Add(i); } // 一人目は一番番号が小さい人 int min = no_use.Min(); list.Add(min); use[min] = true; // 二人目はまだ選ばれていないそれ以外の人 no_use = no_use.Skip(1).ToList(); foreach (int v in no_use) { list.Add(v); use[v] = true; if (list.Count < 2 * N) Dfs(); else { int xor = 0; for (int i = 0; i < N * 2; i += 2) xor ^= mat[list[i], list[i + 1]]; ans = Math.Max(ans, xor); } use[v] = false; list.RemoveAt(list.Count - 1); } use[min] = false; list.RemoveAt(list.Count - 1); } } } |
D – Peaceful Teams
問題の概要
N 人の選手がいて、そのなかで A[i] 番目の選手と B[i] 番目の選手は相性が悪い。
この選手たちを T 個のチームに分ける。
どの選手もちょうど一つのチームに属さなければならず、どのチームにも少なくとも一人の選手が属さなければならない。
また同じチームに相性が悪い選手同士がいてはならない。
この条件を満たすチーム分けの方法は何通りあるか求めよ。
各選手がどのチームに属するかを決めます。このときにD – String Equivalence にある標準形をつくったときのような処理をおこないます。標準形のなかで要素の種類が T 個ある場合、選手たちのチーム分けができたことになります。
あとは相性が悪い選手が同一チームでないチーム分けになっているものだけを数えます。
|
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 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int T = int.Parse(vs[1]); int M = int.Parse(vs[2]); List<(int, int)> ng_pairs = new List<(int, int)>(); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); ng_pairs.Add((a - 1, b - 1)); } List<int> list = new List<int>(); int ans = 0; Dfs(0); Console.WriteLine(ans); void Dfs(int depth) { int last = list.Count == 0 ? 0 : list.Max() + 1; for (int i = 0; i <= last; i++) { list.Add(i); if (list.Count < N) Dfs(depth + 1); else if (list.Max() == T - 1) // チーム分け完了 { // 選手たちの相性が悪くないかチェック bool ok = true; foreach (var pair in ng_pairs) { if (list[pair.Item1] == list[pair.Item2]) { ok = false; break; } } if (ok) ans++; } list.RemoveAt(list.Count - 1); } } } } |
D – Domino Covering XOR
H 行 W 列のマス目があり、マス (i, j) には非負整数 A[i, j] が書かれている。
このマス目にドミノを 0 個以上置く。
1 つのドミノは隣り合う 2 つのマスを覆うように置くことができるが、同じマスに対して複数のドミノを置くことはできない。
ドミノが置かれていないマスに書かれた整数すべてのビットごとの排他的論理和を置き方のスコアと定義する。
ドミノの置き方のスコアとしてありうる最大値を求めよ。
ドミノは縦に置くか横に置くかのどちらかです。そこですべての(i, j)において、ドミノを (i, j), (i, j + 1) と置くか、(i, j), (i + 1, j) と置くか、置かないかを決めます。処理を高速にするためにはドミノを置く置かないを bit で管理するようにし、次のマスに移動するときは再帰呼び出しでドミノの状態を渡していきます。
|
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 |
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(); long ans = 0; long[][] A = new long[H][]; for (int r = 0; r < H; r++) A[r] = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); // 横（(r, c), (r, c + 1)）に置けるか？ // 置けるなら置いたときの bit を返す。置けない場合は第三引数をそのまま返す int PutH(int r, int c, int bit) { int idx = r * W + c; int next_idx = idx + 1; if (c < W - 1 && ((bit >> idx) & 1) == 0 && ((bit >> next_idx) & 1) == 0) return bit | (1 << idx) | (1 << next_idx); else return bit; } // 縦（(r, c), (r + 1, c)）に置けるか？ int PutV(int r, int c, int bit) { int idx = r * W + c; int next_idx = idx + W; if (r < H - 1 && ((bit >> idx) & 1) == 0 && ((bit >> next_idx) & 1) == 0) return bit | (1 << idx) | (1 << next_idx); else return bit; } void Dfs(int r, int c, int bit) { int bit_h = PutH(r, c, bit); int bit_v = PutV(r, c, bit); if (c < W - 1) { Dfs(r, c + 1, bit); // 置かない（そのあと現在位置を右へ移動） if(bit != bit_h) Dfs(r, c + 1, bit_h); // 横に置く（同） if(bit != bit_v) Dfs(r, c + 1, bit_v); // 縦に置く（同） } else if (r < H - 1) { // 現在位置が一番右の列なので置く置かないを決めたら現在位置を次の行へ移動 Dfs(r + 1, 0, bit); if (bit != bit_h) Dfs(r + 1, 0, bit_h); if (bit != bit_v) Dfs(r + 1, 0, bit_v); } else // 最後まできたのでスコアを計算する ans = Math.Max(ans, CalcScore(bit)); } long CalcScore(int bit) { long score = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { int idx = r * W + c; if (((bit >> idx) & 1) == 0) score ^= A[r][c]; } } return score; } Dfs(0, 0, 0); Console.WriteLine(ans); } } |
D – Hanjo
問題の概要
H 行 W 列のグリッドと A 個の 1 × 2 の大きさのタイル、B 個の 1 × 1 の大きさのタイルがある。
グリッド上にタイルが重なったり隙間ができないように敷き詰めた場合、置き方は何通りあるだろうか？
D – Domino Covering XOR と同じような方法で解けますが、置き方を数え上げるときにダブルカウントしないように注意する必要があります。
|
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
class Program { static void Main() { (int, int) ReadInt2() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1])); } string[] vs = Console.ReadLine().Split(); int H = int.Parse(vs[0]); int W = int.Parse(vs[1]); int A = int.Parse(vs[2]); int B = int.Parse(vs[3]); int ans = 0; // 横（(r, c), (r, c + 1)）に置けるか？ // 置けるなら置いたときの bit を返す。置けない場合は第五引数をそのまま返す // 第三引数、第四引数は使われていない 1 × 2, 1 × 1 のタイルの数 int PutH(int r, int c, int a, int b, int bit) { int idx = r * W + c; int next_idx = idx + 1; if (a > 0 && c < W - 1 && ((bit >> idx) & 1) == 0 && ((bit >> next_idx) & 1) == 0) return bit | (1 << idx) | (1 << next_idx); else return bit; } // 縦（(r, c), (r + 1, c)）に置けるか？ int PutV(int r, int c, int a, int b, int bit) { int idx = r * W + c; int next_idx = idx + W; if (a > 0 && r < H - 1 && ((bit >> idx) & 1) == 0 && ((bit >> next_idx) & 1) == 0) return bit | (1 << idx) | (1 << next_idx); else return bit; } // 1 × 1 のタイルを置けるか？ int PutHalf(int r, int c, int a, int b, int bit) { int idx = r * W + c; if (b > 0 && ((bit >> idx) & 1) == 0) return bit | (1 << idx); else return bit; } void Dfs(int r, int c, int a, int b, int bit) { int bit_h = PutH(r, c, a, b, bit); int bit_v = PutV(r, c, a, b, bit); int bit_half = PutHalf(r, c, a, b, bit); // タイルが置けたので全部埋まったか確認 if (bit != bit_h && Check(bit_h)) ans++; if (bit != bit_v && Check(bit_v)) ans++; if (bit != bit_half && Check(bit_half)) ans++; // ここからは前問とほぼ同じ if (c < W - 1) { Dfs(r, c + 1, a, b, bit); if (bit != bit_h) Dfs(r, c + 1, a - 1, b, bit_h); if (bit != bit_v) Dfs(r, c + 1, a - 1, b, bit_v); if (bit != bit_half) Dfs(r, c + 1, a, b - 1, bit_half); } else if (r < H - 1) { Dfs(r + 1, 0, a, b, bit); if (bit != bit_h) Dfs(r + 1, 0, a - 1, b, bit_h); if (bit != bit_v) Dfs(r + 1, 0, a - 1, b, bit_v); if (bit != bit_half) Dfs(r + 1, 0, a, b - 1, bit_half); } } // 隙間なく並べられているかチェックする bool Check(int bit) { for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { int idx = r * W + c; if (((bit >> idx) & 1) == 0) return false; } } return true; } Dfs(0, 0, A, B, 0); Console.WriteLine(ans); } } |
