ABC253

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc253

問題A

コンテスト提出

要素が3つしかないため、3つの値の合計から最大値と最小値を引いた値が中央値として求めることができるので、中央値がBと一致しているかを判定します。

public static void Solve()
{
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var mid = A.Sum() - A.Min() - A.Max();
    var answer = A[1] == mid ? "Yes" : "No";
    Console.WriteLine(answer);
}

問題B

コンテスト提出

(h1,w1)から(h2,w2)への移動回数は縦横の差分の合計Abs(h2-h1) + Abs(w2-w1)で求めることができます。
2つのoの位置を取得は、1つ目ならば(h1,w1)を更新し、2つ目ならば(h2,w2)を更新するようにフラグなどで管理することで判定できます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var G = new string[H];
    for (var i = 0; i < H; i++)
    {
        G[i] = Scanner.Scan<string>();
    }

    var (h1, w1) = (0, 0);
    var (h2, w2) = (0, 0);
    var ok = false;
    for (var i = 0; i < H; i++)
    {
        for (var j = 0; j < W; j++)
        {
            if (G[i][j] == '-') continue;
            if (!ok)
            {
                (h1, w1) = (i, j);
                ok = true;
            }
            else
            {
                (h2, w2) = (i, j);
            }
        }
    }

    var answer = Math.Abs(h2 - h1) + Math.Abs(w2 - w1);
    Console.WriteLine(answer);
}

問題C

コンテスト提出

リストを使って集合の管理をしてしまうと、クエリごとの最悪時間計算量がO(NlogN)になってしまい、全体でO(QNlogN)となり、実行時間制限に間に合いません。
そこで、ソートされている集合(C#ではSortedSet)等を実際に集合に存在する値に対して使うことで、要素の追加をO(logN)、最大値の最小値の取得をO(1)で行うことができ、全体でO(QlogN)に改善することができます。

public static void Solve()
{
    var Q = Scanner.Scan<int>();
    var set = new SortedSet<int>();
    var dict = new Dictionary<int, long>();
    while (Q-- > 0)
    {
        var query = Scanner.ScanEnumerable<int>().ToArray();
        if (query[0] == 1)
        {
            var x = query[1];
            if (!dict.ContainsKey(x)) dict[x] = 0;
            dict[x]++;
            set.Add(x);
        }
        else if (query[0] == 2)
        {
            var (x, c) = (query[1], query[2]);
            if (!dict.ContainsKey(x)) dict[x] = 0;
            dict[x] -= Math.Min(dict[x], c);
            if (dict[x] == 0)
            {
                set.Remove(x);
            }
        }
        else
        {
            var answer = set.Max - set.Min;
            Console.WriteLine(answer);
        }
    }
}

問題D

コンテスト提出
復習提出

N以下の値を全て捜査してしまうと、時間計算量がO(N)になってしまい、N=1e9の場合に間に合いません。 そこで、1からNまでの総和から、Aの倍数の総和とBの倍数の総和を引き、AとBの最小公倍数の総和を足すことでO(logMin(a,b))で求めることができます。
1からxまでの総和は、F(x) = x * (x+1) / 2で求められるので、1からNまでの総和はF(N)で求めることができます。
N以下のXの倍数の総和は、N以下にXの倍数はN/X個あるため、M=N/Xとしたとき、X*F(M)で求めることができます。 よって、xとyの最小公倍数をLCM(x,y)としたとき、F(N) - F(N/A)*A - F(N/B)*B + F(N/LCM(A,B))*LCM(A,B)で求めることができます。

public static void Solve()
{
    var (N, A, B) = Scanner.Scan<long, long, long>();

    long F(long x) => x * (x + 1) / 2;
    long G(long n, long a, long b)
    {
        var result = F(n);
        result -= a * F(n / a);
        result -= b * F(n / b);
        var lcm = Lcm(a, b);
        result += lcm * F(n / lcm);
        return result;
    }

    var answer = G(N, A, B);
    Console.WriteLine(answer);
}

問題E

復習提出

累積和を求めながら動的計画法をすることで求めることができます。 初期状態として、[1,M]は各1になり、i+1項目への遷移はdp[i][0..j-k] + dp[i][j+k..M]の総和となります。 区間和dp[i][0..j-k] + dp[i][j+k..M]を各jに対して求めてしまうと、時間計算量がO(M)かかってしまうので、あらかじめ累積和を取っておくことで、jごとにO(1)で区間和を求めることができます。 K=0のときには注意が必要で、dp[i][1..M]の総和が遷移します。

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

    for (var i = 0; i < N; i++)
    {
        var cum = new mint[M + 10];
        for (var j = 1; j <= M; j++)
        {
            cum[j + 1] = cum[j] + dp[i, j];
        }

        for (var j = 1; j <= M; j++)
        {
            if (K > 0)
            {
                var l1 = 0;
                var r1 = Math.Max(0, j - K) + 1;
                var l2 = Math.Min(M + 1, j + K);
                var r2 = M + 1;
                dp[i + 1, j] += cum[r1] - cum[l1] + cum[r2] - cum[l2];
            }
            else
            {
                dp[i + 1, j] += cum[M + 1];
            }
        }
    }

    mint answer = 0;
    for (var i = 1; i <= M; i++)
    {
        answer += dp[N - 1, i];
    }

    Console.WriteLine(answer);
}