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); } } |
E – Maximize XOR
問題の概要
長さ N の非負整数列 A および整数 K が与えられる。ここで二項係数 nCk は 10^6 以下であることが保証される。
A から異なる K 項を選ぶとき、選んだ K 個の数の総 XOR としてあり得る最大値を求めよ。
単純にこれまでやってきたような再帰全探索をしようとすると TLE します。以下はダメなコードです。N = 1000, K = 998 のようなテストケースがあると通りません。
|
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() { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int K = int.Parse(vs[1]); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long ans = 0; int[] arr = new int[K]; Dfs(-1, 0); Console.WriteLine(ans); void Dfs(int cur, int depth) { for (int i = cur + 1; i < N; i++) { arr[depth] = i; if (depth < K - 1) Dfs(i, depth + 1); else { long xor = 0; foreach (var idx in arr) xor ^= A[idx]; ans = Math.Max(ans, xor); } } } } } |
打開策ですが、K が N の半分よりも大きいときは K 個取る方法ではなく、N – K 個を取らない方法を考えます。これだと実行時間制限をオーバーすることなく 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 |
class Program { static void Main() { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int K = int.Parse(vs[1]); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); long XOR = 0; foreach (var v in A) XOR ^= v; long ans = 0; int[] arr = new int[K]; if(N == K) ans = XOR; else if (K < N - K) Dfs(-1, 0, true); else { K = N - K; arr = new int[K]; Dfs(-1, 0, false); } Console.WriteLine(ans); // 第三引数が false の場合は N 個から N - K 個選ばない場合を考える void Dfs(int cur, int depth, bool b) { for (int i = cur + 1; i < N; i++) { arr[depth] = i; if (depth < K - 1) Dfs(i, depth + 1, b); else { long xor = b ? 0 : XOR; foreach (var idx in arr) xor ^= A[idx]; ans = Math.Max(ans, xor); } } } } } |
D – ABC Puzzle
問題の概要
整数 N と ‘A’, ‘B’, ‘C’ からなる長さ N の文字列 R,C が与えられる。
N×N のマス目の各マスに A, B, C のうち高々 1 文字を書き込んだときに、以下の条件を全て満たすことが可能であるか判定し、可能であれば書き込み方を 1 つ出力せよ。
各行 / 各列 に A, B, C がちょうど 1 個ずつ含まれる
i 行目に書かれた文字の中で最も左にある文字は R の i 文字目と一致する
i 列目に書かれた文字の中で最も上にある文字は C の i 文字目と一致する
全パターン調べましょう。
まず順列を生成して “ABC..” の並び順をすべて生成します。N = 3 なら 6 通り、N = 4 なら 24 とおり、N = 5 なら 60 通りです。
あとは再帰全探索でこれらのなかから 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 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 109 110 111 |
class Program { static void Main() { string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); string R = Console.ReadLine(); string C = Console.ReadLine(); List<string> F() { List<string> res = new List<string>(); char[] arr = new char[N]; arr[0] = 'A'; arr[1] = 'B'; arr[2] = 'C'; for (int i = 3; i < N; i++) { arr[i] = '.'; } Array.Sort(arr); do { res.Add(new string(arr)); } while (AtCoder.StlFunction.NextPermutation(arr)); return res; } List<string> S = F(); List<string> ans = null; List<int> list = new List<int>(); HashSet<char>[] col_sets = new HashSet<char>[N]; // 各列に格納した '.' 以外の文字 for (int i = 0; i < N; i++) col_sets[i] = new HashSet<char>(); Dfs(); if (ans != null) { Console.WriteLine("Yes"); foreach (var str in ans) Console.WriteLine(str); } else Console.WriteLine("No"); void Dfs() { if (ans != null) return; for (int i = 0; i < S.Count; i++) { // 条件に反するものはここで弾いて計算量を減らす bool ok = true; for (int col = 0; col < N; col++) { if (S[i][col] == '.') continue; if (S[i][col] != R[list.Count]) // 各行の最初の文字が条件と違う ok = false; break; } for (int col = 0; col < N; col++) { if (S[i][col] == '.') continue; // 各列に同じ文字をセットしようとしている。 // または各列の最初の文字が条件と違う if (col_sets[col].Contains(S[i][col]) || (col_sets[col].Count == 0 && S[i][col] != C[col])) { ok = false; break; } } if (ok) { for (int col = 0; col < N; col++) { if(S[i][col] != '.') col_sets[col].Add(S[i][col]); } list.Add(i); if (list.Count < N) Dfs(); else { List<string> grid = new List<string>(); foreach (var idx in list) grid.Add(S[idx]); ans = grid; } list.RemoveAt(list.Count - 1); for (int col = 0; col < N; col++) col_sets[col].Remove(S[i][col]); } } } } } |
D – Stone XOR
問題の概要
N 個の袋があり、袋 i には A[i] 個の石が入っている。
「2 つの袋 A, B を選び、袋 A に入っている石を すべて 袋 B に入れる」という操作を好きなだけ（0 回でもよい）繰り返す。
このとき「すべての袋に入っている石の数の排他的論理和」としてあり得るものが何個あるか求めよ。
「2 つの袋 A, B を選び、袋 A に入っている石を すべて 袋 B に入れる」という操作は A と B を同じグループにするということを意味しています。
なのでグループ分けを全パターン試します。
D – Peaceful Teamsと似ていますが、この問題はグループの個数に縛りがない点が異なっています。
あとは XOR を計算してその種類数をカウントするだけと言いたいのですが、long 型で HashSet を使おうとするとハッシュが衝突して計算時間が伸びてしまい TLE するというケースがあります。なので 32 で割ったときの剰余で別のオブジェクトに格納するようにしています。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); List<int> list = new List<int>(); // 各袋はどのグループに属するか？ HashSet<long>[] sets = new HashSet<long>[32]; for (int i = 0; i < 32; i++) sets[i] = new HashSet<long>(); Dfs(); Console.WriteLine(sets.Sum(_ => _.Count)); void Dfs() { int last = list.Count == 0 ? 0 : list.Max() + 1; for (int i = 0; i <= last; i++) { list.Add(i); if (list.Count < N) Dfs(); else // グループ分け完了 { long[] sums = new long[N]; for (int j = 0; j < N; j++) { int g = list[j]; sums[g] += A[j]; } long xor = 0; for (int j = 0; j < N; j++) xor ^= sums[j]; sets[xor & 31].Add(xor >> 5); } list.RemoveAt(list.Count - 1); } } } } |
D – RGB Coloring 2
問題の概要
N 頂点 M 辺の単純無向グラフが与えられる。
辺 i は頂点 A[i] と頂点 B[i] を結んでいる。
このグラフの各頂点を赤、緑、青の 3 色のいずれかで塗る方法であって、以下の条件を満たすものの数を求めよ。
辺で直接結ばれている 2 頂点は必ず異なる色で塗られている。
使われない色があってもよい。
N の最大値が 20 なので3^N 通りの塗り方を全探索する方法では実行時間制限に間に合わせることができません。
しかし、全探索の対象を 3^N 通りではなく 3 × 2^(N – 1) に減らすことができます。
なぜならある頂点 x の色を決めた時、x と辺で繋がっている頂点の色の探索候補は 2 通りしかありません。グラフが連結なら 3 × 2^(N – 1) だけ探索すればよいし、連結でないなら各連結成分で同様の処理をおこない、部分解の総積が解となります。
連結成分に分解して各グループのある頂点を起点に色をつけていきます。隣の頂点と同じ色で塗ろうとしている場合以外は再帰処理を繰り返してすべての頂点に色をつけることができたものを数え上げます。
着色する順番を適当に決めていると TLE する原因となります。
与えられたグラフがスターグラフ（中心から放射状に枝が伸びているグラフ）を考えることにします。中心の頂点番号が 20、それ以外の葉にあたる頂点の番号が 1 ～ 19 であった場合、葉は互いに独立なので全部 3 通り探索しなければなりません。これだと計算量が O(3^(N – 1) × 2)となり、N = 20 の場合は 3^19 = 1,162,261,467 であることを考えると TLE 必至です。
この問題は探索する頂点を DFS木順 に並べることで回避できます。このように並べ直すことで次の探索対象は必ず「すでに塗られた隣接頂点」を持つからです。これによって計算量を O(3 × 2^(N – 1)) に落とすことができます。
連結成分に分解する処理は ライブラリ ac-library-csharp の Dsu クラスを使用しています。
|
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 |
using AtCoder; 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]; Dsu dsu = new Dsu(N); for (int i = 0; i < N; i++) G[i] = new List<int>(); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; G[a].Add(b); G[b].Add(a); dsu.Merge(a, b); } int[][] groups = dsu.Groups(); int[] colors = new int[N]; // 0 なら色未定、1:Red, 2:Green, 3:Blue long ans = 1; foreach (int[] group in groups) { int[] order = Order(group); ans *= Dfs(0, order); } Console.WriteLine(ans); // 各連結成分の頂点を DFS木順 に並べかえた配列を返す int[] Order(int[] group) { bool[] seen = new bool[N]; List<int> order = new List<int>(); Dfs(group[0]); return order.ToArray(); void Dfs(int cur_v) { if (seen[cur_v]) return; seen[cur_v] = true; order.Add(cur_v); foreach (var next_v in G[cur_v]) Dfs(next_v); } } // order[idx] に可能であれば色をつける long Dfs(int idx, int[] order) { if (idx == order.Length) return 1; int cur_v = order[idx]; long res = 0; for (int color = 1; color <= 3; color++) { bool ok = true; foreach (var next_v in G[cur_v]) { if (colors[next_v] == color) { ok = false; break; } } if (ok) { colors[cur_v] = color; res += Dfs(idx + 1, order); colors[cur_v] = 0; } } return res; } } } |
E – Red Polyomino
問題の概要
N 行 N 列のグリッドが与えられる。
上から i 番目、左から j 番目のマスは、S[i][j] で表され、これが # なら黒く塗られており、. なら白く塗られている。
白く塗られたマスのうち、ちょうど K 個のマスを選んで赤く塗りたい。
赤く塗られたマスが連結である塗り方は何通りあるだろうか？
N^2 個のマスから K 個選ぶ方法は (N^2)C(K) 通りあり、N = 8, K = 8 のときは 64C8 = 4,426,165,368 となり、TLE 必至です。
しかし赤マス同士が連結という条件から、条件を満たす選び方はそれより少ないです。入出力例 3 から 最大で 64678 しかないことがわかります。
最初に赤く塗るマスを決め、あとはすでに赤く塗られているマスから上下左右に辿って到達できるものだけを塗り続けるという再帰処理をして全探索します。
|
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 |
using System.Text; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int K = int.Parse(Console.ReadLine()); char[][] grid = new char[N][]; for (int r = 0; r < N; r++) grid[r] = Console.ReadLine().ToArray(); int ans = 0; HashSet<string> set = new HashSet<string>(); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (grid[r][c] == '.') { grid[r][c] = '@'; Dfs(K - 1); grid[r][c] = '.'; } } } Console.WriteLine(ans); void Dfs(int k) // k は赤く塗らなければならない残りの数 { string s = GridToString(); // この状態はすでに見たのでなにもしない if (set.Contains(s)) return; set.Add(s); // K 個塗ることができたのでカウントする if (k == 0) { ans++; return; } List<(int, int)> nexts = GetNexts(); // 次に赤マスを塗る場所の候補 foreach (var next in nexts) { grid[next.Item1][next.Item2] = '@'; Dfs(k - 1); grid[next.Item1][next.Item2] = '.'; } } string GridToString() { StringBuilder sb = new StringBuilder(); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) sb.Append(grid[r][c]); } return sb.ToString(); } // 次に赤マスを塗る場所の候補を返す List<(int, int)> GetNexts() { int[] dr = [1, -1, 0, 0]; int[] dc = [0, 0, 1, -1]; List<(int, int)> nexts = new List<(int, int)>(); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { // (r, c) を次の赤マスにできる条件は、 // grid[r][c] が '.' であり、かつ、grid[r][c]の隣が '@' であること if (grid[r][c] == '.') { bool ok = false; for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (0 <= nr && nr < N && 0 <= nc && nc < N && grid[nr][nc] == '@') ok = true; } if (ok) nexts.Add((r, c)); } } } return nexts; } } } |
