はじめに
AtCoder Beginner Contest 311の復習記事です。
記事における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/abc311
問題A
char型は整数型として扱うことができるので、対象となる文字からAを引くことで、Aの場合は0、Bの場合は1、Cの場合は2にすることができ、配列のインデックスとして状態を管理することができます。
長さが3のbool型配列の全てがtrueになったときが何番目かを出力します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var used = new bool[3];
for (var i = 0; i < N; i++)
{
var c = S[i] - 'A';
used[c] = true;
if (used.All(x => x))
{
Console.WriteLine($"{i + 1}");
return;
}
}
}
問題B
X[i][j]をi番目の人のj日目までに連続する暇な日数としたとき、j日目の全ての人の連続する暇な日数の最小値は、j日目における選べる日数の最大値になります。
このことから、全てのjにおける選べる日数の最大値が答えとなります。
j日目までに連続する暇な日数は累積和で求めることができ、全体時間計算量O(ND)で答えを求めることができます。
public static void Solve()
{
var (N, D) = Scanner.Scan<int, int>();
var X = new int[N][];
for (var i = 0; i < N; i++)
{
var s = Scanner.Scan<string>();
X[i] = new int[D + 1];
for (var j = 0; j < D; j++)
{
if (s[j] == 'o')
{
X[i][j + 1] = X[i][j] + 1;
}
}
}
var answer = 0;
const int Inf = (int)1e9;
for (var j = 0; j <= D; j++)
{
var min = Inf;
for (var i = 0; i < N; i++)
{
min = Math.Min(min, X[i][j]);
}
answer = Math.Max(answer, min);
}
Console.WriteLine(answer);
}
問題C
Disjoint Set Unionなどでグラフにおける閉路の検知と始点を決めます。
深さ優先探索を行い、現在の頂点から既に訪れた頂点にたどり着くことができるかを判定していき、たどり着くことができるならば、その頂点は閉路を構成しているため、答えに追加するという操作を行います。
この方法では、答えが逆順に追加されていることに注意が必要です。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
var answer = new List<int>();
for (var i = 0; i < N; i++)
{
G[i].Add(A[i]);
}
var dsu = new DisjointSetUnion(N);
var s = -1;
for (var i = 0; i < N; i++)
{
if (dsu.IsSame(i, A[i]))
{
s = A[i];
break;
}
dsu.Merge(i, A[i]);
}
var used = new bool[N];
bool Dfs(int u)
{
if (used[u]) return true;
used[u] = true;
var result = false;
foreach (var v in G[u])
{
result |= Dfs(v);
}
if (result)
{
answer.Add(u);
}
return result;
}
Dfs(s);
answer.Reverse();
Console.WriteLine(answer.Count);
Console.WriteLine(string.Join(" ", answer.Select(x => x + 1)));
}
問題D
visited[i][j][d]をi行j列目に方向dで訪れたことがあるかとした幅優先探索を行います。
いずれかの方向でi行j列目に訪れることができれば、プレイヤーが触れることができる氷とすることができ、この数の総和が答えとなります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var G = new bool[N][];
for (var i = 0; i < N; i++)
{
G[i] = Scanner.Scan<string>().Select(x => x == '.').ToArray();
}
var visited = new bool[N, M, 4];
var queue = new Queue<(int H, int W, int D)>();
for (var i = 0; i < 4; i++)
{
visited[1, 1, i] = true;
queue.Enqueue((1, 1, i));
}
var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
while (queue.Count > 0)
{
var (ch, cw, d) = queue.Dequeue();
var (dh1, dw1) = D4[d];
var (nh1, nw1) = (ch + dh1, cw + dw1);
if (nh1 < 0 || N <= nh1 || nw1 < 0 || M <= nw1) continue;
if (visited[nh1, nw1, d]) continue;
if (G[nh1][nw1])
{
visited[nh1, nw1, d] = true;
queue.Enqueue((nh1, nw1, d));
}
else
{
for (var d = 0; d < 4; d++)
{
var (dh2, dw2) = D4[d];
var (nh2, nw2) = (ch + dh2, cw + dw2);
if (nh2 < 0 || N <= nh2 || nw2 < 0 || M <= nw2) continue;
if (visited[nh2, nw2, d] || !G[nh2][nw2]) continue;
visited[nh2, nw2, d] = true;
queue.Enqueue((nh2, nw2, d));
}
}
}
var answer = 0;
for (var i = 0; i < N; i++)
{
for (var j = 0; j < M; j++)
{
var ok = false;
for (var d = 0; d < 4; d++)
{
ok |= visited[i, j, d];
}
if (ok) answer++;
}
}
Console.WriteLine(answer);
}
問題E
次のような動的計画法を解きます。
dp[i][j] := (i,j)を正方形の右下隅としたときの穴のない正方形の辺の長さの最大値
遷移は次のようになります。
(i,j)が穴ではないとき、
dp[i][j] = Min(dp[i-1,j], dp[i,j-1], dp[i-1,j-1]) + 1;
(i,j)を正方形の右下隅としたとき、dp[i][j]通りの辺の長さの正方形を作ることができるので、全ての(i,j)におけるdp[i][j]の総和が答えとなります。
public static void Solve()
{
var (H, W, N) = Scanner.Scan<int, int, int>();
var isHole = new bool[H, W];
for (var i = 0; i < N; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
isHole[a, b] = true;
}
var dp = new int[H, W];
for (var i = 0; i < H; i++)
{
if (!isHole[i, 0]) dp[i, 0] = 1;
}
for (var j = 0; j < W; j++)
{
if (!isHole[0, j]) dp[0, j] = 1;
}
const int Inf = (int)1e9;
for (var i = 1; i < H; i++)
{
for (var j = 1; j < W; j++)
{
if (isHole[i, j]) continue;
var min = Inf;
min = Math.Min(min, dp[i - 1, j]);
min = Math.Min(min, dp[i, j - 1]);
min = Math.Min(min, dp[i - 1, j - 1]);
dp[i, j] = min + 1;
}
}
long answer = 0;
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
answer += dp[i, j];
}
}
Console.WriteLine(answer);
}