ABC265

Published on Sunday, 21 August 2022

Updated on Sunday, 21 August 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc265

問題A

コンテスト提出

3個のりんごをbセット買ったとき、1個のりんごをa=N-b*3セット買うことができます。このaとbを全探索し、a*X+b*Yの最小を求めます。

public static void Solve()
{
    var (X, Y, N) = Scanner.Scan<int, int, int>();
    const int inf = (int)1e9;
    var answer = inf;
    for (var b = 0; b * 3 <= N; b++)
    {
        var a = (N - b * 3);
        var v = a * X + b * Y;
        answer = Math.Min(answer, v);
    }
    Console.WriteLine(answer);
}

X*3>Yで場合分けをして、時間計算量O(1)で解くこともできます。

public static void Solve()
{
    var (X, Y, N) = Scanner.Scan<int, int, int>();
    var answer = X * 3 > Y ? (N / 3) * Y + N % 3 * X : X * N;
    Console.WriteLine(answer);
}

問題B

コンテスト提出

愚直にシミュレーションを行い、現在の持ち時間-A[i]が0以下になれば、答えはNoとなります。 1回の移動あたりのボーナスを全て探索してしまうと、全体の時間計算量がO(N^2)かかってしまうので、あらかじめ配列としてbonus[x]をもっておくことで、1回の移動あたりのボーナスの値をO(1)で取得することができ、全体計算量O(N)で解くことができます。

public static void Solve()
{
    var (N, M, T) = Scanner.Scan<int, int, long>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    var bonus = new long[N + 1];
    for (var i = 0; i < M; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        bonus[x] = y;
    }

    var curr = T;
    for (var i = 0; i < N - 1; i++)
    {
        curr += bonus[i + 1];
        if (curr > A[i])
        {
            curr -= A[i];
        }
        else
        {
            Console.WriteLine("No");
            return;
        }
    }

    Console.WriteLine("Yes");
}

問題C

コンテスト提出

現在いるマスに書かれている文字にそって愚直にシミュレーションを行います。あるマス(i,j)からマスの外に出ようとした場合には、答えはマス(i,j)となります。無限に移動し続ける場合の判定として、既に訪れたマスをフラグ管理なのでメモしておき、移動先のマスが既に訪れているマスの場合には答えは-1となります。

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

    var used = new bool[H, W];
    used[0, 0] = true;
    var queue = new Queue<(int, int)>();
    queue.Enqueue((0, 0));
    while (queue.Count > 0)
    {
        var (ch, cw) = queue.Dequeue();
        var (nh, nw) = G[ch][cw] switch
        {
            'U' => (ch - 1, cw),
            'D' => (ch + 1, cw),
            'L' => (ch, cw - 1),
            'R' => (ch, cw + 1),
            _ => (0, 0),
        };

        if (nh < 0 || H <= nh || nw < 0 || W <= nw)
        {
            Console.WriteLine($"{ch + 1} {cw + 1}");
            return;
        }

        if (used[nh, nw])
        {
            Console.WriteLine(-1);
            return;
        }

        used[nh, nw] = true;
        queue.Enqueue((nh, nw));
    }
}

累積和をあらかじめ求めておくことで、区間和を時間計算量O(1)で求めることができます。また、尺取り法で区間和Cum[w]-Cum[x]==P+Q+Rとなる区間を求めることで、xとwが時間計算量O(N)でわかります。このxとw間でCum[y]-Cum[x]==P、Cum[z]-Cum[y]==Q、Cum[w]-Cum[z]==Rとなるyとzが存在すれば、答えはYesとなります。

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

    var PQR = P + Q + R;
    var w = 0;
    for (var x = 0; x < N; x++)
    {
        while (x < N && cum[w] - cum[x] < PQR) w++;
        if (cum[w] - cum[x] != PQR) continue;
        
        var y = l;
        while (y < w && cum[y] - cum[x] < P) y++;
        if (cum[y] - cum[x] != P) continue;

        var z = y;
        while (z < w && cum[z] - cum[y] < Q) z++;
        if (cum[z] - cum[y] != Q) continue;

        if (cum[w] - cum[z] != R) continue;

        Console.WriteLine("Yes");
        return;
    }

    Console.WriteLine("No");
}

問題E

コンテスト提出

dp[i][x][y] := i回目の移動で(x,y)に至る移動経路の個数とする動的計画法を解きます。ここで、(x,y)の取りうる値は疎であることから、全ての(x,y)を管理せずに移動しうる(x,y)をキーとした辞書などを使って管理することで、時間計算量O(N^3logN)で答えを求めることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var (A, B, C, D, E, F) = Scanner.Scan<long, long, long, long, long, long>();
    var delta = new (long, long)[] { (A, B), (C, D), (E, F) };
    var obstacles = new HashSet<Point>();
    for (var i = 0; i < M; i++)
    {
        var (x, y) = Scanner.Scan<long, long>();
        obstacles.Add(new Point(x, y));
    }

    var dp0 = new Dictionary<Point, mint>();
    dp0[new Point(0, 0)] = 1;
    for (var i = 0; i < N; i++)
    {
        var dp1 = new Dictionary<Point, mint>();
        foreach (var (p, v) in dp0)
        {
            foreach (var (dx, dy) in delta)
            {
                var np = new Point(p.X + dx, p.Y + dy);
                if (obstacles.Contains(np)) continue;
                if (!dp1.ContainsKey(np)) dp1[np] = 0;
                dp1[np] += v;
            }
        }

        dp0 = dp1;
    }

    mint answer = 0;
    foreach (var (_, v) in dp0)
    {
        answer += v;
    }

    Console.WriteLine(answer);
}

public readonly struct Point : IEquatable<Point>
{
    public readonly long X;
    public readonly long Y;
    public Point(long x, long y) => (X, Y) = (x, y);
    public bool Equals(Point other) => X == other.X && Y == other.Y;
    public override int GetHashCode() => HashCode.Combine(X, Y);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E