AtCoder の問題は AtCoder Library(ACL) を前提としているものも多くあります。C#にこのようなものはないのでしょうか？
C#なら以下がおすすめです。
ac-library-csharp
SourceExpander
ac-library-csharp は ACL の C#移植、SourceExpander は提出用のソースコードを作成するライブラリです。プロジェクトを右クリックして「NuGetパッケージの管理」でNuGet管理画面を開き、これらをインストールします。
AtCoder Library Practice Contest の問題 を ac-library-csharp を使って解いてみます。
Contents
Union-Find木
Union-Find木は以下の処理が高速にできるデータ構造です。
要素xと要素yが同じグループに属するかどうかを判定する
要素xの属するグループと要素yの属するグループの併合する
問題では頂点同士を連結させる、指定された2つの頂点が連結であるか判定するという処理が必要なので、ここはUnion-Find木を使っていきましょう。
|
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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } AtCoder.Dsu dsu = new AtCoder.Dsu(N); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; int u = vs[1]; int v = vs[2]; if (t == 0) dsu.Merge(u, v); if (t == 1) Console.WriteLine(dsu.Same(u, v) ? 1 : 0); } } } |
SourceExpander.Expander.Expand();の一行をいれてビルドするとCombined.csxという名前のファイルが生成されるので、そこに出力されているコードを提出します。
フェニック木
フェニック木 または Binary Indexed Tree (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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); AtCoder.FenwickTree<long> fenwickTree = new AtCoder.FenwickTree<long>(N); for (int i = 0; i < N; i++) fenwickTree.Add(i, A[i]); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; if (t == 0) { int p = vs[1]; int x = vs[2]; fenwickTree.Add(p, x); } if (t == 1) { int l = vs[1]; int r = vs[2]; Console.WriteLine(fenwickTree.Sum(l, r)); } } } } |
Floor Sum
N, M, A, B が与えられたときに floor((A×i+B)/M) を高速で計算するアルゴリズムがあります。
floor sum アルゴリズムとその一般化 – Qiita
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int N = vs[0]; int M = vs[1]; int A = vs[2]; int B = vs[3]; Console.WriteLine(AtCoder.MathLib.FloorSum(N, M, A, B)); } } } |
最大流問題
この問題は N 行 M 列のマス目を市松模様に塗り、隣り合う色が異なるマスに1×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 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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, M; { int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } char[,] grid = new char[N, M]; for (int r = 0; r < N; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < M; c++) grid[r, c] = vs[c]; } AtCoder.MfGraph<int> g = new MfGraph<int>(N * M + 2); for (int row = 0; row < N; row++) { for (int col = 0; col < M; col++) { if (grid[row, col] == '#') continue; if ((row + col) % 2 == 0) { int idx = row * M + col; // row 行 col 列 を 0～N * M に変換する if (row - 1 >= 0 && grid[row - 1, col] != '#') // 上 { int u = (row - 1) * M + col; g.AddEdge(idx, u, 1); } if (row + 1 < N && grid[row + 1, col] != '#') // 下 { int d = (row + 1) * M + col; g.AddEdge(idx, d, 1); } if (col - 1 >= 0 && grid[row, col - 1] != '#') // 左 { int l = row * M + col - 1; g.AddEdge(idx, l, 1); } if (col + 1 < M && grid[row, col + 1] != '#') // 右 { int r = row * M + col + 1; g.AddEdge(idx, r, 1); } } } } int s = N * M; int t = N * M + 1; for (int row = 0; row < N; row++) { for (int col = 0; col < M; col++) { int idx = row * M + col; if ((row + col) % 2 == 0) g.AddEdge(s, idx, 1); else g.AddEdge(idx, t, 1); } } Console.WriteLine(g.Flow(s, t)); var edges = g.Edges(); foreach (var edge in edges) { if (edge.From == s || edge.To == t || edge.Flow == 0) continue; if (edge.From == edge.To + 1) // 左 { grid[edge.From / M, edge.From % M] = '<'; grid[edge.To / M, edge.To % M] = '>'; } if (edge.From == edge.To - 1) // 右 { grid[edge.From / M, edge.From % M] = '>'; grid[edge.To / M, edge.To % M] = '<'; } if (edge.From == edge.To + M) // 上 { grid[edge.From / M, edge.From % M] = '^'; grid[edge.To / M, edge.To % M] = 'v'; } if (edge.From == edge.To - M) // 下 { grid[edge.From / M, edge.From % M] = 'v'; grid[edge.To / M, edge.To % M] = '^'; } } for (int row = 0; row < N; row++) { char[] vs = new char[M]; for (int col = 0; col < M; col++) vs[col] = grid[row, col]; Console.WriteLine(new string(vs)); } } } |
最小費用流問題
行番号を左側ノード、列番号を右側ノードとした二部グラフを考えます。左側ノードの頂点の番号は 0 ～ N – 1、右側ノードの頂点の番号は N ～ 2 * N – 1となります。そしてマス(i, j)に書かれている値をA[i, j]とするのであれば頂点 i と頂点 N + j の間に辺を貼り、容量を 1 とします。そして s から左側ノードへ容量 K の辺を張り、右側ノードから t へも同様に容量 K の辺を張ります。
これで最小費用流問題を考えることで、各行各列で選ぶマスの個数を K 個にしたときのマスに書かれている値の総和の最小値を得ることができます。
しかし問題文で問われていることは「選んだマスに書かれている数の総和を最大値」です。そこでコストの符号を反転させます。ただし最小費用流問題を解くアルゴリズムでは辺のコストは負数であってはならないので全体に大きな値（A[i, j]の値の上限から10^9とする）を加算してコストを正の値にします。
また各行各列で選ぶマスの個数を K 個ちょうどにするのではなく、行と列によってはこれよりも少なく選んだほうが総和を最大化することができる場合があります。問題のページの入力例 2では K = 2ですが3行目と3列目はひとつだけしか選んでいません。これに対応させるために s と t の間に容量 N * K、コスト 10^9 の辺を張ります。総和を最大化するうえでマスを選択しないほうがよい場合のフローはここに流れるようになります。
これで最小費用流問題を解けば解を得ることができます。辺のコストの符号を反転させて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 44 45 46 47 48 49 50 51 52 53 54 55 56 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, K; { int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; K = vs[1]; } long b = (long)Math.Pow(10, 9); AtCoder.McfGraph<int, long> g = new AtCoder.McfGraph<int, long>(N + N + 2); for (int r = 0; r < N; r++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int c = 0; c < N; c++) g.AddEdge(r, c + N, 1, b - vs[c]); } int s = N + N; int t = N + N + 1; for (int i = 0; i < N; i++) { g.AddEdge(s, i, K, 0); g.AddEdge(i + N, t, K, 0); } g.AddEdge(s, t, N * K, b); var ret = g.Flow(s, t, N * K); Console.WriteLine($"{-(ret.cost - ret.cap * b)}"); var edges = g.Edges(); char[,] grid = new char[N, N]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) grid[r, c] = '.'; } foreach (var edge in edges) { if (edge.From == s || edge.To == t || edge.Flow == 0) continue; grid[edge.From, edge.To - N] = 'X'; // フローが流れている辺から選ぶべきマスがわかる } for (int r = 0; r < N; r++) { char[] vs = new char[N]; for (int c = 0; c < N; c++) vs[c] = grid[r, c]; Console.WriteLine(new string(vs)); } } } |
畳み込み和
∑f(n)g(m – n)を畳み込み和といいます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, M; { int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); Console.WriteLine(string.Join(" ", AtCoder.MathLib.Convolution<AtCoder.Mod998244353>(A, B))); } } |
強連結成分分解
有向グラフにおいてお互いに行き来できる頂点を同じグループに分けることを強連結成分分解といいます。
|
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() { SourceExpander.Expander.Expand(); int N, M; { int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } AtCoder.SccGraph g = new AtCoder.SccGraph(N); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0]; int b = vs[1]; g.AddEdge(a, b); } var scc = g.Scc(); // リストはトポロジカルソートされている。リスト内の頂点の順序は未定義 Console.WriteLine(scc.Length); foreach (int[] vs in scc) { List<int> list = new List<int>(); list.Add(vs.Length); list.AddRange(vs); Console.WriteLine(string.Join(" ", list)); } } } |
2-SAT
充足可能性問題（satisfiability problem）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を’真’にできるか、という問題です。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれます。
2-SAT は、全ての節でリテラルが高々2つの問題です。この問題では旗をXに置くかYに置くかなのでリテラルは2つしかありません。
では、2-SAT における充足可能性の判定はどのようにしておこなえばよいのでしょうか？ まず論理式を有向グラフに変換します。この有向グラフは含意グラフ (implication graph) と呼ばれ、論理式における A ⇒ B の関係を有向辺で表したものです。
まず、それぞれの変数と、それぞれの変数の否定に対応する 2 * N 個の頂点をつくります。もし節が (A ⇒ B) と表されているなら、A → B と 反B → 反A を追加します。
この有向グラフを強連結成分分解して同じ強連結成分内にAと反Aが存在する場合は矛盾していることが同時に発生するということなので充足可能な割当は存在しないということになります。A → 反A のパスのみが存在するときは A == true であってはならないため A == false です。また反A → A のパスのみが存在するときは A == false であってはならないため A == true です。
また「A ⇒ B」と「AではないまたはB」は同じ意味となります。
旗iを左（または）に置いたとき旗j（i < j）を置く方法はひとつに限定されるかを考えてみます。Math.Abs(L[i] – L[j]) < D なら「旗iを左に置く ⇒ 旗jを左に置いてはならない」（AddClauseメソッドに渡す引数で言えば「旗iは左ではない または 旗jは左ではない」）となります。同様に Math.Abs(L[i] – R[j]) < D なら「旗iは左ではない または 旗jは左である」、Math.Abs(R[i] – L[j]) < D なら「旗iは左である または 旗jは左ではない」、Math.Abs(R[i] – R[j]) < D なら「旗iは左である または 旗jは左である」となります。
|
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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, D; { int[] vs =Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; D = vs[1]; } int[] L = new int[N]; int[] R = new int[N]; for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); L[i] = vs[0]; R[i] = vs[1]; } AtCoder.TwoSat twoSat = new AtCoder.TwoSat(N); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if(Math.Abs(L[i] - L[j]) < D) twoSat.AddClause(i, false, j, false); if (Math.Abs(L[i] - R[j]) < D) twoSat.AddClause(i, false, j, true); if (Math.Abs(R[i] - L[j]) < D) twoSat.AddClause(i, true, j, false); if (Math.Abs(R[i] - R[j]) < D) twoSat.AddClause(i, true, j, true); } } if (twoSat.Satisfiable()) { Console.WriteLine("Yes"); bool[] rets = twoSat.Answer(); for (int i = 0; i < N; i++) Console.WriteLine(rets[i] ? L[i] : R[i]); } else Console.WriteLine("No"); } } |
Suffix配列とLCP配列を用いた部分文字列の数え上げ
文字列から部分文字列を取り出す方法は重複を認めてもよいのであれば(string.Length * (string.Length + 1) / 2)です。ここから重複を取り除いたものがこの問題の答えとなります。
“abracadabra”を例にすると、先頭から一文字ずつ削っていくと “abracadabra”, “bracadabra”, “racadabra”, ……, “ra”, “a” という11の接尾辞を持っています。この11の接尾辞を辞書順に並べ替え、その開始位置を配列にしたものが StringLib.SuffixArrayメソッドで取得できます。
また接尾辞を辞書順に並べ替えた場合、直前の接尾辞と比較したときに先頭から共通する文字数のことを最長共通接頭辞（LCP, Longest Common Prefix）と呼びます。この総和が(string.Length * (string.Length + 1) / 2)から取り除く重複の数です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Program { static void Main() { SourceExpander.Expander.Expand(); string S = Console.ReadLine(); long ans = 1L * S.Length * (S.Length + 1) / 2; int[] suffixArray = AtCoder.StringLib.SuffixArray(S); var arr = AtCoder.StringLib.LcpArray(S, suffixArray); foreach (int v in arr) ans -= v; Console.WriteLine(ans); } } |
