ABC280

はじめに

AtCoder Beginner Contest 280の復習記事です。

記事におけるScannerクラスは、自作の入力クラスです。

コンテスト

https://atcoder.jp/contests/abc280

問題A

コンテスト提出

文字列として入力をとり、全ての文字から#の数を数え上げます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var answer = 0;
    for (var i = 0; i < H; i++)
    {
        var S = Scanner.Scan<string>();
        foreach (var c in S)
        {
            if (c == '#') answer++;
        }
    }

    Console.WriteLine(answer);
}

問題B

コンテスト提出

S[k]=A[1]+A[2]+...A[k-1]+A[k]であることから、S[k]=S[k-1]+A[k]であることがわかります。 そのため、i==1のときはA[1]=S[1]であり、i>1の場合はA[i]=S[i]-S[i-1]として、答えとなる数列Aを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = Scanner.ScanEnumerable<long>().ToArray();
    var A = new long[N];
    A[0] = S[0];
    for (var i = 1; i < N; i++)
    {
        A[i] = S[i] - S[i - 1];
    }

    Console.WriteLine(string.Join(" ", A));
}

問題C

コンテスト提出

Sの長さの範囲ではS[i]!=T[i]となるiが答えとなり、TがSの最後に文字が追加されている文字列である場合は、Tの最後が答えとなります。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var T = Scanner.Scan<string>();
    var N = S.Length;
    for (var i = 0; i < N; i++)
    {
        if (S[i] != T[i])
        {
            Console.WriteLine(i + 1);
            return;
        }
    }

    Console.WriteLine(T.Length);
}

問題D

復習提出

Kについて素因数分解を行い、Kの倍数であるために必要な素数とその個数を求めます。 そして、ある素数をその必要な個数以上使ったときのnの値の最大が答えとなります。

public static void Solve()
{
    var K = Scanner.Scan<long>();
    long answer = 0;
    foreach (var (prime, required) in Prime.GetFactorDictionary(K))
    {
        long n = 0;
        var used = 0;
        while (used < required)
        {
            n += prime;
            var x = n;
            while (x % prime == 0)
            {
                x /= prime;
                used++;
            }
        }

        answer = Math.Max(answer, n);
    }

    Console.WriteLine(answer);
}

public static class Prime
{
    public static IDictionary<long, int> GetFactorDictionary(long value)
    {
        var factors = new Dictionary<long, int>();
        if (value < 2) return factors;

        void CountUp(long n)
        {
            if (value % n != 0) return;
            factors[n] = 0;
            while (value % n == 0)
            {
                value /= n;
                factors[n]++;
            }
        }

        CountUp(2);
        for (var i = 3L; i * i <= value; i += 2) CountUp(i);
        if (value > 1) factors[value] = 1;
        return factors;
    }
}

問題E

復習提出

dp[i] := dp[i+2]*(i+2から遷移する確率) + dp[i+1]*(i+1から遷移する確率) + 1のような攻撃回数についての期待値dpを行います。

public static void Solve()
{
    var (N, P) = Scanner.Scan<int, int>();
    var dp = new mint[N + 1];
    var p2 = P * mint.Inverse(100);
    var p1 = 1 - p2;
    for (var i = N - 1; i >= 0; i--)
    {
        dp[i] = dp[Math.Min(N, i + 1)] * p1 + dp[Math.Min(N, i + 2)] * p2 + 1;
    }

    var answer = dp[0];
    Console.WriteLine(answer);
}