はじめに
AtCoder Beginner Contest 295の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc295
問題A
各Wについて、and、not、that、the、youのいずれかと一致するかを判定します。
対象となる5つの語を配列にまとめることで、Containsメソッドで引数に指定した値が配列内に存在するかを判定することでき、この操作を各Wについて
行い、いずれかが一致すれば答えはYes、しなければ答えはNoとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var W = Scanner.ScanEnumerable<string>().ToArray();
var words = new[] { "and", "not", "that", "the", "you" };
var answer = W.Any(x => words.Contains(x));
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
爆発後の盤面をGとしたとき、Gの初期状態はBであり、B[r1][c1]が爆弾の場合は、マンハッタン距離がB[r1][c1]以下となるG[r2][c2]を空きマスにします。
1<=R,C<=20と制約が小さいため、r1、c1、r2、c2を全探索しても、最大でも20^4=160,000なので十分高速です。
public static void Solve()
{
var (R, C) = Scanner.Scan<int, int>();
var B = new char[R][];
for (var i = 0; i < R; i++)
{
B[i] = Scanner.Scan<string>().ToCharArray();
}
bool IsWallOrEmpty(char c) => c == '#' || c == '.';
int Distance(int r1, int c1, int r2, int c2) => Math.Abs(r1 - r2) + Math.Abs(c1 - c2);
var G = new char[R, C];
for (var i = 0; i < R; i++)
{
for (var j = 0; j < C; j++)
{
G[i, j] = B[i][j];
}
}
for (var r1 = 0; r1 < R; r1++)
{
for (var c1 = 0; c1 < C; c1++)
{
if (IsWallOrEmpty(B[r1][c1])) continue;
var x = B[r1][c1] - '0';
for (var r2 = 0; r2 < R; r2++)
{
for (var c2 = 0; c2 < C; c2++)
{
if (Distance(r1, c1, r2, c2) <= x)
{
G[r2, c2] = '.';
}
}
}
}
}
Printer.Print2D(G);
}
問題C
辞書などのデータ構造を使って各色の靴下の個数をそれぞれ数え上げ、各色の靴下の個数/2の合計が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var dict = new Dictionary<int, long>();
foreach (var a in A)
{
if (!dict.ContainsKey(a)) dict[a] = 0;
dict[a]++;
}
var answer = dict.Values.Sum(x => x / 2);
Console.WriteLine(answer);
}
問題D
嬉しい文字列である条件は、その文字列に存在する各数字について、全ての個数が偶数であることが条件です。
ある数字に注目したとき、範囲[l,r)に存在する数字個数は、cum[i]をi文字目までの累積和としたとき、cum[r]-cum[l]で求めることができます。
また、範囲[l,r)に存在する数字の個数が偶数であるには、cum[r]-cum[l]が偶数-偶数、または奇数-奇数である必要があります。
この条件が全ての数字に当てはまることから、l文字目まで見たときの各数字の個数の偶奇と、r文字目まで見たときの各数字の個数の偶奇が一致すれば、その[l,r)は嬉しい文字列であることがわかります。
このことから、各0<=i<=|S|について、各数字の個数の偶奇の集合の個数を数え上げ、集合がx個ある場合、x個のうちから2個選ぶ組み合わせが、その集合になる[l,r)の組み合わせの個数になります。
各数字の個数の偶奇の集合について、数字は0から9の10種類のみかつそれぞれ偶奇の2通りのため、整数型の各ビットに偶奇フラグとして保持することができます。
これは、初期状態0に対して、1<<S[i]の排他的論理和を累積していくことで、iまで見たときの各数字の個数の偶奇の集合として管理することができます。
public static void Solve()
{
var S = Scanner.Scan<string>().Select(x => x - '0').ToArray();
var N = S.Length;
var dict = new Dictionary<int, long>();
var curr = 0;
dict[curr] = 1;
for (var i = 0; i < N; i++)
{
curr ^= 1 << S[i];
if (!dict.ContainsKey(curr)) dict[curr] = 0;
dict[curr]++;
}
var answer = dict.Values.Sum(x => x * (x - 1) / 2);
Console.WriteLine(answer);
}