はじめに
AtCoder Beginner Contest 264の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc264
問題A
C#では、SubStringメソッドに始点と長さを指定することで、部分文字列を取得することができます。
public static void Solve()
{
var (L, R) = Scanner.Scan<int, int>();
L--;
const string atcoder = "atcoder";
var answer = atcoder.SubString(L, R - L);
Console.WriteLine(answer);
}
また、文字列スライスを使うことで[L,R)区間の部分文字列を取得することもできます。
public static void Solve()
{
var (L, R) = Scanner.Scan<int, int>();
L--;
const string atcoder = "atcoder";
var answer = atcoder[L..R];
Console.WriteLine(answer);
}
問題B
中心(8行目8列目)からの行の距離と列の距離の最大値の偶奇によって色分けされているので、それを判定します。
public static void Solve()
{
var (R, C) = Scanner.Scan<int, int>();
var mid = 8;
var r = Math.Abs(mid - R);
var c = Math.Abs(mid - C);
var answer = Math.Max(r, c) % 2 == 0 ? "white" : "black";
Console.WriteLine(answer);
}
問題C
行列Aのうち、どの行と列を使うかの組み合わせを全探索してます。
これは、bit全探索(2のn乗のビットが立っていれば、そのn行目またはn列目を使う)を行うことで簡潔に書くことができます。
時間計算量は、最大でも(2^10)*(2^10)≒10^6なので、余裕で間に合います。
public static void Solve()
{
var (H1, W1) = Scanner.Scan<int, int>();
var A = new int[H1][];
for (var i = 0; i < H1; i++)
{
A[i] = Scanner.ScanEnumerable<int>().ToArray();
}
var (H2, W2) = Scanner.Scan<int, int>();
var B = new int[H2][];
for (var i = 0; i < H2; i++)
{
B[i] = Scanner.ScanEnumerable<int>().ToArray();
}
for (var H = 0; H < 1 << H1; H++)
{
var hc = 0;
for (var k = 0; k < H1; k++)
{
if ((H >> k & 1) == 1) hc++;
}
if (hc != H2) continue;
for (var W = 0; W < 1 << W1; W++)
{
var wc = 0;
for (var k = 0; k < W1; k++)
{
if ((W >> k & 1) == 1) wc++;
}
if (wc != W2) continue;
var G = new List<List<int>>();
for (var i = 0; i < H1; i++)
{
if ((H >> i & 1) == 1) G.Add(new List<int>());
else continue;
for (var j = 0; j < W1; j++)
{
if ((W >> j & 1) == 1) G[^1].Add(A[i][j]);
}
}
var ok = true;
for (var i = 0; i < H2; i++)
{
for (var j = 0; j < W2; j++)
{
ok &= G[i][j] == B[i][j];
}
}
if (ok)
{
Console.WriteLine("Yes");
return;
}
}
}
Console.WriteLine("No");
}
問題D
数列をソートするための最小の操作回数は転倒数と一致するため、文字がatcoderの何番目に値するかに変換した数列の転倒数を求めることで、時間計算量O(|S|log|S|)で答えを求めることができます。
public static void Solve()
{
const int N = 7;
var S = Scanner.Scan<string>();
int F(char c)
{
return c switch
{
'a' => 0,
't' => 1,
'c' => 2,
'o' => 3,
'd' => 4,
'e' => 5,
'r' => 6,
_ => 7,
};
}
var T = S.Select(x => F(x)).ToArray();
var ft = new FenwickTree(10);
var answer = 0L;
for (var i = 0; i < N; i++)
{
var c = T[i];
answer += i - ft.Sum(c + 1);
ft.Add(c, 1);
}
Console.WriteLine(answer);
}
文字列を頂点として、隣接する文字を入れ替えていく幅優先探索でも、時間計算量O(|S|!)で答えを求めることができます。
問題E
全ての発電所から電線がつながっている都市をクエリごとに計算してしまうと、連結成分の判定にDisjoint Set Union (DSU)を使ったとしても、DSUの構成に時間計算量O(α(N+M)) (α:アッカーマンの逆関数、非常に小さな定数)、全ての発電所の連結成分の個数の数え上げに時間計算量O(M)となってしまい、全体でO(Q(α(N+M)+M))となり、実行時間制限に間に合いません。
そこで、使わない電線をあらかじめ繋いでおき、そこにクエリの逆順で電線を繋いでいくという問題に言い換えると、クエリごとに毎回DSUを構築しなおす必要がなくなり、クエリ当たりの時間計算量が、全ての発電所の連結成分の個数の数え上げのO(M)のみになります。
さらに、全ての発電所の連結成分の数え上げを、ある一つの発電所に連結成分をまとめ、その発電所のみ調べることで、時間計算量をO(1)にすることができます。
このことから、クエリの先読み逆順処理と発電所のまとめあげをおこなうことで、全体の時間計算量をO(α(N+M)+Q)で答えを求めることができます。
public static void Solve()
{
var (N, M, E) = Scanner.Scan<int, int, int>();
var Edges = new (int U, int V)[E];
for (var i = 0; i < E; i++)
{
var (u, v) = Scanner.Scan<int, int>();
Edges[i] = (u, v);
}
var Q = Scanner.Scan<int>();
var X = new int[Q];
var removes = new bool[E];
for (var i = 0; i < Q; i++)
{
var x = Scanner.Scan<int>() - 1;
X[i] = x;
removes[x] = true;
}
var s = 0;
var dsu = new DisjointSetUnion(N + M + 1);
for (var u = N + 1; u <= N + M; u++)
{
dsu.Merge(s, u);
}
for (var i = 0; i < E; i++)
{
if (!removes[i])
{
var (u, v) = Edges[i];
dsu.Merge(u, v);
}
}
var answer = new int[Q];
for (var i = Q - 1; i >= 0; i--)
{
answer[i] = dsu.SizeOf(s) - (M + 1);
var (u, v) = Edges[X[i]];
dsu.Merge(u, v);
}
Console.WriteLine(string.Join("\n", answer));
}