はじめに
drkenさんのAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～で紹介されていた問題をC#で解いてみました。
AtCoder Beginners Selection コンテストページ
なお、こちらのAtCoderに登録したら解くべき精選過去問10問をRustで解いてみたの二番煎じとなっております。
私は、競技プログラミングは好きなのですが得意ではなく、簡潔なコードで実装していないかもしれません。
"こうした方がいい"という点がありましたら指摘していただけると嬉しいです。
また、本記事中のコードは、以下に記述するコードのSolve関数の部分のみ記載します。
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
namespace AtCoder
{
public class Program
{
public static void Main(string[] args)
{
new Program().Solve(new ConsoleInput(Console.In, ' '));
}
public void Solve(ConsoleInput cin)
{
// 解答はココに書く
}
}
public class ConsoleInput
{
private readonly System.IO.TextReader _stream;
private char _separator = ' ';
private Queue<string> inputStream;
public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
{
this._separator = separator;
this._stream = stream;
inputStream = new Queue<string>();
}
public string Read
{
get
{
if (inputStream.Count != 0) return inputStream.Dequeue();
string[] tmp = _stream.ReadLine().Split(_separator);
for (int i = 0; i < tmp.Length; ++i)
inputStream.Enqueue(tmp[i]);
return inputStream.Dequeue();
}
}
public string ReadLine { get { return _stream.ReadLine(); }}
public int ReadInt { get { return int.Parse(Read); }}
public long ReadLong { get { return long.Parse(Read); }}
public double ReadDouble { get { return double.Parse(Read); }}
public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
}
}
問題と提出コード
0問目 PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）
3つの整数値と文字列を1つ受け取り、整数値の和と文字列を一行に出力する問題です。
C#では、変数の型をvarとすることで、静的に型が決まります。
また、出力のフォーマット指定は$文字を用いて行います。
public void Solve(ConsoleInput cin)
{
var a = cin.ReadInt;
var b = cin.ReadInt;
var c = cin.ReadInt;
var s = cin.Read;
WriteLine($"{a + b + c} {s}");
}
1問目 ABC086A - Product
2つの整数値を受け取り、その積が2の倍数かを判定する問題です。
三項演算子を用いてこのように書けます。
public void Solve(ConsoleInput cin)
{
var a = cin.ReadInt;
var b = cin.ReadInt;
WriteLine(a * b % 2 == 0 ? "Even" : "Odd");
}
2問目 ABC081A - Placing Marbles
文字列を受け取り、1の個数をカウントする問題です。
LINQを用いてこのように書くことが出来ます。LINQについてはこちらの記事がおすすめです。はじめてのLINQ
簡単に説明すると、文字列を1文字ずつに分割した配列から、'1'であるものだけを残し、その個数を数えています。
public void Solve(ConsoleInput cin)
{
var s = cin.Read;
WriteLine(s.Count(x => x == '1'));
}
3問目 ABC081B - Shift only
N個の整数値を受け取り、一度の操作ですべての数を2で割る。割り切れなくなるまで割っていった時、何回割ることが出来るか？
整数値を２進数で表したとき、右から何個0が続いているか？を調べることで、その数を何回2で割り切ることが出来るか？が分かります。
public void Solve(ConsoleInput cin)
{
var min = 30; // 今回はceil(log2(最大値))なら何でもいいです
var N = cin.ReadInt;
for (int i = 0; i < N; ++i)
{
var A = cin.ReadInt;
var c = 0;
while (A % 2 == 0 && A != 0) { A >>= 1; ++c; }
min = Min(min, c);
}
WriteLine(min);
}
ちなみにLINQを使って次のように書くことも出来ます。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
var ans = cin.ReadIntArray(N).Min(x => {
var c = 0;
while (x % 2 == 0 && x != 0) { x >>= 1; ++c; }
return c;
});
WriteLine(ans);
}
4問目 ABC087B - Coins
500円玉をA枚、100円玉をB枚、50円玉をC枚持っているとき、これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする組み合わせを求める問題です。
これは、多重ループを用いて解くことができます。
public void Solve(ConsoleInput cin)
{
var A = cin.ReadInt;
var B = cin.ReadInt;
var C = cin.ReadInt;
var X = cin.ReadInt;
var ans = 0;
for (int i = 0; i <= A; ++i)
for (int j = 0; j <= B; ++j)
for (int k = 0; k <= C; ++k)
if (500 * i + 100 * j + 50 * k == X)
ans++;
WriteLine(ans);
}
LINQのSelectMany関数を用いて、A,B,Cの組合せを列挙して解くことは出来ますが、ゴチャゴチャしてしまってあまり好きではありません。
public void Solve(ConsoleInput cin)
{
var A = Enumerable.Range(0, cin.ReadInt + 1);
var B = Enumerable.Range(0, cin.ReadInt + 1);
var C = Enumerable.Range(0, cin.ReadInt + 1);
var X = cin.ReadInt;
var ans = A.SelectMany(_ => B, (a, b) => 500 * a + 100 * b).SelectMany(_ => C, (s, c) => s + 50 * c).Count(x => x == X);
WriteLine(ans);
}
5問目 ABC083B - Some Sums
1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求める問題です。
これは、1~Nまでの整数を一度文字列に変換し、各桁を足し合わせると簡単に求めることが可能です。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
var A = cin.ReadInt;
var B = cin.ReadInt;
var ans = 0;
for (int i = 1; i <= N; ++i)
{
var sum = 0;
foreach (var c in i.ToString())
sum += (int)(c - '0');
if (A <= sum && sum <= B)
ans += i;
}
WriteLine(ans);
}
LINQを用いるとこのように書けます。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
var A = cin.ReadInt;
var B = cin.ReadInt;
var ans = Enumerable.Range(1, N).Where(n => {
var sum = n.ToString().Sum(c => (int)(c - '0'));
return A <= sum && sum <= B;
}).Sum();
WriteLine(ans);
}
6問目 ABC088B - Card Game for Two
N枚のカードを二人で交互に取っていき、カードに書かれている数字の和の差を求める問題。
カードを降順ソート(大きい順に並べ替え)をして、交互に数字を足していけば良いです。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
var a = cin.ReadIntArray(N);
Array.Sort(a); Array.Reverse(a); // Array.Sortは昇順ソートを行います
var alice = 0;
var bob = 0;
for (int i = 0; i < N; ++i)
{
if (i % 2 == 0) alice += a[i];
else bob += a[i];
}
WriteLine(alice - bob);
}
7問目 ABC085B - Kagami Mochi
N枚の整数値が与えられ、それらの重複しない要素の数を数える問題です。
このような場合にはHashSet(集合)のデータ構造を用いると簡単に求めることが出来ます。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
var set = new HashSet<int>();
for (int i = 0; i < N; ++i)
set.Add(cin.ReadInt);
WriteLine(set.Count());
}
入力を受け取り、Enumerable.Distinct関数で重複を削除するという方法もあります。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
var d = cin.ReadIntArray(N).Distinct();
WriteLine(d.Count());
}
8問目 ABC085C - Otoshidama
10000円札と、5000円札と、1000円札が合計でN枚あって、合計金額がY円であった。このような条件を満たす各金額の札の枚数の組を1つ求める問題です。
本来、各お札についてループを行うところを、for文を工夫し、2つのお札のループだけで解くことにより計算量を削減することが出来ます。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
var Y = cin.ReadInt;
for (int i = 0; i <= N; ++i)
{
for (int j = 0; j <= N - i; ++j)
{
var k = N - i - j;
var sum = 10000 * i + 5000 * j + 1000 * k;
if (sum == Y)
{
WriteLine($"{i} {j} {k}");
return;
}
}
}
WriteLine("-1 -1 -1");
}
9問目 ABC049C - 白昼夢 / Daydream
文字列Sが与えられ、始め空の文字列Tの末尾に "dream", "dreamer", "erase", "eraser"を追加する処理を行って、S=Tにできるか判定する問題です。
一見簡単そうに見えますが、先頭から見ていくと、dreamerase....となっているとき、dreamで切っていいのかの判定が大変です。
そこで、後方から見ていくことにより簡単に解くことが出来ます。
今回、文字列の反転を行うために次のクラスを追加し、stringに対する拡張メソッドを定義しています。
public static class Extensions
{
public static string Reverse(this string sourse)
{
char[] chrAry = sourse.ToCharArray();
Array.Reverse(chrAry);
return new string(chrAry);
}
}
public void Solve(ConsoleInput cin)
{
var S = cin.Read.Reverse();
// 問題文にある文字列を逆にしたもの
var words = new string[] { "maerd", "remaerd", "esare", "resare" };
var flag = true;
for (int i = 0; i < S.Length;)
{
var flag2 = false;
foreach (var x in words)
if (S.Length - i < x.Length) continue;
else if (S.Substring(i, x.Length) == x) { flag2 = true; i += x.Length; }
if (!flag2) { flag = false; break; }
}
if (flag) WriteLine("YES");
else WriteLine("NO");
}
10問目 ABC086C - Traveling
時刻0のとき、平面上の(0, 0)にいます。平面上のN箇所の点を、ある時刻に移動できるかという問題です(雑)。
同じ点にとどまることは出来ませんが、目的の点→隣に移動する→目的の点というような移動は許されています。
また、移動時間より移動距離(二点間のマンハッタン距離)が大きければ移動できません。
public void Solve(ConsoleInput cin)
{
var N = cin.ReadInt;
// 初期状態をt[0], x[0], y[0]とすることで便利になります
var t = new int[N + 1];
var x = new int[N + 1];
var y = new int[N + 1];
y[0] = x[0] = y[0] = 0;
for (int i = 1; i <= N; ++i)
{
t[i] = cin.ReadInt;
x[i] = cin.ReadInt;
y[i] = cin.ReadInt;
}
var flag = true;
for (int i = 0; i < N; ++i)
{
var time = t[i + 1] - t[i];
var dist = Abs(x[i + 1] - x[i]) + Abs(y[i + 1] - y[i]);
if (time < dist) flag = false;
if (Abs(time - dist) % 2 != 0) flag = false;
}
if (flag) WriteLine("Yes");
else WriteLine("No");
}
さいごに
C#は、C++に実行速度等劣るものの、LINQなどSequenceに対する処理が書きやすく、またVisual Studioを始めとする強力な開発環境があることからオススメします！
時間があるときに、類題も解きたいです。