ABC300

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc300

問題A

コンテスト提出

A+Bの値をVとしたとき、CのうちVの位置を出力します。 for文で位置を探索する方法のほかに、Array.IndexOfメソッドを使うことで、指定した値の配列内の位置を取得することができます。

public static void Solve()
{
    var (N, A, B) = Scanner.Scan<int, int, int>();
    var C = Scanner.ScanEnumerable<int>().ToArray();
    var V = A + B;
    var answer = Array.IndexOf(C, V) + 1;
    Console.WriteLine(answer);
}

問題B

コンテスト提出

Aに対して縦方向のシフトをs回すると、A[i][j]の値はA[(i+s)%H][j]に置き換わります。
同様に、横方向のシフトをt回すると、A[i][j]の値はA[i][(j+t)%W]に置き換わります。
このことから、(s,t)を0<=s<H,0<=t<Wの間で全探索して、各要素を判定することで、答えを求めることができます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var A = new char[H][].Select(_ => Scanner.Scan<string>().ToCharArray()).ToArray();
    var B = new char[H][].Select(_ => Scanner.Scan<string>().ToCharArray()).ToArray();
    for (var s = 0; s < H; s++)
    {
        for (var t = 0; t < W; t++)
        {
            var ok = true;
            for (var i = 0; i < H && ok; i++)
            {
                for (var j = 0; j < W && ok; j++)
                {
                    ok &= A[(i + s) % H][(j + t) % W] == B[i][j];
                }
            }

            if (ok)
            {
                Console.WriteLine("Yes");
                return;
            }
        }
    }

    Console.WriteLine("No");
}

問題C

コンテスト提出

サイズsのバツ印が成り立つとき、サイズs-1のバツ印も成り立つ必要があります。 また、サイズs-1のバツ印が成り立つとき、C[a-s][b-s]、C[a-s][b+s]、C[a+s][b-s]、C[a+s][b+s]がグリッド内に存在し、いずれも#であると、サイズsのバツ印が成り立つことになります。 このことから、中心となる(a,b)を全探索し、その位置から成り立つ最大サイズを走査することで、答えを求めることができます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var N = Math.Min(H, W);
    var C = new char[H][].Select(_ => Scanner.Scan<string>().ToCharArray()).ToArray();
    var answer = new int[N + 1];

    int Dfs(int a, int b, int s)
    {
        var ok = true;
        ok &= a - s >= 0 && b - s >= 0 && C[a - s][b - s] == '#';
        ok &= a - s >= 0 && b + s < W && C[a - s][b + s] == '#';
        ok &= a + s < H && b - s >= 0 && C[a + s][b - s] == '#';
        ok &= a + s < H && b + s < W && C[a + s][b + s] == '#';
        var result = s;
        if (ok)
        {
            result = Math.Max(result, Dfs(a, b, s + 1));
        }

        return ok ? result : 0;
    }

    for (var i = 0; i < H; i++)
    {
        for (var j = 0; j < W; j++)
        {
            answer[Dfs(i, j, 0)]++;
        }
    }

    Console.WriteLine(string.Join(" ", answer.Skip(1)));
}

問題D

コンテスト提出
復習提出

c^2<=1e12より、a、b、cはそれぞれ1e6未満の素数になります。 i<k<j番目の素数をそれぞれa=P[i]、P[k]、c=P[j]としたとき、iとjを固定すると、Floor(N/(a^2*c^2))以下のP[k]がbになりえます。
このとき、全てのiとjを探索してしまうと、時間計算量がO(|P|^2)になってしまいますが、a^2>=N、c^2>=N、a^2*c^2>=Nのときを枝刈りすることで、高速で答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var P = Prime.Sieve((int)1e6).Select(x => (long)x).ToArray();
    var answer = 0;
    for (var i = 0; i + 2 < P.Length; i++)
    {
        var a = P[i];
        var aa = a * a;
        if (aa >= N) break;
        for (var j = i + 2; j < P.Length; j++)
        {
            var c = P[j];
            var cc = c * c;
            if (cc >= N || aa * cc >= N) break;
            var v = N / (aa * cc);
            for (var k = i + 1; k < j && P[k] <= v; k++)
            {
                answer++;
            }
        }
    }

    Console.WriteLine(answer);
}

問題E

コンテスト提出

Nを素因数分解したとき、2、3、5以外の素数が含まれているとき、どうやってもNにすることができないので、答えは0になります。 それ以外のとき、次のような動的計画法を解きます。

dp[i][a][b][c] := 素因数をi回使ったとき、2をa回、3をb回、5をc回使っているときの確率

遷移としては次のようになります。

出目が1のとき、素因数の組み合わせに変動を起こさないので無視する。
出目が2のとき、dp[i+1][a+1][b][c]   += dp[i][a][b][c] / 5
出目が3のとき、dp[i+1][a][b+1][c]   += dp[i][a][b][c] / 5
出目が4のとき、dp[i+2][a+2][b][c]   += dp[i][a][b][c] / 5
出目が5のとき、dp[i+1][a][b][c+1]   += dp[i][a][b][c] / 5
出目が6のとき、dp[i+2][a+1][b+1][c] += dp[i][a][b][c] / 5

N==2^a+3^b+5^cとなるときのM=a+b+cとしたとき、dp[M][a][b][c]の値が答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var C = new Dictionary<int, long>();
    var n = N;
    foreach (var v in new[] { 2, 3, 5 })
    {
        C[v] = 0;
        while (n % v == 0)
        {
            C[v]++;
            n /= v;
        }
    }

    if (n != 1)
    {
        Console.WriteLine(0);
        return;
    }

    var i5 = mint.Inverse(5);

    var (c2, c3, c5) = (C[2], C[3], C[5]);
    var M = c2 + c3 + c5;
    var dp = new mint[M + 1, c2 + 1, c3 + 1, c5 + 1];
    dp[0, 0, 0, 0] = 1;
    for (var i = 0; i < M; i++)
    {
        for (var p2 = 0; p2 <= c2; p2++)
        {
            for (var p3 = 0; p3 <= c3; p3++)
            {
                for (var p5 = 0; p5 <= c5; p5++)
                {
                    if (p2 + 1 <= c2) dp[i + 1, p2 + 1, p3, p5] += dp[i, p2, p3, p5] * i5;
                    if (p3 + 1 <= c3) dp[i + 1, p2, p3 + 1, p5] += dp[i, p2, p3, p5] * i5;
                    if (i + 2 <= M && p2 + 2 <= c2) dp[i + 2, p2 + 2, p3, p5] += dp[i, p2, p3, p5] * i5;
                    if (p5 + 1 <= c5) dp[i + 1, p2, p3, p5 + 1] += dp[i, p2, p3, p5] * i5;
                    if (i + 2 <= M && p2 + 1 <= c2 && p3 + 1 <= c3) dp[i + 2, p2 + 1, p3 + 1, p5] += dp[i, p2, p3, p5] * i5;
                }
            }
        }
    }

    var answer = dp[M, c2, c3, c5];
    Console.WriteLine(answer);
}