はじめに
AtCoder Beginner Contest 319の復習記事です。
記事における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/abc319
問題A
名前をキーとして辞書を作成し、対応するレートを出力します。
public static void Solve()
{
var T = @"tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481";
var dict = new Dictionary<string, string>();
foreach (var line in T.Replace("\r", string.Empty).Split('\n'))
{
var array = line.Split(' ');
dict[array[0]] = array[1];
}
var S = Scanner.Scan<string>();
var answer = dict[S];
Console.WriteLine(answer);
}
問題B
各i (0<=i<=N)について、条件を満たすj (1<=j<=9)を全探索します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = new char[N + 1];
Array.Fill(S, '-');
for (var i = 0; i <= N; i++)
{
for (var j = 1; j <= 9; j++)
{
if (N % j == 0 && i % (N / j) == 0)
{
S[i] = (char)(j + '0');
break;
}
}
}
var answer = new string(S);
Console.WriteLine(answer);
}
問題C
h行目w列目(0<=h,w<=2)のマス番号をh*3+wとします。
高橋君が知るマス番号の順列について、9!(362880)通りの全探索を行い、各マス番号の順列について、次の数字を管理しながらがっかりするものかどうかを判定します。
h行目の知った数字w列目の知った数字- 左上から右下にかけての斜めの知った数字
- 右上から左下にかけての斜めの知った数字
(9! - がっかりしたマス番号の順列の個数) / 9!が答えとなります。
public static void Solve()
{
var C = new int[3][];
for (var i = 0; i < 3; i++)
{
C[i] = Scanner.ScanEnumerable<int>().ToArray();
}
(int, int) F(int x) => (x / 3, x % 3);
var all = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
var p = all;
var tate = new List<int>[3].Select(_ => new List<int>(3)).ToArray();
var yoko = new List<int>[3].Select(_ => new List<int>(3)).ToArray();
var naname1 = new List<int>();
var naname2 = new List<int>();
foreach (var items in Enumerable.Range(0, 9).Permute())
{
for (var i = 0; i < 3; i++)
{
yoko[i].Clear();
tate[i].Clear();
}
naname1.Clear();
naname2.Clear();
var ng = false;
for (var i = 0; i < 9 && !ng; i++)
{
var (h, w) = F(items[i]);
var v = C[h][w];
yoko[h].Add(v);
tate[w].Add(v);
if (h - w == 0) naname1.Add(v);
if (h + w == 2) naname2.Add(v);
ng |= yoko[h].Count == 3 && yoko[h][0] == yoko[h][1] && yoko[h][0] != yoko[h][2];
ng |= tate[w].Count == 3 && tate[w][0] == tate[w][1] && tate[w][0] != tate[w][2];
ng |= naname1.Count == 3 && naname1[0] == naname1[1] && naname1[0] != naname1[2];
ng |= naname2.Count == 3 && naname2[0] == naname2[1] && naname2[0] != naname2[2];
}
if (ng) p--;
}
var answer = (double)p / all;
Console.WriteLine(answer);
}
public static partial class EnumerableExtension
{
public static IEnumerable<T[]> Permute<T>(this IEnumerable<T> source)
{
if (source is null) throw new ArgumentNullException(nameof(source));
IEnumerable<T[]> Inner()
{
var items = source.ToArray();
var n = items.Length;
var indices = new int[n];
for (var i = 0; i < indices.Length; i++)
{
indices[i] = i;
}
T[] Result()
{
var result = new T[n];
for (var i = 0; i < n; i++)
{
result[i] = items[indices[i]];
}
return result;
}
yield return Result();
while (true)
{
var (i, j) = (n - 2, n - 1);
while (i >= 0)
{
if (indices[i] < indices[i + 1]) break;
i--;
}
if (i == -1) yield break;
while (true)
{
if (indices[j] > indices[i]) break;
j--;
}
(indices[i], indices[j]) = (indices[j], indices[i]);
Array.Reverse(indices, i + 1, n - 1 - i);
yield return Result();
}
}
return Inner();
}
}
問題D
幅をWとしたときに文章がM行以内に収まるという判定式で、答えとなるWを[Max(L), Sum(L)+N-1)で二部探索します。
判定式では、L[i]を順に見ていき、
- 現在見ている行の文字数が
0の場合、行の始まりなので文字数にL[i]を足します。 - 現在見ている行の文字数が
0より大きい場合、かつ空白と単語を追加できる場合、文字数に1+L[i]を足します。 - 現在見ている行の文字数が
0より大きい場合、かつ空白と単語を追加できない場合、行数を追加し文字数をL[i]にします。
全てのiを見たとき、行数がM以内であるかを判定します。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var L = Scanner.ScanEnumerable<long>().ToArray();
var min = L.Max();
var max = L.Sum() + N - 1;
bool F(long x)
{
var line = 1;
long cum = 0;
for (var i = 0; i < N; i++)
{
if (cum == 0)
{
cum += L[i];
}
else
{
if (cum + 1 + L[i] <= x)
{
cum += 1 + L[i];
}
else
{
cum = L[i];
line++;
}
}
}
return line <= M;
}
var answer = BinarySearch(min - 1, max, 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;
}
問題E
各バスについてP[i]の周期があることから、全体でLcm(P)の周期があることがわかります。
そのため、高橋君の家から出発する時間をそれぞれ0,1,...,Lcm(P)-1としたとき、青木君の家までかかる時間の累積和を時間計算量O(Lcm*N)であらかじめ計算しておくことで、各クエリに対して時間計算量O(1)で答えを求めることができるようになります。
public static void Solve()
{
var (N, X, Y) = Scanner.Scan<int, long, long>();
var P = new int[N - 1];
var T = new long[N - 1];
long lcm = 1;
for (var i = 0; i < N - 1; i++)
{
var (p, t) = Scanner.Scan<int, long>();
P[i] = p;
T[i] = t;
lcm = Lcm(lcm, p);
}
var cum = new long[lcm];
for (var l = 0; l < lcm; l++)
{
cum[l] = l + X;
for (var i = 0; i + 1 < N; i++)
{
cum[l] = (cum[l] + P[i] - 1) / P[i] * P[i] + T[i];
}
cum[l] += Y;
}
var Q = Scanner.Scan<int>();
while (Q-- > 0)
{
var q = Scanner.Scan<int>();
var answer = q / lcm * lcm + cum[q % lcm];
Console.WriteLine(answer);
}
}
public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
public static long Lcm(long a, long b) => a / Gcd(a, b) * b;