ABC308

Published on Saturday, 01 July 2023

Updated on Saturday, 01 July 2023

atcoder csharp

はじめに

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

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

Scannerクラス

public static class Scanner
{
    public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
    public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]));
    }
    public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
    }
    public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
    }
    public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
    }
    public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
    }
    public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
    private static string[] ScanStringArray()
    {
        var line = Console.ReadLine()?.Trim() ?? string.Empty;
        return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
    }
    private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}

コンテスト

https://atcoder.jp/contests/abc308

問題A

コンテスト提出

全てのS[i]において各条件を満たすかどうかを判定します。

public static void Solve()
{
    var A = Scanner.ScanEnumerable<int>().ToArray();
    bool F1(int x) => 100 <= x && x <= 675;
    bool F2(int x) => x % 25 == 0;
    var answer = F1(A[0]) && F2(A[1]);
    for (var i = 1; i < A.Length; i++)
    {
        answer &= A[i] >= A[i - 1] && F1(A[i]) && F2(A[i]);
    }

    Console.WriteLine(answer ? "Yes" : "No");
}

問題B

コンテスト提出

辞書などを使って料理名に対して値段を設定し、食べた料理の価格の合計を計算します。
Dに存在しない料理名の価格はP[0]になることに注意します。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var C = Scanner.ScanEnumerable<string>().ToArray();
    var D = Scanner.ScanEnumerable<string>().ToArray();
    var P = Scanner.ScanEnumerable<long>().ToArray();
    var dict = new Dictionary<string, long>();
    for (var i = 0; i < M; i++)
    {
        dict[D[i]] = P[i + 1];
    }

    var answer = C.Sum(x => dict.ContainsKey(x) ? dict[x] : P[0]);
    Console.WriteLine(answer);
}

成功率を浮動小数点で計算してしまうと誤差が発生してしまうため、整数型で管理できるようにします。ある確率Xが整数aとbでa/b、確率Yが整数cとdでc/dで表すことができるとき、不等式X>Yはa/b>c/dとなりますが、両辺にb*dを掛けることで、a*d>c*bとすることができ、整数型で比較を行うことができるようになります。そのため、整数型で分母と分子を管理しながら成功率が高い順に並べることで、答えを求めることができるようになります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var P = new Fraction[N];
    for (var i = 0; i < N; i++)
    {
        var (a, b) = Scanner.Scan<long, long>();
        P[i] = new Fraction(a, a + b);
    }

    var H = Enumerable.Range(0, N).ToArray();
    Array.Sort(H, (x, y) =>
    {
        var result = P[y].CompareTo(P[x]);
        return result == 0 ? x.CompareTo(y) : result;
    });

    Console.WriteLine(string.Join(" ", H.Select(x => x + 1)));
}

public readonly struct Fraction : IComparable<Fraction>, IEquatable<Fraction>
{
    public long Y { get; }
    public long X { get; }

    public Fraction(long y, long x)
    {
        static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
        var g = Gcd(y, x);
        (Y, X) = (y / g, x / g);
    }

    public static bool operator <(Fraction left, Fraction right) => left.CompareTo(right) < 0;
    public static bool operator <=(Fraction left, Fraction right) => left.CompareTo(right) <= 0;
    public static bool operator >(Fraction left, Fraction right) => left.CompareTo(right) > 0;
    public static bool operator >=(Fraction left, Fraction right) => left.CompareTo(right) >= 0;
    public static bool operator ==(Fraction left, Fraction right) => left.Equals(right);
    public static bool operator !=(Fraction left, Fraction right) => !left.Equals(right);
    public int CompareTo(Fraction other) => (Y * other.X).CompareTo(X * other.Y);
    public bool Equals(Fraction other) => Y == other.Y && X == other.X;
    public override bool Equals(object obj) => obj is Fraction other && Equals(other);
    public override int GetHashCode() => HashCode.Combine(Y, X);
    public override string ToString() => $"{Y}/{X}";
}

問題D

コンテスト提出

