はじめに
AtCoder Beginner Contest 329の復習記事です。
記事における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/abc329
問題A
C#では、string.Joinメソッドを使うと、指定した区切り文字で与えられたシーケンスを文字列として結合することができます。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
Console.WriteLine(string.Join(" ", S.ToArray()));
}
問題B
Aから重複をなくしたものをソートし、2番目に大きいものが答えとなります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var B = A.Distinct().ToArray();
Array.Sort(B);
Array.Reverse(B);
var answer = B[1];
Console.WriteLine(answer);
}
問題C
1種類の文字からなる長さがLの連続部分列が存在するとき、長さがL-1の連続部分列も存在します。
よって、ある文字のみからなる連続部分列の最大長が、その文字のからなる連続部分列の種類の個数になります。
このことから、全ての文字ごとのその文字のみからなる連続部分列の最大長の和が答えとなります。
連続部分列の長さは、尺取り法を行うことで時間計算量O(N)で求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>().Select(x => x - 'a').ToArray();
var maxLengths = new int[26];
var l = 0;
var r = 0;
while (l < N)
{
while (r < N && S[r] == S[l]) r++;
maxLengths[S[l]] = Math.Max(maxLengths[S[l]], r - l);
l = r;
}
var answer = maxLengths.Sum();
Console.WriteLine(answer);
}
問題D
count[x]を候補者xの得票数、i-1票目に当選した候補者をyとします。
i票目の投票により、候補者A[i]の票が+1されます。
このとき、count[A[i]]>count[y]の場合、A[i]の得票数が最多となるので、A[i]が答えになります。
count[A[i]]==count[y]の場合、A[i]とyは得票数が最多の候補者が複数いることになるので、Min(A[i],y)が答えとなります。
count[A[i]]<count[y]の場合、変わらずyの得票数が最多なので、yが答えとなります。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var count = new int[N + 1];
var answer = 0;
foreach (var a in A)
{
count[a]++;
if (count[answer] < count[a])
{
answer = a;
}
else if (count[answer] == count[a])
{
answer = Math.Min(answer, a);
}
Console.WriteLine(answer);
}
}
問題E
元の操作に対して、逆の操作を考えます。
これは、Sのi文字目から長さMの連続する部分文字列に対して、全てのjにおいてS[i+j]=='#'またはS[i+j]==T[j]であるとき、その部分文字列を全て#にするという操作になります。
この操作を繰り返し、全ての文字が#になっている場合、答えはYesになります。
この操作をi番目に対しての操作としたとき、i番目に対して複数回操作を行う必要はないので、i番目に対して既に操作を行ったことがあるかを管理しながら、i番目の前後M-1箇所に対して判定を行っていくことで、時間計算量O(NM^2)で答えを求めることができます。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = Scanner.Scan<string>();
var T = Scanner.Scan<string>();
var X = S.ToCharArray();
var used = new bool[N - (M - 1)];
var queue = new Queue<int>();
void F(int idx)
{
if (used[idx]) return;
var ok = true;
for (var i = 0; i < M && ok; i++)
{
ok &= (X[idx + i] == '#' || X[idx + i] == T[i]);
}
if (ok)
{
used[idx] = true;
queue.Enqueue(idx);
}
}
for (var i = 0; i < N - (M - 1); i++)
{
F(i);
}
while (queue.Count > 0)
{
var idx = queue.Dequeue();
X.AsSpan(idx, M).Fill('#');
for (var i = Math.Max(0, idx - (M - 1)); i <= Math.Min(N - M, idx + (M - 1)); i++)
{
F(i);
}
}
var answer = new string(X) == new string('#', N);
Console.WriteLine(answer ? "Yes" : "No");
}
問題F
S[i]をi番目の箱に入っているボールの色の集合とします。
各クエリにおいて、S[a]からS[b]にボールを移動し、S[a]を空にするという操作を行います。
このとき、|S[a]|>|S[b]|の場合、S[a]からS[b]にボールを移動する代わりに、S[a]とS[b]を入れ替えてからS[a]からS[b]にボールを移動させることで、ボールの移動回数を減らすことができます。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var C = Scanner.ScanEnumerable<int>().ToArray();
var set = C.Select(c => new HashSet<int> { c }).ToArray();
while (Q-- > 0)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
if (set[b].Count < set[a].Count) (set[a], set[b]) = (set[b], set[a]);
set[b].UnionWith(set[a]);
set[a].Clear();
Console.WriteLine(set[b].Count);
}
}