たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】AtCoder Beginner Contest 148 の反省

AtCoder Beginner Contest 148のコンテストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。

はじめに

コンテストへのリンク

atcoder.jp

解いた問題

A,B,C,Dを解きました。Eが解けなかったので解説を確認して実装しました。今回、D問題まで灰色レベルだったので4完したといえど、茶色前半のパフォーマンスでした。

解答説明

A問題

組み合わせを考えるのですが、A,Bを入れ替えた場合分けを書くのが面倒くさかったので、私はA+Bが3,4,5の時で場合分けをしました。

if (A + B == 3) Console.WriteLine(3);
if (A + B == 4) Console.WriteLine(2);
if (A + B == 5) Console.WriteLine(1);

実装 AtCoder/A.cs at master · chittai/AtCoder · GitHub

B問題

下記のように解答用のstring型の変数 res に交互に追加。ほぼA問題と同じレベルですね。

string res = "";
for (int i = 0; i < N; i++)
{
    res += S[i];
    res += T[i];
}

実装 AtCoder/C.cs at master · chittai/AtCoder · GitHub

C問題

最小公倍数を求める。以前作成した関数を使用しました。CalcLCMの引数にA,Bを指定して上げればOKです。

public static long CalcGCD(long a, long b)
{
    if (b == 0) { return a; }
    return CalcGCD(b, a % b);
}
public static long CalcLCM(long a, long b)
{
    return a * b / CalcGCD(a, b);
}

実装 AtCoder/C.cs at master · chittai/AtCoder · GitHub

D問題

先頭から、貪欲に1,2,3,...,Kの値を与えられたa[]から探していき、該当しなければすべてのブロックを削除します(res)。

long res = 0;
long current = 0;
for (int i = 0; i < N; i++)
{
    if (current + 1 == a[i]) { current = a[i]; }
    else res++;
}

E問題

整数 N が与えられます。f(N) を 10 進法で表記した時に末尾に何個の 0 が続くかを求めてください。

という問題です。f(N) = 1 (N<2) , f(N) = N * f(N-2) (N <= 2) です。

drken1215.hatenablog.com

まさにまんま実装しました。最初、10 -> 1 , 20 -> 2 ...というところまでは見れていたので10の登場回数かと思っていましたが、当然それだと例3の答えに合わず。。。実際は2 * 5 でも10がつくれるのでmin(2で割った回数, 5で割った回数)でできるとのこと。こういう数学的問題はなかなか解けないので、なれるしかないのかなという感想。

実装 AtCoder/E.cs at master · chittai/AtCoder · GitHub