はじめに
AtCoder Beginner Contest 345の復習記事です。
記事における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/abc345
問題A
Sの先頭が<、末尾が>、それ以外が=であるかを判定します。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var answer = S[0] == '<' && S[^1] == '>';
for (var i = 1; i < S.Length - 1; i++)
{
answer &= S[i] == '=';
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
Xが正の整数である場合は、(X+10-1)/10を計算することで、切り上げた値を得ることができます。
一方、Xが負の整数である場合は、切り上げは0に近づける処理になるので、符号を正にした値を切り捨てた値の符号を負にすればいいので、-(-X/10)で求めることができます。
例
public static void Solve()
{
var X = Scanner.Scan<long>();
var answer = X > 0 ? (X + 9) / 10 : -(-X / 10);
Console.WriteLine(answer);
}
問題C
文字ごとに出現数を数え上げ、count[c]を現在見ている箇所より右側に出現する文字cの数とします。
同じ文字が複数出現する場合は、それらの位置を入れ替えたものは元の文字から変わらないので、答えを+1します。
i番目の文字とi<jとなるj番目の文字を入れ替えたとき、元の文字列とは異なる文字列になる組み合わせは、i番目の文字列と異なる文字の数になります。
これは、iを0-indexedにすると、N-i-count[c]通りになり、count[c]を1減らすという操作を全てのiにおいて計算することで、答えを求めることができます。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var N = S.Length;
var count = new long[26];
foreach (var c in S)
{
count[c - 'a']++;
}
long answer = 0;
if (count.Any(x => x > 1)) answer++;
for (var i = 0; i < N; i++)
{
var c = S[i] - 'a';
answer += N - i - count[c];
count[c]--;
}
Console.WriteLine(answer);
}
問題D
あり得る配置数を枝刈りを工夫して全探索を行います。
例
public static void Solve()
{
var (N, H, W) = Scanner.Scan<int, int, int>();
var T = new (int A, int B)[N];
for (var i = 0; i < N; i++)
{
var (a, b) = Scanner.Scan<int, int>();
T[i] = (a, b);
}
var G = new bool[H, W];
bool Dfs((int A, int B)[] tiles, int k)
{
var result = true;
for (var i = 0; i < H && result; i++)
{
for (var j = 0; j < W && result; j++)
{
result &= G[i, j];
}
}
if (k >= N || result) return result;
if (Dfs(tiles, k + 1)) return true;
var (a, b) = tiles[k];
for (var t = 0; t < 2; t++)
{
var end = false;
for (var h = 0; h + a <= H && !end; h++)
{
for (var w = 0; w + b <= W && !end; w++)
{
if (G[h, w]) continue;
var ok = true;
for (var i = 0; i < a && ok; i++)
{
for (var j = 0; j < b && ok; j++)
{
ok &= !G[h + i, w + j];
}
}
if (!ok) continue;
for (var i = 0; i < a; i++)
{
for (var j = 0; j < b; j++)
{
G[h + i, w + j] = true;
}
}
if (Dfs(tiles, k + 1)) return true;
for (var i = 0; i < a; i++)
{
for (var j = 0; j < b; j++)
{
G[h + i, w + j] = false;
}
}
end = true;
}
}
if (a == b) break;
(a, b) = (b, a);
}
return false;
}
var tiles = new (int A, int B)[N];
foreach (var order in Permutation.Generate(N))
{
for (var i = 0; i < N; i++)
{
tiles[i] = T[order[i]];
}
if (Dfs(tiles, 0))
{
Console.WriteLine("Yes");
return;
}
}
Console.WriteLine("No");
}
public static class Permutation
{
public static bool NextPermutation(Span<int> indices)
{
var n = indices.Length;
var (i, j) = (n - 2, n - 1);
while (i >= 0 && indices[i] >= indices[i + 1]) i--;
if (i == -1) return false;
while (j > i && indices[j] <= indices[i]) j--;
(indices[i], indices[j]) = (indices[j], indices[i]);
indices[(i + 1)..].Reverse();
return true;
}
public static bool PreviousPermutation(Span<int> indices)
{
var n = indices.Length;
var (i, j) = (n - 2, n - 1);
while (i >= 0 && indices[i] <= indices[i + 1]) i--;
if (i == -1) return false;
indices[(i + 1)..].Reverse();
while (j > i && indices[j - 1] < indices[i]) j--;
(indices[i], indices[j]) = (indices[j], indices[i]);
return true;
}
public static IEnumerable<IReadOnlyList<int>> Generate(int n)
{
return Inner();
IEnumerable<IReadOnlyList<int>> Inner()
{
var indices = new int[n];
for (var i = 0; i < indices.Length; i++) indices[i] = i;
do { yield return indices; } while (NextPermutation(indices));
}
}
public static IEnumerable<IReadOnlyList<int>> GenerateDescending(int n)
{
return Inner();
IEnumerable<IReadOnlyList<int>> Inner()
{
var indices = new int[n];
for (var i = 0; i < indices.Length; i++) indices[i] = n - 1 - i;
do { yield return indices; } while (PreviousPermutation(indices));
}
}
}