はじめに
AtCoder Beginner Contest 322の復習記事です。
記事における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/abc322
問題A
C#では、String.IndexOfメソッドを使うことで、文字列のうち指定した文字列が最初に出現する位置を求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var answer = S.IndexOf("ABC");
if (answer != -1) answer += 1;
Console.WriteLine(answer);
}
問題B
SとTの先頭N文字が一致しているかをisPrefix、SとTの末尾N文字が一致しているかをisSuffixとして求めておき、それぞれの条件に対応した答えを出力します。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = Scanner.Scan<string>();
var T = Scanner.Scan<string>();
var isPrefix = true;
var isSuffix = true;
for (var i = 0; i < N; i++)
{
isPrefix &= T[i] == S[i];
isSuffix &= T[M - 1 - i] == S[N - 1 - i];
}
if (isPrefix && isSuffix)
{
Console.WriteLine(0);
}
else if (isPrefix)
{
Console.WriteLine(1);
}
else if (isSuffix)
{
Console.WriteLine(2);
}
else
{
Console.WriteLine(3);
}
}
問題C
各iにつき愚直にAを探索すると全体時間計算量がO(N^2)になってしまうので、各iにつきAを二部探索することで全体時間計算量O(NlogN)で答えを求めることができます。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
for (var i = 1; i <= N; i++)
{
var lb = LowerBound(A, i);
Console.WriteLine(A[lb] - i);
}
}
public static int LowerBound<T>(List<T> source, T key, IComparer<T>? comparer = null)
=> LowerBound(System.Runtime.InteropServices.CollectionsMarshal.AsSpan(source), key, comparer);
public static int LowerBound<T>(ReadOnlySpan<T> source, T key, IComparer<T>? comparer = null)
{
comparer ??= Comparer<T>.Default;
var (lo, hi) = (-1, source.Length);
while (hi - lo > 1)
{
var mi = lo + ((hi - lo) >> 1);
if (comparer.Compare(source[mi], key) >= 0) hi = mi;
else lo = mi;
}
return hi;
}
問題D
全てのポリオミノの回転の組み合わせと全てのポリオミノの平行移動の組み合わせを全探索します。
public static void Solve()
{
const int N = 4;
var P = new char[3][,];
for (var k = 0; k < 3; k++)
{
P[k] = new char[N, N];
for (var i = 0; i < N; i++)
{
var p = Scanner.Scan<string>().ToCharArray();
for (var j = 0; j < N; j++)
{
P[k][i, j] = p[j];
}
}
}
var G = new char[N, N];
const int Inf = 1 << 30;
// グリッドの初期化
void Init(char[,] g)
{
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
g[i, j] = '.';
}
}
}
// ポリオミノを回転させ、左上に寄せる
char[,] Rotate(char[,] p)
{
// ポリオミノを回転させる
var tmp = new char[N, N];
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
tmp[i, j] = p[j, N - 1 - i];
}
}
// 左上に寄せるために#が出現する最小のhとwを求める
var h = Inf;
var w = Inf;
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
if (tmp[i, j] == '#')
{
h = Math.Min(h, i);
w = Math.Min(w, j);
}
}
}
// ポリオミノを左上に寄せる
var result = new char[N, N];
if (h == Inf) return result;
for (var i = 0; h + i < N; i++)
{
for (var j = 0; w + j < N; j++)
{
result[i, j] = tmp[h + i, w + j];
}
}
return result;
}
// グリッドに平行移動させたポリオミノを配置できるかを判定する
bool Fill(char[,] p, int dh, int dw)
{
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
if (p[i, j] == '#')
{
if (dh + i < N && dw + j < N && G[dh + i, dw + j] != '#')
{
G[dh + i, dw + j] = '#';
}
else
{
return false;
}
}
}
}
return true;
}
// 平行移動
IEnumerable<(int dh, int dw)> Delta()
{
for (var h = 0; h < N; h++)
{
for (var w = 0; w < N; w++)
{
yield return (h, w);
}
}
}
for (var a = 0; a < 4; a++)
{
P[0] = Rotate(P[0]);
for (var b = 0; b < 4; b++)
{
P[1] = Rotate(P[1]);
for (var c = 0; c < 4; c++)
{
P[2] = Rotate(P[2]);
foreach (var (dha, dwa) in Delta())
{
foreach (var (dhb, dwb) in Delta())
{
foreach (var (dhc, dwc) in Delta())
{
var ok = true;
Init(G);
ok &= Fill(P[0], dha, dwa);
ok &= Fill(P[1], dhb, dwb);
ok &= Fill(P[2], dhc, dwc);
for (var i = 0; i < N && ok; i++)
{
for (var j = 0; j < N && ok; j++)
{
ok &= G[i, j] == '#';
}
}
if (ok)
{
Console.WriteLine("Yes");
return;
}
}
}
}
}
}
}
Console.WriteLine("No");
}
問題E
次のような動的計画法を解きます。
dp[i][s] := i番目までの開発案を見たとき、開発案のパラメータ状態がsのときの最小コスト
パラメータ状態はK個のパラメータの値を連結した文字列とすることで管理することができ、パラメータ状態の数は(P+1)^Kであり、1<=K,P<=5であることから最大でも6^5=7776通りになります。
public static void Solve()
{
var (N, K, P) = Scanner.Scan<int, int, int>();
var Plans = new (long C, int[] A)[N];
for (var i = 0; i < N; i++)
{
var array = Scanner.ScanEnumerable<int>().ToArray();
Plans[i] = (array[0], array[1..]);
}
var dp = new Dictionary<string, long>();
const long Inf = 1L << 60;
dp[new string('0', K)] = 0;
var B = new int[K];
for (var i = 0; i < N; i++)
{
var (C, A) = Plans[i];
var ndp = new Dictionary<string, long>();
foreach (var (s, c) in dp)
{
for (var j = 0; j < K; j++)
{
B[j] = A[j];
}
for (var j = 0; j < K; j++)
{
B[j] += s[j] - '0';
B[j] = Math.Min(P, B[j]);
}
var ns = string.Join("", B);
if (!ndp.ContainsKey(s)) ndp[s] = Inf;
ndp[s] = Math.Min(ndp[s], c);
if (!ndp.ContainsKey(ns)) ndp[ns] = Inf;
ndp[ns] = Math.Min(ndp[ns], C + c);
}
dp = ndp;
}
var g = new string((char)(P + '0'), K);
var answer = dp.ContainsKey(g) ? dp[g] : -1;
Console.WriteLine(answer);
}