はじめに
AtCoder Beginner Contest 282の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc282
問題A
C++やC#などの言語では、char型のAに+0するとA、+1するとB、+25するとZの文字を取得することができます。
これは、文字Aは数値65をchar型にしたものに対応しており、文字Bや文字Zはそれぞれ数値66と数値90に対応します。
そのため、Aからi進んだ数値をchar型に変換することで、Aからi進んだ文字として得ることができます。
public static void Solve()
{
var K = Scanner.Scan<int>();
var builder = new StringBuilder();
for (var i = 0; i < K; i++)
{
builder.Append((char)('A' + i));
}
var answer = builder.ToString();
Console.WriteLine(answer);
}
問題B
1<=i<j<=Nとなるi番とj番のペアにおいて、M問全ての問題で少なくともどちらか一方でも解くことができるペアの数を数え上げます。
これは、各ペアを列挙し、"i番のk問目とj番のk問目の少なくともどちらか一方がoである"、という小問題を1<=k<=M全てで満たしている場合の数となります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = new string[N];
for (var i = 0; i < N; i++)
{
S[i] = Scanner.Scan<string>();
}
var answer = 0;
for (var i = 0; i < N; i++)
{
for (var j = i + 1; j < N; j++)
{
var ok = true;
for (var k = 0; k < M; k++)
{
ok &= S[i][k] == 'o' || S[j][k] == 'o';
}
if (ok) answer++;
}
}
Console.WriteLine(answer);
}
問題C
現在の文字が括られているかの判定は、それまでに出現した"の数が奇数個であれば括られており、偶数個であれば括られていないことがわかります。
文字を順番に見ていき、現在の文字が括られていないときの,であれば、.に変換します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var level = 0;
var T = new char[N];
for (var i = 0; i < N; i++)
{
var c = S[i];
if (c == '"')
{
level ^= 1;
}
else
{
if (c == ',' && level == 0)
{
c = '.';
}
}
T[i] = c;
}
var answer = new string(T);
Console.WriteLine(answer);
}
問題D
あるグラフが連結である場合、始点を白と決めて幅優先探索などを行い、連結している頂点の色を白黒反転したものを決めていくことで、そのグラフが二部グラフであるかどうかを判定することができます。
二部グラフの性質として、
- グラフが二部グラフではない場合、いずれの頂点どうしを新たに接続しても、二部グラフにすることはできません。
- グラフが二部グラフである場合、色が異なる頂点どうしを新たに接続しても、二部グラフを保つことができます。
- 二部グラフ
Aと二部グラフBがあるとき、Aのいずれの頂点とBのいずれの頂点を接続しても、接続後のグラフは二部グラフを保つことができます。
これらのことから、連結成分ごとに二部グラフかどうかを判定を行い、二部グラフではない連結成分が存在する場合、いずれの頂点どうしを新たに接続しても二部グラフにすることはできないので、答えは0になります。
対して、全ての連結成分が二部グラフである場合、次の総和が答えとなります。
- 各連結成分において
白の頂点の数*黒の頂点の数-既に接続している辺の数が新たに追加できる辺の数となります。 - 連結成分の数が
K個であるとき、1<=i<j<=Kとなる二部グラフi,jにおいて、iの頂点の数*jの頂点の数が新たに追加できる辺の数となります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
var E = new (int u, int v)[M];
for (var i = 0; i < M; i++)
{
var (u, v) = Scanner.Scan<int, int>();
u--;
v--;
G[u].Add(v);
G[v].Add(u);
E[i] = (u, v);
}
var colors = new int[N];
Array.Fill(colors, -1);
var queue = new Queue<int>();
var bipartiteSize = new List<long>();
var isBipartiteNode = new bool[N];
long answer = 0;
for (var i = 0; i < N; i++)
{
if (colors[i] != -1) continue;
var isBipartite = true;
queue.Enqueue(i);
colors[i] = 0;
long c0 = 0;
long c1 = 0;
var list = new List<int>();
while (queue.Count > 0)
{
var u = queue.Dequeue();
list.Add(u);
if (colors[u] == 0) c0++;
else c1++;
foreach (var v in G[u])
{
if (colors[u] == colors[v]) isBipartite = false;
if (colors[v] != -1) continue;
colors[v] = colors[u] ^ 1;
queue.Enqueue(v);
}
}
if (!isBipartite)
{
Console.WriteLine(0);
return;
}
bipartiteSize.Add(c0 + c1);
answer += c0 * c1;
}
answer -= E.Count(x => colors[x.u] != colors[x.v]);
var cum = bipartiteSize.Sum();
foreach (var size in bipartiteSize)
{
cum -= size;
answer += size * cum;
}
Console.WriteLine(answer);
}
問題E
N個の頂点と1<=i<j<=Nとなる頂点i,j間の辺の重さが(A[i]^A[j]+A[j]^[i])%Mとしたときの最大全域木の重みが答えとなります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
mint.Modulo = M;
var list = new List<(long V, int A, int B)>(N * (N - 1));
for (var i = 0; i < N; i++)
{
for (var j = i + 1; j < N; j++)
{
var x = A[i];
var y = A[j];
var v = mint.Power(x, y) + mint.Power(y, x);
list.Add((v, i, j));
}
}
var dsu = new DisjointSetUnion(N);
long answer = 0;
foreach (var (v, a, b) in list.OrderByDescending(x => x.V))
{
if (dsu.IsSame(a, b)) continue;
dsu.Merge(a, b);
answer += v;
}
Console.WriteLine(answer);
}