AtCoder Beginner Contest 162に参加してみました。 atcoder.jp
経緯とか
新型コロナウイルスの影響でいつにも増して引き籠もりがちになり、何か面白いことないかなーと思って目に留まったのが競技プログラミング。
実は競技プログラミングをやったのは初めてではなくて、2013年（7年前！）に一瞬だけTopCoderに参加したことがありました。
その後長らくご無沙汰だったのですが、AtCoderで.NET Core 3.1が使えるようになるらしいという噂が。競プロのコンパイル環境＝バージョンが古いmonoって先入観があったので、最新のC#8.0が使えるなら……と思い興味が出てきました。
コンテストは週1で開催されるようなのですが、気付いたのがちょうど先週のコンテスト終了翌日だったので、1週間過去問を触ったりAtCoder用のプロジェクトテンプレートを整備したりしながら待ち続け、満を持しての初参加となりました。
問題
AtCoder Beginner ContestではA, B, C, D, E, Fの6問が出題され、制限時間100分の中で解けるところまで解いていきます。
標準入力から各ケースごとの入力が与えられ、題意に沿った解答を標準出力に書き込む、というのが大まかな流れです。ちなみに誤答だとペナルティが付きます。
解答やテストが楽になるよう予め以下のようなテンプレートを作っておき、派生クラスのSolve()メソッドで出力文字列を都度yield returnするような形にしてみました。
class Program { // エントリポイント static void Main(string[] args) { // 問題に合わせてクラス名を書き換え IAtCoderQuestion question = new QuestionA(); var answers = question.Solve(Console.In); foreach (var answer in answers) { Console.WriteLine(answer); } } } // なんとなくインターフェース public interface IAtCoderQuestion { IEnumerable<object> Solve(string input); IEnumerable<object> Solve(TextReader inputStream); } public abstract class AtCoderQuestionBase : IAtCoderQuestion { // 単体テスト用 public IEnumerable<object> Solve(string input) { var stream = new MemoryStream(Encoding.Unicode.GetBytes(input)); var reader = new StreamReader(stream, Encoding.Unicode); return Solve(reader); } // 派生クラスでこいつを実装して解答を出力 public abstract IEnumerable<object> Solve(TextReader inputStream); } public class QuestionA : AtCoderQuestionBase { // 解答本体 public override IEnumerable<object> Solve(TextReader inputStream) { yield return "hoge"; yield return "fuga"; } }
A問題 - Lucky 7
問題要約
与えられた3桁の数字に7が含まれるかどうかYes/Noで答えよ。
解答
文字列として受け取ってLINQを使うと楽ですね。
コード中のinputStream.ReadLine()はConsole.ReadLine()と同義です。
public class QuestionA : AtCoderQuestionBase { public override IEnumerable<object> Solve(TextReader inputStream) { yield return inputStream.ReadLine().Any(c => c == '7') ? "Yes" : "No"; } }
B問題 - FizzBuzz Sum
問題要約
FizzBuzz列（1, 2, Fizz, 4, Buzz, Fizz, 7, ...）の項目までのうち、数字のみを足した和を求めよ。
解答
競技プログラミングに興味がなくても、FizzBuzz問題という名前は聞いたことがあるんじゃないでしょうか。3の倍数はFizz、5の倍数はBuzz、3の倍数かつ5の倍数はFizzBuzzにするアレです。
言われた通り素直に実装しますが、int型のオーバーフローに注意です。ご丁寧に入力例にint.MaxValueを超える例が書いてありました。
public class QuestionB : AtCoderQuestionBase { public override IEnumerable<object> Solve(TextReader inputStream) { var n = inputStream.ReadInt(); long sum = 0; for (int i = 1; i <= n; i++) { if (i % 3 != 0 && i % 5 != 0) { sum += i; } } yield return sum; } } // 入力用の拡張メソッドを用意しておくと楽 internal static class TextReaderExtensions { internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader)); internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader)); internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader)); internal static string ReadString(this TextReader reader) => reader.ReadLine(); internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray(); internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray(); internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray(); internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator); }
特に悩むところもない……はずだったのですが、最初ついうっかりfor (int i = 0; i < n; i++)と書いてしまいWA（誤答）。1回間違えるごとに解答時間に5分のペナルティが付くので結構手痛いミス。
xUnitでテストコードを走らせて全ケース正解！ヨシ！と思っていたのですが、範囲系はポカミスしやすいので確認しないとダメですね……という学びを得ました。
C問題 - Sum of gcd of Tuples (Easy)
問題要約
を求めよ。
は
の最大公約数を意味する。
解答
ここで前もって用意しておいたユークリッドの互除法を使います（唐突）。この辺オレオレライブラリを準備してるかしてないかで結構変わってきそうですね……。
愚直に3重ループを書くと計算時間が心配になってきますが、今回はという制約が付いていたので大丈夫でした。
public class QuestionC : AtCoderQuestionBase { public override IEnumerable<object> Solve(TextReader inputStream) { var k = inputStream.ReadInt(); long sum = 0; for (int a = 1; a <= k; a++) { for (int b = 1; b <= k; b++) { for (int c = 1; c <= k; c++) { sum += BasicAlgorithm.Gcd(BasicAlgorithm.Gcd(a, b), c); } } } yield return sum; } } public static class BasicAlgorithm { // ユークリッドの互除法 public static long Gcd(long a, long b) { if (a < b) { (a, b) = (b, a); } while (b != 0) { (a, b) = (b, a % b); } return a; } }
今度はforループの範囲を間違えませんでした。（えらい）
D問題 - RGB Triplets
問題要約
'R', 'G', 'B'のみからなる、長さの文字列
から
の3文字を抜き出す。以下をともに満たす
の数を求めよ。
（
ともに異なる文字）
（3文字が等間隔でない）
解答
愚直に三重ループを回すととなって制限時間（2秒）内に解ききれません。工夫して解きます。
まず2つ目の条件を無視して、1つ目の条件である異なる3文字の選び方を考えると、単純にRの数×Gの数×Bの数で求めることができます。
あとはその数から2つ目の条件の数を引いてあげればOKです。今回は真ん中の文字に着目して、そこから左右等間隔にある文字
が同じ文字だったらカウント、という考え方で出しました。
public class QuestionD : AtCoderQuestionBase { public override IEnumerable<object> Solve(TextReader inputStream) { var n = inputStream.ReadInt(); var s = inputStream.ReadLine(); var rIndex = GetIndexOf(s, 'R'); var gIndex = GetIndexOf(s, 'G'); var bIndex = GetIndexOf(s, 'B'); var all = (long)rIndex.Length * gIndex.Length * bIndex.Length; var sameDistance = 0; sameDistance += GetSameDistanceCount(rIndex, gIndex, bIndex, s.Length); sameDistance += GetSameDistanceCount(gIndex, bIndex, rIndex, s.Length); sameDistance += GetSameDistanceCount(bIndex, rIndex, gIndex, s.Length); yield return all - sameDistance; } Span<int> GetIndexOf(string s, char c) { var list = new List<int>(); for (int i = 0; i < s.Length; i++) { if (s[i] == c) { list.Add(i); } } return list.ToArray().AsSpan(); } int GetSameDistanceCount(Span<int> center, Span<int> indexA, Span<int> indexB, int sLength) { int count = 0; foreach (var centerIndex in center) { var upper = Math.Min(centerIndex, sLength - centerIndex - 1); for (int distance = 1; distance <= upper; distance++) { var small = centerIndex - distance; var large = centerIndex + distance; // 後から考えるとバイナリサーチじゃなくて元の文字列から引っ張ってくればよかった……。 if (indexA.BinarySearch(small) >= 0 && indexB.BinarySearch(large) >= 0) { count++; } else if (indexB.BinarySearch(small) >= 0 && indexA.BinarySearch(large) >= 0) { count++; } } } return count; } }
せっかくC# 8.0が使えるので、なんとなくSpan<T>も使ってみます。今回特にメリットはないですが。
条件2の数え上げの時に無駄にバイナリサーチしちゃいましたが、まあ間に合ったのでよしとします。
ここまで30分+ペナルティ5分。割といいペースだったと思います。
E問題 - Sum of gcd of Tuples (Hard)
問題要約
以上
以下
の整数からなる長さ
の数列
を考える。数列の並べ方は
通りあるが、その全てについての
の和を求めよ。
ただし、答えは非常に大きくなる可能性があるため、和をで割った余りを出力すること。
は
の最大公約数を意味する。
解答
難しかったです。解答時間は70分残ってたんですが解ききれませんでした。
が
となる数列の個数を数え上げて、各
について
とその個数の積を足していってあげれば良いのかな？というところまでは行けたんですが、重複が発生するしどうすれば……素数を数えれば……？（大真面目）とかドツボにハマっちゃってダメでした。
解説を見ると、という数え方ではなく
と上から数えると重複を除去できると書いてあってなるほどなあという感じでした。復習としてその通りに実装してみたところ、思いのほか簡潔なコードに。こんなふうに綺麗に解けると気持ち良いんだろうなあ、と。
public class QuestionE : AtCoderQuestionBase { // 復習 public override IEnumerable<object> Solve(TextReader inputStream) { var (n, k) = inputStream.ReadValue<int, int>(); var patterns = new Modular[k]; // gcd = i-1となる数列の数 Modular total = new Modular(0); for (int i = k; i >= 1; i--) { // 例えばN=10, K=8のとき、最小公倍数が3となるAiは3,6の2通りであり、 // その並べ方は2^N=1024通り。 var pattern = Modular.Pow(new Modular(k / i), n); // 最小公倍数が6のときと被っちゃうので、その分を引く。 for (int j = 2; i * j <= k; j++) { pattern -= patterns[i * j - 1]; } patterns[i - 1] = pattern; var gcd = new Modular(i) * pattern; total += gcd; } yield return total.Value; } } internal static class TextReaderExtensions { // 入力をValueTupleで受け取るやつ internal static (T1, T2) ReadValue<T1, T2>(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); return (v1, v2); } }
あと新しいC#が使えるようになって嬉しいのが、複合型の分解（C# 7.0～）。123 456みたいな入力値の読み取りをvar (n, k) = inputStream.ReadValue<int, int>();みたいに書けるのでだいぶストレスフリーです。
また、「で割った余りを出力」系の問題は真面目にやると面倒なんですが、過去問で出会ったときに作っておいた自作の
Modular構造体を使いました。あれこれ詰め込みすぎて相当長いですが、一応貼っておきます。
public readonly struct Modular : IEquatable<Modular>, IComparable<Modular> { private const int _defaultMod = 1000000007; public int Value { get; } public int Mod { get; } // 配列とかで引数なしコンストラクタが呼ばれると0で初期化されて死ぬ（ガイドライン違反）（int?にすると割り算が2倍遅くなる）（諦め）（運用でカバー） public Modular(long value, int mod = _defaultMod) { if (mod < 2 || mod > 1073741789) { // 1073741789はint.MaxValue / 2 = 1073741823以下の最大の素数 throw new ArgumentOutOfRangeException(nameof(mod), $"{nameof(mod)}は2以上1073741789以下の素数でなければなりません。"); } Mod = mod; if (value >= 0 && value < mod) { Value = (int)value; } else { Value = (int)(value % mod); if (Value < 0) { Value += mod; } } } public static Modular operator +(in Modular a, in Modular b) { CheckModEquals(a, b); var result = a.Value + b.Value; if (result > a.Mod) { result -= a.Mod; // 剰余演算を避ける } return new Modular(result, a.Mod); } public static Modular operator -(in Modular a, in Modular b) { CheckModEquals(a, b); var result = a.Value - b.Value; if (result < 0) { result += a.Mod; // 剰余演算を避ける } return new Modular(result, a.Mod); } public static Modular operator *(in Modular a, in Modular b) { CheckModEquals(a, b); return new Modular((long)a.Value * b.Value, a.Mod); } public static Modular operator /(in Modular a, in Modular b) { CheckModEquals(a, b); return a * Pow(b, a.Mod - 2); } // 需要は不明だけど一応 public static bool operator ==(in Modular left, in Modular right) => left.Equals(right); public static bool operator !=(in Modular left, in Modular right) => !(left == right); public static bool operator <(in Modular left, in Modular right) => left.CompareTo(right) < 0; public static bool operator <=(in Modular left, in Modular right) => left.CompareTo(right) <= 0; public static bool operator >(in Modular left, in Modular right) => left.CompareTo(right) > 0; public static bool operator >=(in Modular left, in Modular right) => left.CompareTo(right) >= 0; public static explicit operator int(in Modular a) => a.Value; public static explicit operator long(in Modular a) => a.Value; public static Modular Pow(in Modular a, int n) { switch (n) { case 0: return new Modular(1, a.Mod); case 1: return a; case int m when m >= 0: // ジャンプテーブル化はできなくなる var p = Pow(a, m >> 1); // m / 2 return p * p * Pow(a, m & 0x01); // m % 2 default: throw new ArgumentOutOfRangeException(nameof(n), $"べき指数{nameof(n)}は0以上の整数でなければなりません。"); } } private static Dictionary<int, List<int>> _factorialCache; private static Dictionary<int, List<int>> FactorialCache => _factorialCache ??= new Dictionary<int, List<int>>(); private static Dictionary<(int, int), List<int>> _permutationCache; private static Dictionary<(int, int), List<int>> PermutationCache => _permutationCache ??= new Dictionary<(int, int), List<int>>(); public static Modular Factorial(int n, int mod = _defaultMod) { if (n < 0) { throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。"); } if (mod < 2) { throw new ArgumentOutOfRangeException(nameof(mod), $"{nameof(mod)}は2以上の素数でなければなりません。"); } if (!FactorialCache.ContainsKey(mod)) { FactorialCache.Add(mod, new List<int>() { 1 }); } var cache = FactorialCache[mod]; for (int i = cache.Count; i <= n; i++) // Countが1（0!までキャッシュ済み）のとき1!～n!まで計算 { cache.Add((int)((long)cache[i - 1] * i % mod)); } return new Modular(cache[n], mod); } public static Modular Permutation(int n, int r, int mod = _defaultMod) { CheckNR(n, r); if (!PermutationCache.ContainsKey((mod, n))) { PermutationCache.Add((mod, n), new List<int>() { 1 }); } var cache = PermutationCache[(mod, n)]; for (int i = cache.Count; i <= r; i++) // Countが1（nP0までキャッシュ済み）のときnP1～nPrまで計算 { cache.Add((int)((long)cache[i - 1] * (n - (i - 1)) % mod)); } return new Modular(cache[r], mod); } public static Modular Combination(int n, int r, int mod = _defaultMod) { CheckNR(n, r); return n == r ? new Modular(1, mod) : Factorial(n, mod) / (Factorial(r, mod) * Factorial(n - r, mod)); } public static Modular[] CreateArray(int length, int mod = _defaultMod) => Enumerable.Repeat(new Modular(0, mod), length).ToArray(); private static void CheckModEquals(in Modular a, in Modular b) { if (a.Mod != b.Mod) { throw new ArgumentException($"{nameof(a)}, {nameof(b)}", $"両者の法{nameof(Mod)}は等しくなければなりません。"); } } private static void CheckNR(int n, int r) { if (n <= 0) { throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は正の整数でなければなりません。"); } if (r < 0) { throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。"); } if (n < r) { throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。"); } } public override string ToString() => $"{Value} (mod {Mod})"; public override bool Equals(object obj) => obj is Modular m ? Equals(m) : false; public bool Equals([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value == other.Value && Mod == other.Mod; public int CompareTo([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) { CheckModEquals(this, other); return Value.CompareTo(other.Value); } public override int GetHashCode() => (Value, Mod).GetHashCode(); }
F問題 - Select Half
読んですらいません。
結果
初参加にしては上出来だったと思います。D問題まであまり詰まらずにスムーズに解けたのが要因かなと。とはいえ上を目指していくならE問題も解けるようにならなきゃなあ……といったところ。
過去問埋めをやっているんですが、D問題とE問題の間に大きな壁を感じるのでもっと精進が必要そうです。
今回はたまたまビギナーズラックだったような気がするので、コンスタントにこれ以上の成績を出し続けられるようにしていきたいですね。
長くなりましたが、AtCoder、とても面白いです。こういったパズル的なものを解くのは久し振りなのですが、解けたときの脳内麻薬分泌はすごいですね。
最新のC#が使えるようになって1ストレスフリーに書けるので、C#erの皆さんはどしどし参加していくと楽しいと思います。ぼくも頑張ります。
-
過去問は現時点で未対応みたいでちょっと残念。↩
