はじめに
AtCoder Beginner Contest 312の復習記事です。
記事における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/abc312
問題A
Sが候補となる文字列に存在するかを判定します。
一つ一つ判定しても答えを求めることができますが、あらかじめ候補となる文字列を配列などで管理しておき、存在判定することでも答えを求めることができます。
public static void Solve()
{
var OK = new string[] { "ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD" };
var S = Scanner.Scan<string>();
var answer = OK.Contains(S);
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
グリッドから9*9の領域を全探索し、それぞれが条件を満たすかを判定します。
条件判定をそれぞれメソッドとして切り出すことで、読みやすくすることができます。
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();
}
bool CheckBlack(int h, int w)
{
var result = true;
for (var i = 0; i < 3 && result; i++)
{
for (var j = 0; j < 3 && result; j++)
{
result &= G[h + i][w + j];
result &= G[h + 6 + i][w + 6 + j];
}
}
return result;
}
bool CheckWhite(int h, int w)
{
var result = true;
for (var i = 0; i < 3 && result; i++)
{
result &= !G[h + i][w + 3];
result &= !G[h + 3][w + i];
result &= !G[h + 6 + i][w + 6 - 1];
result &= !G[h + 6 - 1][w + 6 + i];
}
result &= !G[h + 3][w + 3];
result &= !G[h + 6 - 1][w + 6 - 1];
return result;
}
for (var i = 0; i + 9 <= N; i++)
{
for (var j = 0; j + 9 <= M; j++)
{
if (CheckBlack(i, j) && CheckWhite(i, j))
{
Console.WriteLine($"{i + 1} {j + 1}");
}
}
}
}
問題C
次のようなxを二部探索します。
りんごをx円で売ってもよいと考える売り手の人数が、りんごをx円で買ってもよいと考える買い手の人数以上である。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var B = Scanner.ScanEnumerable<int>().ToArray();
bool F(long x)
{
var a = A.Count(v => x >= v);
var b = B.Count(v => x <= v);
return a >= b;
}
const long Inf = (long)1e18;
var answer = BinarySearch(0, Inf, F);
Console.WriteLine(answer);
}
public static long BinarySearch(long ng, long ok, Func<long, bool> func)
{
while (Math.Abs(ok - ng) > 1)
{
var m = (ok + ng) / 2;
if (func(m)) ok = m;
else ng = m;
}
return ok;
}
問題D
次のような動的計画法を解きます。
括弧列のレベルを、それまでの`(`の出現数から`)`の出現数を引いたものとしたとき、
dp[i,j] := i番目の文字まで見たとき、現在の括弧列のレベルがjとしてありえる文字列の数
遷移は次のようになります。
S[i]が`(`のとき、
dp[i+1,j+1] += dp[i,j] (0<=j<N)
S[i]が`)`のとき、
dp[i+1,j-1] += dp[i,j] (0<j<=N)
S[i]が`?`のとき、
dp[i+1,j+1] += dp[i,j] (0<=j<N)
dp[i+1,j-1] += dp[i,j] (0<j<=N)
N文字目までみたときの括弧列のレベルが0となるものの数が答えとなります。
括弧列のレベルが0未満になる場合、その文字列は括弧列として成り立たないことに注意が必要です。
public static void Solve()
{
var S = Scanner.Scan<string>();
var N = S.Length;
var dp = new mint[N + 1, N + 1];
dp[0, 0] = 1;
for (var i = 0; i < N; i++)
{
var c = S[i];
if (c == '(' || c == '?')
{
for (var j = 0; j < N; j++)
{
dp[i + 1, j + 1] += dp[i, j];
}
}
if (c == ')' || c == '?')
{
for (var j = 1; j <= N; j++)
{
dp[i + 1, j - 1] += dp[i, j];
}
}
}
var answer = dp[N, 0];
Console.WriteLine(answer);
}
問題E
3次元空間をグリッドとしてみたとき、各直方体がどのグリッドを占有しているかを管理し、各直方体のグリッドが面する直方体の種類数を数え上げます。
与えられる線分の座標は開区間であり、座標を開区間のまま管理すると面が重複してしまうことがあるため、半開区間に変換する必要があります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new int[105, 105, 105];
var P = new (int X1, int Y1, int Z1, int X2, int Y2, int Z2)[N];
for (var i = 0; i < N; i++)
{
var (x1, y1, z1, x2, y2, z2) = Scanner.Scan<int, int, int, int, int, int>();
x1++; y1++; z1++;
P[i] = (x1, y1, z1, x2, y2, z2);
for (var x = x1; x <= x2; x++)
{
for (var y = y1; y <= y2; y++)
{
for (var z = z1; z <= z2; z++)
{
G[x, y, z] = i + 1;
}
}
}
}
foreach (var (x1, y1, z1, x2, y2, z2) in P)
{
var set = new HashSet<int>();
for (var x = x1; x <= x2; x++)
{
for (var y = y1; y <= y2; y++)
{
for (var z = z1; z <= z2; z++)
{
set.Add(G[x1 - 1, y, z]);
set.Add(G[x2 + 1, y, z]);
set.Add(G[x, y1 - 1, z]);
set.Add(G[x, y2 + 1, z]);
set.Add(G[x, y, z1 - 1]);
set.Add(G[x, y, z2 + 1]);
}
}
}
set.Remove(0);
Console.WriteLine(set.Count);
}
}
問題F
M個の品物のうち、缶切りが不要な缶をx個として固定したとき、缶切りが必要な缶と缶切りをM-x個選んだ時の満足度の最大値を求めます。
缶切りが不要な缶と缶切りが必要な缶は、いずれも満足度が大きいものから選ぶことが最適になります。
また、缶切りは使用できる缶の数が多い物から順に使うことが最適になります。
これにより、あらかじめ、缶切りが不要な缶をa個選んだ時の満足度の累積和と、缶切りが必要な缶と缶切りを合わせてb個選んだ時の満足度の累積和を求めておくことで、時間計算量O(M)で満足度の最大値を求めることができます。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var cans0 = new List<long>();
var cans1 = new List<long>();
var openers = new List<int>();
for (var i = 0; i < N; i++)
{
var (T, X) = Scanner.Scan<int, int>();
if (T == 0)
{
cans0.Add(X);
}
else if (T == 1)
{
cans1.Add(X);
}
else
{
openers.Add(X);
}
}
cans0.Sort();
cans0.Reverse();
cans1.Sort();
cans1.Reverse();
openers.Sort();
openers.Reverse();
var N0 = cans0.Count;
var N1 = cans1.Count;
var N2 = openers.Count;
var cum0 = new long[M + 1];
for (var i = 0; i < M; i++)
{
cum0[i + 1] = cum0[i];
if (i < N0) cum0[i + 1] += cans0[i];
}
var cum1 = new long[M + 1];
{
var i = 0;
var j = 0;
var rem = 0;
for (var k = 0; k < M; k++)
{
cum1[k + 1] += cum1[k];
if (rem > 0 && i < N1)
{
cum1[k + 1] += cans1[i++];
rem--;
}
else if (j < N2)
{
rem = openers[j++];
}
}
}
long answer = 0;
for (var i = 0; i <= M; i++)
{
answer = Math.Max(answer, cum0[i] + cum1[M - i]);
}
Console.WriteLine(answer);
}