はじめに
AtCoder Beginner Contest 328の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
Scannerクラス
public static class Scanner
{
public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]));
}
public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
}
public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
}
public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
}
public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
}
public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
private static string[] ScanStringArray()
{
var line = Console.ReadLine()?.Trim() ?? string.Empty;
return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
}
private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}
コンテスト
https://atcoder.jp/contests/abc328
問題A
Sのうち、X以下の値の総和を求めます。
C#では、配列などのIEnumerable<T>に対してLINQを使って例のように書くことができます。
例
public static void Solve()
{
var (N, X) = Scanner.Scan<int, int>();
var S = Scanner.ScanEnumerable<int>().ToArray();
var answer = S.Where(x => x <= X).Sum();
Console.WriteLine(answer);
}
問題B
ぞろ目であるには、月と日の数字がすべて同じである必要があるため、各数字が1から9のいずれかである必要があります。
そのため、ぞろ目にする数字xを全探索し、N以下のxを並べてできた値の月mのうち、D[m]以下のxを並べてできた値の日dの数を数え上げます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var D = Scanner.ScanEnumerable<int>().ToArray();
var answer = 0;
for (var b = 1; b < 10; b++)
{
var m = b;
while (m <= N)
{
var d = b;
while (d <= D[m - 1])
{
answer++;
d *= 10;
d += b;
}
m *= 10;
m += b;
}
}
Console.WriteLine(answer);
}
問題C
S[l..r]を全探索してしまうと、時間計算量がO(N^2)になってしまいます。
そこで、あらかじめx文字までに文字が隣り合う回数を累積和cum[x]として時間計算量O(N)で計算しておき、クエリごとにcum[r]-cum[l-1]を計算することで、S[l..r]の文字が隣り合う回数を時間計算量O(1)で求められるようになります。
ただし、S[l]==S[l-1]である場合、S[l-1]は範囲外であるため、答えを-1する必要がある点に注意が必要です。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var S = Scanner.Scan<string>();
var cum = new int[N + 1];
for (var i = 1; i < N; i++)
{
cum[i + 1] += cum[i];
if (S[i] == S[i - 1]) cum[i + 1]++;
}
while (Q-- > 0)
{
var (l, r) = Scanner.Scan<int, int>();
l--;
var answer = cum[r] - cum[l];
if (l > 0 && S[l - 1] == S[l]) answer--;
Console.WriteLine(answer);
}
}
問題D
文字列Tのm文字目までの文字が決まっているとしたとき、3文字を削除することはmを-3することと同じ意味になります。
よって、はじめにTを空文字、m=0として、Sのi番目の文字を順に追加していき、Tの長さが3文字以上かつ末尾がABCとなる場合はABCを削除しながらmを更新していくことで、最終的にできた文字列が答えとなります。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var N = S.Length;
var T = new char[N];
var m = 0;
for (var i = 0; i < N; i++)
{
T[m] = S[i];
while (m >= 2 && T[m - 2] == 'A' && T[m - 1] == 'B' && T[m] == 'C')
{
m -= 3;
}
m++;
}
var answer = new string(T[..m]);
Console.WriteLine(answer);
}
問題E
N頂点のグラフの全域木には、N-1本の辺が必要となります。
よって、M本の辺からN-1本を選ぶ組み合わせを全探索し、そのN-1本の辺の組み合わせが全域木になる場合のコストの最小値が答えとなります
N-1本の辺の組み合わせが全域木になるかは、DSUなどのデータ構造を使ってグラフの連結成分が1つであることを示すことで判定することができます。
例
public static void Solve()
{
var (N, M, K) = Scanner.Scan<int, int, long>();
var E = new (int U, int V, long W)[M];
for (var i = 0; i < M; i++)
{
var (u, v, w) = Scanner.Scan<int, int, long>();
u--; v--;
E[i] = (u, v, w);
}
var answer = K;
foreach (var order in Combine(Enumerable.Range(0, M), N - 1))
{
long cost = 0;
var dsu = new DisjointSetUnion(N);
foreach (var (u, v, w) in order.Select(x => E[x]))
{
dsu.Merge(u, v);
cost += w;
cost %= K;
}
if (dsu.SizeOf(0) == N)
{
answer = Math.Min(answer, cost);
}
}
Console.WriteLine(answer);
}
public static IEnumerable<TSource[]> Combine<TSource>(IEnumerable<TSource>? source, int count)
{
if (source is null) throw new ArgumentNullException(nameof(source));
IEnumerable<TSource[]> Inner()
{
var items = source.ToArray();
if (count <= 0 || items.Length < count) throw new ArgumentOutOfRangeException(nameof(count));
var n = items.Length;
var indices = new int[n];
for (var i = 0; i < indices.Length; i++)
{
indices[i] = i;
}
TSource[] Result()
{
var result = new TSource[count];
for (var i = 0; i < count; i++)
{
result[i] = items[indices[i]];
}
return result;
}
yield return Result();
while (true)
{
var done = true;
var idx = 0;
for (var i = count - 1; i >= 0; i--)
{
if (indices[i] == i + n - count) continue;
idx = i;
done = false;
break;
}
if (done) yield break;
indices[idx]++;
for (var i = idx; i + 1 < count; i++)
{
indices[i + 1] = indices[i] + 1;
}
yield return Result();
}
}
return Inner();
}
問題F
N個の頂点があり、各頂点の値がX[i]であるものを考えます。
部分集合Sが良い集合であるということは、部分集合Sに含まれる全てのクエリ(a,b,d)において、X[a]-X[b]==dであり、頂点aと頂点b間は同じ連結成分であると考えることができます。
よって、各クエリ(a,b,d)を順に見ていったとき、頂点aと頂点bが同じ連結成分である場合は、X[a]-X[b]==dが成り立つ場合にのみクエリをSに追加できます。
一方、頂点aと頂点bが異なる連結成分である場合は、X[a]-X[b]==dとなるように片方の連結集合の全てのXの値を変更することで、頂点aと頂点bを同じ連結成分にできるため、クエリをSに追加することができます。
この操作をマージとしたとき、連結成分の小さい方から大きい方へマージすることで、高速にマージすることができるようになります。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var S = new List<int>();
var X = new long[N];
var dsu = new DisjointSetUnion(N);
var nodes = new List<int>[N];
for (var i = 0; i < N; i++)
{
nodes[i] = new List<int> { i };
}
for (var i = 0; i < Q; i++)
{
var (a, b, d) = Scanner.Scan<int, int, long>();
a--; b--;
if (dsu.IsSame(a, b))
{
if (X[a] - X[b] == d)
{
S.Add(i);
}
}
else
{
var (u, v) = (dsu.LeaderOf(a), dsu.LeaderOf(b));
d -= X[a] - X[b];
if (nodes[u].Count < nodes[v].Count)
{
(u, v) = (v, u);
d *= -1;
}
for (var j = 0; j < nodes[v].Count; j++)
{
nodes[u].Add(nodes[v][j]);
X[nodes[v][j]] -= d;
}
dsu.Merge(a, b);
S.Add(i);
}
}
Console.WriteLine(string.Join(" ", S.Select(x => x + 1)));
}