ABC275

Published on Saturday, 29 October 2022

Updated on Saturday, 29 October 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc275

問題A

コンテスト提出

順番にAの値を見ていき、それまでの最大値より大きい場合、最大値と答えを更新し、最後まで見たときの最大値の順番が答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var H = Scanner.ScanEnumerable<int>().ToArray();
    var answer = 0;
    var max = 0;
    for (var i = 0; i < N; i++)
    {
        if (max < H[i])
        {
            max = H[i];
            answer = i + 1;
        }
    }

    Console.WriteLine(answer);
}

64bit整数型を使っても、10^18^6は整数型に収まりません。 (X*Y)%Mの値は(X%M)*(Y%M)の値と等しくなるように、余りをとる+,-,*の演算は計算の途中で余りをとっても最終的な余りと等しくなります。そのため、各演算ごとに余りを取ることで、各項最大でも10^9に収まり、掛け算でも10^9 * 10^9で10^18に収まります。引き算を行うことで値が負の値になる可能性があるので、余りを足すことで正の値にすることに注意します。余りをとる整数型の構造体をライブラリとして作っておくと便利です。

public static void Solve()
{
    var (A, B, C, D, E, F) = Scanner.Scan<long, long, long, long, long, long>();
    var answer = ((mint)A * (mint)B * (mint)C) - ((mint)D * (mint)E * (mint)F);
    Console.WriteLine(answer);
}

public readonly struct ModuloInteger : IEquatable<ModuloInteger>
{
    public long Value { get; }

    // The modulo will be used as an editable property.
    // public static long Modulo { get; set; } = 998244353;
    // The constant modulo will be recommended to use for performances in use cases.
    public const long Modulo = 998244353;

    public ModuloInteger(int value)
    {
        Value = value % Modulo;
        if (Value < 0) Value += Modulo;
    }

    public ModuloInteger(long value)
    {
        Value = value % Modulo;
        if (Value < 0) Value += Modulo;
    }

    public static implicit operator int(ModuloInteger mint) => (int)mint.Value;
    public static implicit operator long(ModuloInteger mint) => mint.Value;
    public static implicit operator ModuloInteger(int value) => new ModuloInteger(value);
    public static implicit operator ModuloInteger(long value) => new ModuloInteger(value);
    public static ModuloInteger operator +(ModuloInteger a, ModuloInteger b) => a.Value + b.Value;
    public static ModuloInteger operator -(ModuloInteger a, ModuloInteger b) => a.Value - b.Value;
    public static ModuloInteger operator *(ModuloInteger a, ModuloInteger b) => a.Value * b.Value;
    public static ModuloInteger operator /(ModuloInteger a, ModuloInteger b) => a * b.Inverse();
    public static bool operator ==(ModuloInteger a, ModuloInteger b) => a.Equals(b);
    public static bool operator !=(ModuloInteger a, ModuloInteger b) => !a.Equals(b);
    public bool Equals(ModuloInteger other) => Value == other.Value;
    public override bool Equals(object obj) => obj is ModuloInteger other && Equals(other);
    public override int GetHashCode() => Value.GetHashCode();
    public override string ToString() => Value.ToString();
    public ModuloInteger Inverse() => Inverse(Value);

    public static ModuloInteger Inverse(long value)
    {
        if (value == 0) return 0;
        var (s, t, m0, m1) = (Modulo, value, 0L, 1L);
        while (t > 0)
        {
            var u = s / t;
            s -= t * u;
            m0 -= m1 * u;
            (s, t) = (t, s);
            (m0, m1) = (m1, m0);
        }

        if (m0 < 0) m0 += Modulo / s;
        return m0;
    }

    public ModuloInteger Power(long n) => Power(Value, n);

    public static ModuloInteger Power(long value, long n)
    {
        if (n < 0) throw new ArgumentException(nameof(n));
        var result = 1L;
        while (n > 0)
        {
            if ((n & 1) > 0) result = result * value % Modulo;
            value = value * value % Modulo;
            n >>= 1;
        }

        return result;
    }
}

問題C

コンテスト提出

正方形となる4つの頂点を全探索し、正方形となる頂点の組み合わせを数え上げます。正方形の左上の頂点をp1、右上の頂点をp2、左下の頂点をp3、右下をp4としたとき、p1-p2のベクトルと、p3-p4のベクトルは一致し、p1-p3のベクトルは、p1-p2を90度回転させたものと一致する必要があります。

public static void Solve()
{
    var N = 9;
    var G = new bool[N][];
    for (var i = 0; i < N; i++)
    {
        G[i] = Scanner.Scan<string>().Select(x => x == '#').ToArray();
    }

    var answer = 0;

    IEnumerable<(int H, int W)> F()
    {
        for (var i = 0; i < N; i++)
        {
            for (var j = 0; j < N; j++)
            {
                yield return (i, j);
            }
        }
    }

    foreach (var p1 in F())
    {
        foreach (var p2 in F())
        {
            foreach (var p3 in F())
            {
                foreach (var p4 in F())
                {
                    if (p1 == p2 || p1 == p3 || p1 == p4 || p2 == p3 || p2 == p4 || p3 == p4) continue;
                    var e1 = (p2.H - p1.H, p2.W - p1.W);
                    var e3 = (p4.H - p3.H, p4.W - p3.W);
                    var e2 = (p3.W - p1.W, -(p3.H - p1.H));
                    var ok = e1 == e3 && e1 == e2;
                    ok &= G[p1.H][p1.W];
                    ok &= G[p2.H][p2.W];
                    ok &= G[p3.H][p3.W];
                    ok &= G[p4.H][p4.W];
                    if (ok) answer++;
                }
            }
        }
    }

    answer /= 4;
    Console.WriteLine(answer);
}

問題D

コンテスト提出

全てのF(x)を都度求めてしまうと、何度も同じ計算を行ってしまい、Nが大きい場合、実行時間制限に間に合いません。そこで、一度計算した値を保持しておくことで(メモ化再帰)、同じ計算を省略することで、実行時間制限に間に合わせることができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var dp = new Dictionary<long, long>();
    dp[0] = 1;

    long F(long x)
    {
        if (dp.ContainsKey(x)) return dp[x];
        return dp[x] = F(x / 2) + F(x / 3);
    }

    var answer = F(N);
    Console.WriteLine(answer);
}

問題E

コンテスト提出

dp[i][j]:=ルーレットをi回まわした時にマスjにいる確率とした動的計画法を解きます。遷移としては、今いるマスの確率/Mが次のいるマスの確率に寄与します。 Mの逆元を求めることにO(logMod)かかるので、前計算しておくことで高速化できます。

public static void Solve()
{
    var (N, M, K) = Scanner.Scan<int, int, int>();
    var dp = new mint[K + 1, N + 1];
    dp[0, 0] = 1;
    var im = mint.Inverse(M);

    for (var k = 0; k < K; k++)
    {
        for (var m = 1; m <= M; m++)
        {
            for (var n = 0; n < N; n++)
            {
                var x = n + m;
                if (x > N) x = Math.Max(0, N - (x - N));
                dp[k + 1, x] += dp[k, n] * im;
            }
        }
    }

    mint answer = 0;
    for (var k = 0; k <= K; k++)
    {
        answer += dp[k, N];
    }

    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E