はじめに
AtCoder Beginner Contest 349の復習記事です。
記事における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/abc349
問題A
総和は0になるので、0-Aの総和が答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var answer = -A.Sum();
Console.WriteLine(answer);
}
問題B
文字ごとに出現数を数え上げ、全ての出現数において、その種類数が0か2であるかを判定します。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var count = new int[26];
foreach (var c in S)
{
count[c - 'a']++;
}
var dict = new Dictionary<int, int>();
for (var i = 0; i < 26; i++)
{
if (count[i] == 0) continue;
if (!dict.ContainsKey(count[i])) dict[count[i]] = 0;
dict[count[i]]++;
}
var answer = dict.Values.All(x => x == 0 || x == 2);
Console.WriteLine(answer ? "Yes" : "No");
}
問題C
Sを左から順にみて、Tのk番目の小文字が出現したかを判定します。
Sの末尾にxを追加したものをSとして考えることで、末尾にXを追加したものを判定することができます。
例
public static void Solve()
{
var S = Scanner.Scan<string>() + "x";
var T = Scanner.Scan<string>().ToLower();
var k = 0;
foreach (var c in S)
{
if (k >= 3) break;
if (T[k] == c) k++;
}
var answer = k == 3;
Console.WriteLine(answer ? "Yes" : "No");
}
問題D
r%b==0かつl=(r/b-1)*b>=Lとなる最大の2のべき乗bをrの大きい順に求めることで達成できます。
各数列において、bは最大60回程度で求めることができます。
例
public static void Solve()
{
var (L, R) = Scanner.Scan<long, long>();
var answers = new List<(long L, long R)>();
while (R > L)
{
long b = 1L << 60;
var l = (R / b - 1) * b;
while (R % b != 0 || l < L)
{
b >>= 1;
l = (R / b - 1) * b;
}
answers.Add((l, R));
R = l;
}
Console.WriteLine(answers.Count);
answers.Reverse();
foreach (var (l, r) in answers)
{
Console.WriteLine($"{l} {r}");
}
}