はじめに
AtCoder Beginner Contest 337の復習記事です。
記事における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/abc337
問題A
チーム高橋の合計得点とチーム青木の合計得点を数え上げます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var a = 0;
var b = 0;
for (var i = 0; i < N; i++)
{
var (x, y) = Scanner.Scan<int, int>();
a += x;
b += y;
}
var answer = "Draw";
if (a > b) answer = "Takahashi";
if (b > a) answer = "Aoki";
Console.WriteLine(answer);
}
問題B
A、B、Cをそれぞれ0、1、2としたとき、S[i]-S[i-1]が全てのi (1<=i<N)において0以上であることが拡張ABC文字列であることの条件になります。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
for (var i = 1; i < S.Length; i++)
{
if (S[i] - S[i - 1] < 0)
{
Console.WriteLine("No");
return;
}
}
Console.WriteLine("Yes");
}
問題C
A[i]==-1の場合はcurr=iとし、それ以外の場合はnext[A[i]]=iとすると、i番目の人はcurrであり、その次の人はcurr=next[curr]になり、これをN人分求めることで、答えを求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var next = new int[N];
var curr = -1;
for (var i = 0; i < N; i++)
{
if (A[i] == -1) curr = i;
else next[A[i] - 1] = i;
}
var answer = new int[N];
for (var i = 0; i < N; i++)
{
answer[i] = curr;
curr = next[curr];
}
Console.WriteLine(string.Join(" ", answer.Select(x => x + 1)));
}
問題D
横にK個のマスを全てoにできるかを考えます。
これは、各行ごとにoの数の累積和cumOを求めておくことで、連続するK列の区間にあるoの数をcumO[i+K]-cumO[i]で求めることができ、oの数をcとしたとき、K-cが.またはxの数になります。
そのため、xの累積和cumXを同様に求め、同じ区間のxの数が0の場合、その区間の.の数はK-c個となり、K-c個をoにすることで連続したK列をoにすることができます。
同様に縦の場合も考え、全ての連続するK列またはK行のうち、その区間にxが存在しない場合のk-cの最小値が答えとなります。
例
public static void Solve()
{
var (H, W, K) = Scanner.Scan<int, int, int>();
var S = new char[H][];
for (var i = 0; i < H; i++)
{
S[i] = Scanner.Scan<string>().ToCharArray();
}
var oX = new long[H, W + 1];
var oY = new long[H + 1, W];
var xX = new long[H, W + 1];
var xY = new long[H + 1, W];
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
oX[i, j + 1] += oX[i, j];
oY[i + 1, j] += oY[i, j];
xX[i, j + 1] += xX[i, j];
xY[i + 1, j] += xY[i, j];
if (S[i][j] == 'o')
{
oX[i, j + 1] += 1;
oY[i + 1, j] += 1;
}
else if (S[i][j] == 'x')
{
xX[i, j + 1] += 1;
xY[i + 1, j] += 1;
}
}
}
const long Inf = 1 << 30;
var answer = Inf;
for (var i = 0; i < H; i++)
{
for (var j = 0; j + K <= W; j++)
{
var o = oX[i, j + K] - oX[i, j];
var x = xX[i, j + K] - xX[i, j];
if (x == 0) answer = Math.Min(answer, K - o);
}
}
for (var j = 0; j < W; j++)
{
for (var i = 0; i + K <= H; i++)
{
if (S[i][j] == 'x') continue;
var o = oY[i + K, j] - oY[i, j];
var x = xY[i + K, j] - xY[i, j];
if (x == 0) answer = Math.Min(answer, K - o);
}
}
if (answer == Inf) answer = -1;
Console.WriteLine(answer);
}
問題E
毒ワインで有名な問題です。
N本のジュースの毒を判別するための最少人数はlog2(N)人であり、i番目の人がx番目のジュースを飲むかどうかは、xを2進数で見たときにi番目のビットが1である場合にのみ飲むことで、おなかを壊した人の文字列を2進数としてみることができるようになり、それを10進数に変換した番目のジュースが答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var M = 0;
while (1 << M < N) M++;
Console.WriteLine(M);
var lists = new List<int>[M].Select(_ => new List<int>()).ToArray();
for (var i = 0; i < N; i++)
{
for (var k = 0; k < M; k++)
{
if ((i >> k & 1) == 1) lists[k].Add(i + 1);
}
}
foreach (var list in lists)
{
Console.WriteLine($"{list.Count} {string.Join(" ", list)}");
}
var S = Scanner.Scan<string>();
var answer = 0;
for (var i = 0; i < M; i++)
{
answer |= (S[i] - '0') << i;
}
answer++;
Console.WriteLine(answer);
}