各マスを頂点とし、現在の文字がsnuke文字列の何番目であるかを管理しながら、幅優先探索を行います。

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

    int F(char c)
    {
        return c switch
        {
            's' => 0,
            'n' => 1,
            'u' => 2,
            'k' => 3,
            'e' => 4,
            _ => -1,
        };
    }

    var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };

    var used = new bool[H, W];
    var queue = new Queue<(int H, int W, int S)>();
    if (G[0][0] == 0)
    {
        used[0, 0] = true;
        queue.Enqueue((0, 0, 0));
    }

    while (queue.Count > 0)
    {
        var (ch, cw, cs) = queue.Dequeue();
        foreach (var (dh, dw) in D4)
        {
            var (nh, nw) = (ch + dh, cw + dw);
            if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
            var ns = G[nh][nw];
            if (ns == (cs + 1) % 5 && !used[nh, nw])
            {
                used[nh, nw] = true;
                queue.Enqueue((nh, nw, ns));
            }
        }
    }

    var answer = used[H - 1, W - 1];
    Console.WriteLine(answer ? "Yes" : "No");
}

問題E

復習提出

jを固定したとき、そのjからありえるMEXの組み合わせは、A[i]の値が0,1,2の3通りとA[k]の値が0,1,2の3通りの合計9通りになります。
jまでに出現する{0,1,2}の個数、j以降に出現する{0,1,2}の個数に対してmex({0,1,2},A[j],{0,1,2})を掛けることで、そのjに対するmex(A[i],A[j],A[k])の総和を求めることができます。
あらかじめ累積和で各値が出現する個数を求めておくことで、jにおける各mex(A[i],A[j],A[k])の値を時間計算量O(1)で求めることができ、全体で時間計算量O(N)で答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var S = Scanner.Scan<string>();

    var countM = new long[N + 1, 3];
    var countX = new long[N + 1, 3];
    for (var i = 0; i < N; i++)
    {
        for (var m = 0; m < 3; m++)
        {
            countM[i + 1, m] += countM[i, m];
            countX[i + 1, m] += countX[i, m];
        }

        if (S[i] == 'M') countM[i + 1, A[i]]++;
        if (S[i] == 'X') countX[i + 1, A[i]]++;
    }

    int Mex(int a, int b, int c)
    {
        for (var mex = 0; mex < 3; mex++)
        {
            if (mex != a && mex != b && mex != c) return mex;
        }

        return 3;
    }

    long answer = 0;
    for (var j = 0; j < N; j++)
    {
        if (S[j] != 'E') continue;
        for (var i = 0; i < 3; i++)
        {
            for (var k = 0; k < 3; k++)
            {
                var ci = countM[j, i];
                var ck = countX[N, k] - countX[j, k];
                answer += ci * ck * Mex(i, A[j], k);
            }
        }
    }

    Console.WriteLine(answer);
}

問題F

復習提出

Pを小さい順に見ていき、各P[i]に対して利用可能な最大のD[j]を使用していくことで、最小値を求めることができます。利用可能な最大のD[j]は、L[j]を小さい順にソートし、現在見ているP[i]以下のL[j]に対応するD[j]を優先度付きキューに挿入していき、優先度付きキューの先頭にあるものを消費することで求めることができ、全体時間計算量`O(NlogN+MlogM)で答えを求めることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var P = Scanner.ScanEnumerable<int>().ToArray();
    var L = Scanner.ScanEnumerable<long>().ToArray();
    var D = Scanner.ScanEnumerable<long>().ToArray();
    var LD = L.Zip(D).ToArray();
    Array.Sort(P, (x, y) => x.CompareTo(y));
    Array.Sort(LD, (x, y) => x.First.CompareTo(y.First));

    var queue = new PriorityQueue<long>((x, y) => y.CompareTo(x));
    var idx = 0;
    long answer = 0;
    foreach (var p in P)
    {
        answer += p;
        while (idx < M && LD[idx].First <= p)
        {
            queue.Enqueue(LD[idx++].Second);
        }

        if (queue.Count > 0)
        {
            answer -= queue.Dequeue();
        }
    }

    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E

問題F