はじめに
AtCoder Beginner Contest 333の復習記事です。
記事における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/abc333
問題A
C#では、stringのコンストラクタに文字と長さを与えると、与えられた文字を与えられた長さ繰り返した文字列を生成することができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var answer = new string((char)(N + '0'), N);
Console.WriteLine(answer);
}
問題B
ある線分の長さが等しいとき、A-B-C-D-E-Aとして長さ1の辺で連結しているときの、時計回りで辿る頂点間の距離と反時計回りで辿る頂点間の距離のうち小さい方を頂点間の距離としたとき、頂点間の距離も等しくなります。
A,B,C,D,Eを0,1,2,3,4、S[0]<S[1]、T[0]<T[1]とします。
反時計回りで辿ったときの頂点間の距離はS[1]-S[0]になり、E-Aをまたぐことを1周したとしてS[0]の値を+5して考えると、時計回りで辿ったときの頂点間の距離はS[0]+5-S[1]になり、これらのうち小さい方がその頂点間の距離になります。
例
public static void Solve()
{
var S = Scanner.Scan<string>().Select(x => x - 'A').ToArray();
var T = Scanner.Scan<string>().Select(x => x - 'A').ToArray();
Array.Sort(S);
Array.Sort(T);
var d1 = Math.Min(S[1] - S[0], S[0] + 5 - S[1]);
var d2 = Math.Min(T[1] - T[0], T[0] + 5 - T[1]);
var answer = d1 == d2;
Console.WriteLine(answer ? "Yes" : "No");
}
問題C
あり得る数を全列挙し、N番目の数を求めます。
i番目のレピュニット数R[i]は、R[1]=1、R[i]=R[i-1]*10+1になります。
入出力例から333番目は13桁あればいいので、13桁のレピュニット数を3つ選ぶ方法を全探索し、重複を削除したもののN番目が答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var M = 13;
var A = new long[M];
A[0] = 1;
for (var i = 1; i < M; i++)
{
A[i] = A[i - 1] * 10 + 1;
}
var set = new HashSet<long> { 0 };
for (var i = 0; i < M; i++)
{
for (var j = 0; j < M; j++)
{
for (var k = 0; k < M; k++)
{
set.Add(A[i] + A[j] + A[k]);
}
}
}
var array = set.Order().ToArray();
var answer = array[N];
Console.WriteLine(answer);
}
問題D
頂点1を葉にするには、頂点1に連結しているM個の部分木のうち、M-1個の部分木を削除することで達成できます。
よって、M個の部分木の大きさをそれぞれ数え上げ、その中で一番大きな部分木以外の部分木を削除し、最後に頂点1を削除することが最小の操作回数となります。
また、部分木の大きさは深さ優先探索で求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
for (var i = 0; i < N - 1; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
G[a].Add(b);
G[b].Add(a);
}
int Dfs(int u, int p)
{
var result = 0;
foreach (var v in G[u])
{
if (v == p) continue;
result += Dfs(v, u);
}
return result + 1;
}
const int Inf = 1 << 30;
var counts = new int[G[0].Count];
for (var i = 0; i < G[0].Count; i++)
{
counts[i] = Dfs(G[0][i], 0);
}
var answer = counts.Sum() - counts.Max() + 1;
Console.WriteLine(answer);
}
問題E
出来事を後ろから見ていくことで、その時点で必要なポーションの個数を計算することができます。
x番目のモンスターに必要なポーションの個数をP[x]、必要なポーションの個数の合計をkとします。
出来事を後ろから見ていったとき、
t==1のとき、P[x]==0ならば、この出来事の後にはxのポーションが必要なモンスターは出てこないため、そのポーションを拾う必要はありません。P[x]>0ならば、この出来事の後にはxのポーションが必要なモンスターが出てくるため、そのポーションを拾う必要があります。 また、P[x]-=1,k-=1になります。
t==2のとき、xのポーションが必要なモンスターが出てくるため、P[x]+=1になります。
そして、全ての出来事を見たとき、k>0ならば、必要なポーションが足りていないので答えは-1になり、k==0ならば、全ての出来事の間のkの最大値がKminになり、t==1 && P[x]>0のときの出来事のポーションを拾うことが答えとなります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var Q = new Query[N];
for (var i = 0; i < N; i++)
{
var (t, x) = Scanner.Scan<int, int>();
Q[i] = new Query(t, x - 1);
}
var answers = new List<int>();
var P = new int[N];
var k = 0;
var minK = 0;
for (var i = N - 1; i >= 0; i--)
{
var (t, x) = Q[i];
if (t == 1)
{
if (P[x] == 0)
{
answers.Add(0);
}
else
{
answers.Add(1);
minK = Math.Max(minK, k);
P[x]--;
k--;
}
}
else
{
P[x]++;
k++;
}
}
if (k > 0)
{
Console.WriteLine(-1);
}
else
{
answers.Reverse();
Console.WriteLine(minK);
Console.WriteLine(string.Join(" ", answers));
}
}
public readonly record struct Query(int T, int X);