はじめに
AtCoder Beginner Contest 326の復習記事です。
記事における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/abc326
問題A
階層の差がd階のとき、下に3階分は-3<=d、上に2階分はd<=2となるので、-3<=d<=2の場合に答えはYesになります。
例
public static void Solve()
{
var (X, Y) = Scanner.Scan<int, int>();
var d = Y - X;
var answer = -3 <= d && d <= 2;
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
N以上の整数xを全探索し、xの百の位をa、十の位をb、一の位をcとしたとき、a*b==cになるかを判定します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
for (var x = N; x <= 999; x++)
{
var a = x / 100;
var b = x / 10 % 10;
var c = x % 10;
if (a * b == c)
{
Console.WriteLine(x);
return;
}
}
}
問題C
Aをソートし、lを固定したとき、A[r]>=A[l]+Mとなるrを求めることで、座標A[l]を半開区間の左端としたときにr-l個のプレゼントを選ぶことができるようになります。
Aのソートに時間計算量O(NlogN)、rを尺取り法で求めることで時間計算量O(N)で答えを求めることができます。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
Array.Sort(A);
var answer = 0;
var r = 0;
for (var l = 0; l < N; l++)
{
while (r < N && A[r] < A[l] + M) r++;
answer = Math.Max(answer, r - l);
}
Console.WriteLine(answer);
}
問題D
条件1から、Aが各行/各列にちょうど1つのみ含まれるパターンは5!通りであり、同様にBとCも5!通りになります。
5!^3通りパターンを全探索し、条件の2と3を満たすかを判定します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var R = Scanner.Scan<string>();
var C = Scanner.Scan<string>();
var G = new char[N, N];
bool CheckR()
{
var result = true;
for (var i = 0; i < N && result; i++)
{
for (var j = 0; j < N && result; j++)
{
if (G[i, j] != '.')
{
result &= G[i, j] == R[i];
break;
}
}
}
return result;
}
bool CheckC()
{
var result = true;
for (var j = 0; j < N && result; j++)
{
for (var i = 0; i < N && result; i++)
{
if (G[i, j] != '.')
{
result &= G[i, j] == C[j];
break;
}
}
}
return result;
}
foreach (var AI in Permutation.GeneratePermutation(N))
{
foreach (var BI in Permutation.GeneratePermutation(N))
{
foreach (var CI in Permutation.GeneratePermutation(N))
{
var ok = true;
for (var i = 0; i < N && ok; i++)
{
ok &= AI[i] != BI[i];
ok &= AI[i] != CI[i];
ok &= BI[i] != CI[i];
}
if (!ok) continue;
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
G[i, j] = '.';
}
}
for (var i = 0; i < N; i++)
{
G[AI[i], i] = 'A';
G[BI[i], i] = 'B';
G[CI[i], i] = 'C';
}
if (CheckR() && CheckC())
{
Console.WriteLine("Yes");
Printer.Print2D(G);
return;
}
}
}
}
Console.WriteLine("No");
}
問題E
A[i]が支給される確率をP[i]、期待値をE[i]としたとき、E[i]=A[i]*P[i]となります。
あるyについてP[y]の確率は、x<yとなるP[x]から1/Nの確率で推移することから、cumP[y-1]=P[0]+P[1]+...+P[y-1]としたとき、P[y]=cumP[y-1]/Nとして求めることができます。
よって、各iについて累積の確率を管理しながら期待値を求めることで、時間計算量O(N)で答えを求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var iN = mint.Inverse(N);
var E = new mint[N + 1];
var P = new mint[N + 1];
var cumP = new mint[N + 1];
P[0] = cumP[0] = 1;
for (var i = 1; i <= N; i++)
{
P[i] = cumP[i - 1] * iN;
E[i] = A[i - 1] * P[i];
cumP[i] = cumP[i - 1] + P[i];
}
mint answer = 0;
for (var i = 1; i <= N; i++)
{
answer += E[i];
}
Console.WriteLine(answer);
}