AtCoder NoviStepsを埋めてみる(3) 貪欲法 1Q問題の続きです。今回はbit全探索です。
bit全探索とは、bit演算を使って全探索をする方法です。bit全探索を使えば、部分集合を全パターン列挙することができます。M 個のものを部分集合にいれるかどうかの組み合わせは全部で 2 の M 乗 とおりありますが、bitが立っている桁のものはいれて、そうでないものは入れないという感じにするのです。
Contents
C – Popcorn
問題の概要
N 個のポップコーン売り場があり、そこでは合計 M 種類のポップコーンが売られている。
全種類のポップコーンを買いたいができるだけ訪問する売り場の数を少なくしたい。
最低何個の売り場を訪れる必要があるだろうか？
1 以上 2 の 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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); List<string> S = new List<string>(); for (int i = 0; i < N; i++) S.Add(Console.ReadLine()); int ans = int.MaxValue; for (int bit = 1; bit < 1 << N; bit++) { List<string> selected = new List<string>(); for (int i = 0; i < N; i++) { if (((bit >> i) & 1) == 1) selected.Add(S[i]); } bool ok = true; for (int i = 0; i < M; i++) { bool find = false; foreach (string s in selected) { if (s[i] == 'o') find = true; } if (!find) ok = false; } if (ok) ans = Math.Min(ans, selected.Count); } Console.WriteLine(ans); } } |
C – Separated Lunch
問題の概要
N 個の部署が存在し、i 番目の部署に所属する人数は K[i] 人である。
それぞれの部署をグループ A, B のいずれか一方に割り当て、グループごとに同時に昼休みをとり、かつグループ A, B の昼休みの時間が重ならないようにしたとき、同時に昼休みをとる最大人数としてあり得る最小の値は？
実際に全体を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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] K = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long ans = long.MaxValue; for (int bit = 1; bit < (1 << N) - 1; bit++) { long A = 0; long B = 0; for (int i = 0; i < N; i++) { if (((bit >> i) & 1) == 1) A += K[i]; else B += K[i]; } ans = Math.Min(ans, Math.Max(A, B)); } Console.WriteLine(ans); } } |
D – 派閥
問題の概要
N 人の国会議員と、M 個の人間関係 (x, y は知り合いである) が存在する。
N 人の議員から何人かを選んで派閥を作る。
派閥に含まれるすべての議員は互いに知り合いでなければならない。
派閥に属する議員数を最大化したとき、その派閥に属する議員数は？
bit全探索でじっさいに派閥をつくってみるのですが、このときに派閥内のなかから任意の2人からできるペアのうち、1組でも「互いに知り合いである」という条件から外れるもの（コード内の pairs[x, y] が false のもの）があってはいけません。条件を満たした派閥ができたらそのなかから人数が一番多いものを選びます。
|
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 |
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(); bool[,] pairs = new bool[N, N]; for (int i = 0; i < M; i++) { (int x, int y) = ReadInt2(); x--; y--; pairs[x, y] = true; pairs[y, x] = true; } // 派閥に含まれる議員たちがすべて互いに知り合いであるか調べる bool Check(int bit) { for (int x = 0; x < N; x++) { if (((bit >> x) & 1) == 1) { for (int y = x + 1; y < N; y++) { if (((bit >> y) & 1) == 1) { if (!pairs[x, y]) return false; } } } } return true; } int ans = 0; for (int bit = 1; bit < 1 << N; bit++) { if (Check(bit)) { int popcount = 0; for (int i = 0; i < N; i++) { if (((bit >> i) & 1) == 1) popcount++; } ans = Math.Max(ans, popcount); } } Console.WriteLine(ans); } } |
C – Keys
問題の概要
N 本の鍵 と 鍵を何本でも挿し込めるドアがある。
ドアは正しい鍵を K 本以上挿し込んだ時だけ開く。
C[i] 本の鍵（どの鍵かは入力で与えられる）を差し込むテストをおこなった結果、R[i] = o のときはドアが開き、x のときは開かなかった。
テストの結果と矛盾しない鍵の選び方は何通り存在するだろうか？
bit全探索ですべての鍵の選びかたを試せばよいです。以下のような組み合わせは適切ではありません。
ドアが開いたテストと一致する鍵を K 本以上選べていない
ドアが開かなかったテストと一致する鍵を 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 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 |
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 M, int K) = ReadInt3(); List<int> OK = new List<int>(); List<int> NG = new List<int>(); for (int i = 0; i < M; i++) { string[] vs = Console.ReadLine().Split(); int c = int.Parse(vs[0]); string ret = vs[c + 1]; int[] arr = vs.Skip(1).Take(c).Select(_ => int.Parse(_) - 1).ToArray(); int bit = 0; foreach (var v in arr) bit += 1 << v; if (vs[c + 1] == "o") OK.Add(bit); else NG.Add(bit); } int PopCount(int bit) { int cnt = 0; for (int i = 0; i < N; i++) cnt += ((bit >> i) & 1) == 1 ? 1 : 0; return cnt; } bool Check(int bit) { foreach (int v in OK) { if (PopCount(bit & v) < K) return false; } foreach (int v in NG) { if (PopCount(bit & v) >= K) return false; } return true; } int ans = 0; for (int bit = 0; bit < 1 << N; bit++) { if (Check(bit)) ans++; } Console.WriteLine(ans); } } |
C – HonestOrUnkind2
問題の概要
N 人の人がいる。彼らは必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかである。
人 i の j 個目の証言は x, y で表され、y = 1 x は正直者であり、 y = 0 であれば x は不親切な人であることを示す。
N 人の中には最大で何人の正直者が存在し得るだろうか？
人 i が正直者だと言っている人と不親切だと言っている人をまとめます。そして正直者と仮定する部分集合（コード内の 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 |
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.Parse(Console.ReadLine()); int[] honest_bits = new int[N]; int[] liar_bits = new int[N]; for (int i = 0; i < N; i++) { int A = int.Parse(Console.ReadLine()); for (int a = 0; a < A; a++) { (int x, int y) = ReadInt2(); x--; if (y == 1) honest_bits[i] |= 1 << x; else liar_bits[i] |= 1 << x; } } int ans = 0; for (int bit = 1; bit < 1 << N; bit++) { int pop_count = 0; int honest_bit = 0; // 正直者と仮定した人たちが正直者だと言っている人の集合 int liar_bit = 0; // 正直者と仮定した人たちが不親切な人だと言っている人の集合 for (int i = 0; i < N; i++) { if (((bit >> i) & 1) == 1) { pop_count++; honest_bit |= honest_bits[i]; liar_bit |= liar_bits[i]; } } // 証言と仮定に矛盾はないか？ if ((bit & honest_bit) == honest_bit && (bit & liar_bit) == 0) ans = Math.Max(ans, pop_count); } Console.WriteLine(ans); } } |
C – Time Gap
問題の概要
高橋君の都市と他の N 番目の都市の時刻の差を調べてみたところ、i 番目の都市との時刻の差は D[i] 時間であった。
ただし時刻の差は min(d, 24 – d) であるものとする。
高橋君の都市と N 個の都市の合計 N + 1 個の都市のからできるすべての 2 つの都市どうしの時刻の差のなかで最小であるものを s とする。
s として考えられる最大値は？
高橋君の都市は 0 時に固定して他の都市の時刻を考えます。時刻の差が d であるならその都市の時刻は d か 24 – d のどちらかです。これをbit全探索で考えるのですが、都市は全部で50個あるので 2 の 50 乗とおり考えることはできません。
しかし 1 日 は 24 時間であり、入力される値も 0 から 12 の 13種類しかないのでその時刻の差である都市をまとめてしまえばbit全探索が可能になります。
その時刻の差である都市が 1 つしかない場合は実際の時刻は d かもしれないし 24 – d かもしれないので両方の考える必要があります。2 つある場合は s を最大化するのであれば一方が d であり、他方が 24 – d である場合を考えます。3 つ以上ある場合は d と 24 – d のうちどちらかが必ず 2 つ以上になります。この場合はどうやっても s は 0 にしかなりません。また 入力に 0 がひとつでもある場合、これも s は 0 にしかならないので解は 0 となります。
|
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 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); int[] D = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Dictionary<int, int> dic = new Dictionary<int, int>(); foreach (var v in D) { if(!dic.ContainsKey(v)) dic.Add(v, 0); dic[v]++; } // 解が 0 になる場合 if (D.Any(_ => _ == 0) || dic.Any(_ => _.Value >= 3)) { Console.WriteLine(0); return; } // 時刻の差が 1 つだけのものと 2 つあるものにわける int[] D1 = dic.Where(_ => _.Value == 1).Select(_ => _.Key).ToArray(); int[] D2 = dic.Where(_ => _.Value == 2).Select(_ => _.Key).ToArray(); int ans = 0; int cnt = D1.Length; for (int bit = 0; bit < 1 << cnt; bit++) { // 時刻の差が 1 つだけのものは bit全探索で両方考える List<int> vs = new List<int>(); for (int i = 0; i < cnt; i++) { if (((bit >> i) & 1) == 1) vs.Add(D1[i]); else vs.Add(24 - D1[i]); } // 時刻の差が 2 つあるものは常に両方考える foreach (int d2 in D2) { vs.Add(d2); vs.Add(24 - d2); } // 高橋くんの都市 vs.Add(0); vs.Add(24); // s を計算する vs = vs.OrderBy(_ => _).ToList(); int s = int.MaxValue; for (int i = 0; i < vs.Count - 1; i++) { int d = vs[i + 1] - vs[i]; s = Math.Min(s, Math.Min(d, 24 - d)); } ans = Math.Max(ans, s); } Console.WriteLine(ans); } } |
A72 – Tile Painting
問題の概要
縦 H 行、横 W 列のマス目があり、それぞれ白か黒で塗られている。
ある行またはある列を選び、すべて黒で塗り替える操作を K 回まで行うことができる。
最大で何個のマスを黒くできるだろうか？
H は最大で 10 なので選ぶ行をbit全探索で決めます。選んだ行数が K を超えてしまった場合は不適切な選び方です。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 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 |
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(); int cnt0 = 0; // 初期状態の黒マスの数 char[,] grid = new char[H, W]; for (int r = 0; r < H; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < W; c++) { grid[r, c] = vs[c]; if (vs[c] == '#') cnt0++; } } int ans = 0; for (int bit = 0; bit < 1 << H; bit++) { char[,] clone = (char[,])grid.Clone(); int k = K; int cnt = cnt0; for (int i = 0; i < H; i++) { if (((bit >> i) & 1) == 1) { k--; for (int col = 0; col < W; col++) { if (clone[i, col] == '.') { clone[i, col] = '#'; cnt++; } } } } if (k < 0) continue; // 選びすぎ 不適 // 各列にある白マスを数える List<int> vs = new List<int>(); for (int col = 0; col < W; col++) { int cnt2 = 0; for (int r = 0; r < H; r++) { if (clone[r, col] == '.') cnt2++; } vs.Add(cnt2); } // 上位 k 個の和を足す cnt += vs.OrderByDescending(_ => _).Take(k).Sum(); ans = Math.Max(ans, cnt); } Console.WriteLine(ans); } } |
D – バレンタインデー
女子が N 人、男子が M 人いて、ここから女子 P 人と男子 Q 人からなるグループを作る。
女子 x[i] は 男子 y[i] にチョコレートを渡したいと考えていて、男女がグループ内にいるときだけ渡すことができる。
実際に渡すことができた場合は幸福度 z[i] を得ることができる。
幸福度の総和の最大値は？
女子と男子はそれぞれ最大16人なので、それぞれをbit全探索しようとすると 2 の 16 乗 の 2 乗 通り調べることになり、時間以内には終わりません。
そこで女子だけ全探索することにします。それぞれの場合で各男子にわたすことで得られる幸福度を計算します。この上位 Q 個の総和を調べます。これを 2 の 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 |
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])); } string[] vs = Console.ReadLine().Split(); int N = int.Parse(vs[0]); int M = int.Parse(vs[1]); int P = int.Parse(vs[2]); int Q = int.Parse(vs[3]); int R = int.Parse(vs[4]); Dictionary<int, List<(int, int)>> dic = new Dictionary<int, List<(int, int)>>(); for (int i = 0; i < R; i++) { (int x, int y, int z) = ReadInt3(); x--; y--; if (!dic.ContainsKey(x)) dic.Add(x, new List<(int, int)>()); dic[x].Add((y, z)); } int ans = 0; for (int f_bit = 1; f_bit < 1 << N; f_bit++) { List<int> f_list = new List<int>(); for (int i = 0; i < N; i++) { if (((f_bit >> i) & 1) == 1) f_list.Add(i); } if (f_list.Count != P) continue; int[] m_score = new int[M]; foreach (var f in f_list) { if (dic.ContainsKey(f)) { foreach (var pair in dic[f]) m_score[pair.Item1] += pair.Item2; } } ans = Math.Max(ans, m_score.OrderByDescending(_ => _).Take(Q).Sum()); } Console.WriteLine(ans); } } |
G – Wildcards
問題の概要
N 個の英小文字のみからなる長さ L の文字列 S[i] が与えられる。
長さ L の英小文字と K 個の ? からなる文字列 T を考える。
? は任意の文字に置き換えることができるなら T と S[i] が一致する個数の最大値はどうなるだろうか？
bit全探索で ? の位置をすべて試します。? の個数が K 個ではないものは不適です。
それ以外の場合は ? は何でもよいので比較対象から外しても問題ないと考えます。S[i] から ? がある位置の文字を取り除いた文字列を 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 |
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 L, int K) = ReadInt3(); List<string> S = new List<string>(); for (int i = 0; i < N; i++) S.Add(Console.ReadLine()); int ans = 0; for (int bit = 0; bit < 1 << L; bit++) { // T の i 文字目が '?' ならあってもなくても同じなので // i 文字目がない S をつくって一番多くできる種類のものを考える HashSet<int> removeIndexes = new HashSet<int>(); for (int i = 0; i < L; i++) { if (((bit >> i) & 1) == 1) removeIndexes.Add(i); } if (removeIndexes.Count != K) continue; Dictionary<string, int> dic = new Dictionary<string, int>(); foreach (var s in S) { string t = ""; for (int i = 0; i < L; i++) { if (!removeIndexes.Contains(i)) t += s[i]; } if(!dic.ContainsKey(t)) dic.Add(t, 0); dic[t]++; } int max = dic.Max(_ => _.Value); ans = Math.Max(ans, max); } Console.WriteLine(ans); } } |
A – Not coprime
問題の概要
N 個の 2 以上 50 以下の整数 X[i] が与えられる。
すべての X[i] と互いに素ではない Y のなかで最小のものを求めよ。
X[i] と Y が互いに素でないことは X[i] と Y の両方に共通の素因数が存在することを意味します。
X[i] はすべて 50 以下なので 50 以下の素数を考えます。これは全部で 15 個しかありません。そこでこれらからなるすべての合成数のなかから、すべての X と互いに素ではないものを探します。このなかで最小のものが求める解です。
|
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() { SourceExpander.Expander.Expand(); (int, int, int) ReadInt3() { string[] vs = Console.ReadLine().Split(); return (int.Parse(vs[0]), int.Parse(vs[1]), int.Parse(vs[2])); } // 最大公約数 long GCD(long a, long b) => b > a ? GCD(b, a) : (b == 0 ? a : GCD(b, a % b)); // 50 以下の素数をすべて求める // もっと高速な方法もあるが上限が50なのでこれでよいということで List<int> primes = new List<int>(); for (int i = 2; i < 50; i++) { bool is_prime = true; for (int j = 2; j < i; j++) { if (i % j == 0) is_prime = false; } if (is_prime) primes.Add(i); } int N = int.Parse(Console.ReadLine()); int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long ans = long.MaxValue; int primes_count = primes.Count; for (int bit = 0; bit < 1 << primes_count; bit++) { long v = 1; for (int i = 0; i < primes_count; i++) { if (((bit >> i) & 1) == 1) v *= primes[i]; } bool ok = true; foreach (int x in X) { if (GCD(v, x) == 1) ok = false; } if(ok) ans = Math.Min(ans, v); } Console.WriteLine(ans); } } |
C – オレンジグラフ
N 頂点 M 辺の連結した単純無向グラフがある。最初、辺はすべて白である。
「白い辺をひとつ選びオレンジに塗る」という操作をできなくなるまで繰り返し行なう。
ただしオレンジの辺のみからなる奇数長の閉路ができてしまう場合、その操作はできない。
操作を終えた後、最終的な辺の色の組合せとして考えられるものは何通りあるだろうか？
グラフの辺の両端の一方に白、他方に黒を塗ります。奇数長の閉路がある場合はこのような操作ができません。なのでオレンジ色に塗られた辺だけでできたグラフは二部グラフとなります。
では辺をオレンジ色に塗る操作をできなくなるまで繰り返し行なった結果、できる二部グラフとはどのようなグラフでしょうか？ もとのグラフが連結した単純無向グラフなのでできる二部グラフも連結したグラフになります。
UnionFind木の Dsu クラスは ac-library-csharp のものを使っています。
|
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 |
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, int)> edges = new List<(int, int)>(); for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); u--; v--; edges.Add((u, v)); } HashSet<string> set = new HashSet<string>(); for (int bit = 0; bit < 1 << N; bit++) { // 各頂点を 2 色で塗り分ける。全パターン試す // 二部グラフを作ってみる // 元のグラフの辺で両端の色が異なる場合は二部グラフとして辺を繋いでよい // 最終的に生成された二部グラフが連続であればよい List<int> use = new List<int>(); // 塗った辺の番号を格納する Dsu dsu = new Dsu(N); for (int i = 0; i < M; i++) { if (((bit >> edges[i].Item1) & 1) != ((bit >> edges[i].Item2) & 1)) { use.Add(i); dsu.Merge(edges[i].Item1, edges[i].Item2); } } if (dsu.Groups().Length == 1) set.Add(string.Join(",", use)); } Console.WriteLine(set.Count); } } |
E – Moat
問題の概要
4×4 のグリッド上のいくつかのマスの上に村があります。村をすべて囲うように堀を建設します。
堀は格子点をつなげることでできている。
堀は x 軸または y 軸に平行でなければならない。
堀は自己交差していたり複数にわかれていてはならない。
堀で囲まれた領域内に別の堀が存在してはならない。
このような堀は何通りあるだろうか？
各マスを掘で囲われた領域内にいれるかどうかをbit全探索で調べます。
すべての村が領域内に入っていない場合は不適です。また領域内に入れたマスが連結していない場合も不適です。
問題は「堀で囲まれた領域内に別の堀が存在する」場合をどうやって検出するかですが、堀のなかにいれないマス同士も連結させ、17番目の頂点を定義し、堀のなかにいれないマスの行番号と列番号が 0 と 3 の場合はこれと連結させます。
すると条件を満たしているのであれば堀にいれる領域と堀にいれない領域の連結成分数はそれぞれ 1 となります。このようなものだけを数えればそれが解となります。
UnionFind木の Dsu クラスは ac-library-csharp のものを使っています。
|
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 |
using AtCoder; class Program { static void Main() { int[,] grid = new int[4, 4]; int mask = 0; for (int r = 0; r < 4; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int c = 0; c < 4; c++) { grid[r, c] = vs[c]; if (vs[c] == 1) mask |= 1 << (r * 4 + c); } } int ans = 0; for (int bit = 0; bit < 1 << 16; bit++) { if ((bit & mask) != mask) // すべての村が入っていない continue; Dsu dsu = new Dsu(16 + 1); for (int i = 0; i < 16; i++) { int r = i / 4; int c = i % 4; (int, int)[] next_pairs = [(1, 0), (-1, 0), (0, 1), (0, -1)]; if (((bit >> i) & 1) == 1) { // 堀にいれた領域は連結しているかチェックする foreach (var pair in next_pairs) { int nr = r + pair.Item1; int nc = c + pair.Item2; if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) continue; int n_idx = nr * 4 + nc; if (((bit >> n_idx) & 1) == 1) dsu.Merge(i, n_idx); } } else { // 堀にいれない領域は17番頂点と連結しているかチェックする foreach (var pair in next_pairs) { int nr = r + pair.Item1; int nc = c + pair.Item2; if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4) { dsu.Merge(i, 16); continue; } int n_idx = nr * 4 + nc; if (((bit >> n_idx) & 1) == 0) dsu.Merge(i, n_idx); } } } if (dsu.Groups().Length == 2) ans++; } Console.WriteLine(ans); } } |
