はじめに
AtCoder Beginner Contest 324の復習記事です。
記事における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/abc324
問題A
Aから重複をなくしたものの要素の個数が1であるかどうかを判定します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var answer = A.Distinct().Count() == 1;
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
N==(2^x)*(3^x)であることは、N/((2^x)*(3^x))==1であることと同値であるため、Nを2と3で割れるだけ割ったものが1であるかを判定します。
public static void Solve()
{
var N = Scanner.Scan<long>();
while (N > 1 && N % 2 == 0) N /= 2;
while (N > 1 && N % 3 == 0) N /= 3;
var answer = N == 1;
Console.WriteLine(answer ? "Yes" : "No");
}
問題C
あるSはT'と等しいか、(挿入|削除|変更)により1文字違いである必要があります。
これにより、||S| - |T|| <= 1である必要があります。
そして、SとT'の差分が1または0である、つまり差分が1以下であれば、Sは条件を満たすことがわかります。
これは次のようなアルゴリズムで判定することができます。
siをSのsi文字目、tiをTのti文字目、diffを現在見ている文字までの差分とする。
- S[si] == T[ti] の場合、
siを1増やす。
tiを1増やす。
- S[si] != T[ti] の場合、
- diffが0の場合、
diffを1増やす。
- |S| > |T|の場合、(SはTに1文字追加したものの可能性)
siを1増やす。
- |S| < |T|の場合、(SはTから1文字削除したものの可能性)
tiを1増やす。
- |S| == |T|の場合、(SはTから1文字変更したものの可能性)
siを1増やす。
tiを1増やす。
- diffが1以上の場合
Sは条件を満たさない
全てのsiとtiを見たとき、diffが1以下であればSは条件を満たす。
public static void Solve()
{
var (N, T) = Scanner.Scan<int, string>();
var answers = new List<int>();
for (var i = 0; i < N; i++)
{
var S = Scanner.Scan<string>();
if (Math.Abs(S.Length - T.Length) > 1) continue;
var si = 0;
var ti = 0;
var diff = 0;
var ok = true;
while (si < S.Length && ti < T.Length && ok)
{
if (S[si] == T[ti]) { si++; ti++; }
else
{
diff++;
if (S.Length < T.Length) { ti++; }
else if (S.Length > T.Length) { si++; }
else { si++; ti++; }
}
ok = diff <= 1;
}
if (ok) answers.Add(i + 1);
}
Console.WriteLine(answers.Count);
if (answers.Count == 0) Console.WriteLine();
else Console.WriteLine(string.Join(" ", answers));
}
問題D
N桁以下の平方数を列挙し、各平方数の桁の数字の個数がSの桁の数字の個数と一致するかを判定します。
N桁以下の平方数は、Sqrt(10^13)程度なので、十分高速に求めることができます。
また、0の個数に関しては、平方数に対して0埋めすることが可能なので、Sの0の個数以下であれば条件を満たします。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var CS = new int[10];
foreach (var c in S.Select(x => x - '0')) CS[c]++;
var MAX = (long)1e13;
var sqrs = new List<long>();
long v = 0;
while (v * v <= MAX)
{
sqrs.Add(v * v);
v++;
}
long answer = 0;
foreach (var x in sqrs)
{
var CT = new int[10];
var y = x;
while (y > 0)
{
CT[(int)(y % 10)]++;
y /= 10;
}
var ok = true;
for (var i = 0; i < 10 && ok; i++)
{
if (i == 0)
{
ok &= CS[i] >= CT[i];
}
else
{
ok &= CS[i] == CT[i];
}
}
if (ok) answer++;
}
Console.WriteLine(answer);
}
問題E
A[i]をi番目の文字列を先頭から見たときのTの部分列として一致している長さ、B[i]をi番目の文字列を末尾から見たときのTの部分列として一致している長さとしたとき、A[i]+B[j]>=|T|が成り立つi,jが条件を満たします。
これは、あらかじめAとBを計算しておき、各Aに対してソートしたBを二部探索することで、時間計算量O(|S| + NlogN)で求めることができます。
public static void Solve()
{
var (N, T) = Scanner.Scan<int, string>();
var S = new string[N];
for (var i = 0; i < N; i++)
{
S[i] = Scanner.Scan<string>();
}
var A = new int[N];
var B = new int[N];
for (var i = 0; i < N; i++)
{
var a = 0;
var b = 0;
for (var j = 0; j < S[i].Length; j++)
{
if (a < T.Length && S[i][j] == T[a]) a++;
if (b < T.Length && S[i][^(j + 1)] == T[^(b + 1)]) b++;
}
A[i] = a;
B[i] = b;
}
Array.Sort(B);
long answer = 0;
for (var i = 0; i < N; i++)
{
var lb = LowerBound(B, T.Length - A[i]);
answer += N - lb;
}
Console.WriteLine(answer);
}