はじめに
AtCoder Beginner Contest 307の復習記事です。
記事における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/abc307
問題A
i (0-indexed)番目の歩数は、Floor(i/7)週目の歩数になることに注意して、総和を数え上げます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var answers = new long[N];
for (var i = 0; i < N * 7; i++)
{
answers[i / 7] += A[i];
}
Console.WriteLine(string.Join(" ", answers));
}
問題B
i!=jとなるS[i]、S[j]を繋げた文字が回文であるかを判定します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = new string[N];
for (var i = 0; i < N; i++)
{
S[i] = Scanner.Scan<string>();
}
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
if (i == j) continue;
var T = S[i] + S[j];
var m = T.Length;
var ok = true;
for (var k = 0; k < m - 1 - k; k++)
{
ok &= T[k] == T[m - 1 - k];
}
if (ok)
{
Console.WriteLine("Yes");
return;
}
}
}
Console.WriteLine("No");
}
問題C
縦Hマス、横Wマスのシートの配置方法は、(H*2-1)*(W*2-1)通りあります。
シートAとシートBをそれぞれ(H*2-1)*(W*2-1)通りずつ配置し、黒いマスの座標の集合がシートXの座標の集合と一致しているかを判定します。
このとき、配置されたシートAの座標の集合は、シートXの座標の集合の部分集合である必要があるため、配置されたシートAの座標の集合がシートXの座標の集合の部分集合ではない場合に枝刈りすることで高速化することができます。
public static void Solve()
{
var P = new HashSet<(int H, int W)>[3];
for (var k = 0; k < 3; k++)
{
P[k] = new HashSet<(int H, int W)>();
var (H, W) = Scanner.Scan<int, int>();
for (var i = 0; i < H; i++)
{
var s = Scanner.Scan<string>();
for (var j = 0; j < W; j++)
{
if (s[j] == '#')
{
P[k].Add((i, j));
}
}
}
}
var A = P[0];
var B = P[1];
var X = P[2];
for (var dia = -10; dia <= 10; dia++)
{
for (var dja = -10; dja <= 10; dja++)
{
var a = A.Select(p => (p.H + dia, p.W + dja)).ToHashSet();
if (!a.IsSubsetOf(X)) continue;
for (var dib = -10; dib <= 10; dib++)
{
for (var djb = -10; djb <= 10; djb++)
{
var b = B.Select(p => (p.H + dib, p.W + djb));
if (a.Concat(b).ToHashSet().SetEquals(X))
{
Console.WriteLine("Yes");
return;
}
}
}
}
}
Console.WriteLine("No");
}
問題D
削除すべき文字列の区間は、(が出現してから初めて出現する)までの区間となります。
これは、文字列Sを順にみていき、)が出現したときに対応する(までの文字を削除することで、答えを得ることができます。
ただし、)に対応する(が存在しない場合があります。
そこで、ある文字が何個の()で囲まれているかをlevelとしたとき、(が出現したときはlevelを+1、)が出現したときはlevelを-1とすると、levelが負のとき、)に対応する(が存在しないことを判定することができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var level = 0;
var T = new char[N];
var idx = 0;
foreach (var c in S)
{
if (c == ')' && level > 0)
{
while (idx >= 0 && T[idx - 1] != '(') idx--;
idx--;
level--;
}
else
{
T[idx++] = c;
if (c == '(') level++;
}
}
var answer = new string(T[..idx]);
Console.WriteLine(answer);
}