ABC252

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc252

問題A

コンテスト提出

C#ではcharの0-255にはASCII文字コードが割り当てられているため、数値をchar型に明示的に変換することで、与えられた数値に対する文字に変換することができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var answer = (char)N;
    Console.WriteLine(answer);
}

問題B

コンテスト提出

おいしさが最大のときの食品の番号の集合をとり、Bの何れかがその集合に存在していればYes、そうでなければNoとなります。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var set = new HashSet<int>();
    var max = -1;
    for (var i = 0; i < N; i++)
    {
        if (max < A[i])
        {
            max = A[i];
            set.Clear();
            set.Add(i + 1);
        }
        else if (max == A[i])
        {
            set.Add(i + 1);
        }
    }

    var answer = false;
    foreach (var b in B)
    {
        answer |= set.Contains(b);
    }

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

問題C

コンテスト提出

表示される数字を全探索して最小となる秒数を求めます。
各リールにおいて指定した数字が出現する秒数をN周分保持し、出現する秒数が早い順から採用します。
採用したリールをメモしておき、全てのリールが採用された時の秒数の最小を出力します。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = new int[N][];
    for (var i = 0; i < N; i++)
    {
        var s = Scanner.Scan<string>();
        S[i] = s.Select(x => x - '0').ToArray();
    }

    const long inf = (long)1e18;
    var answer = inf;
    for (var n = 0; n < 10; n++)
    {
        var list = new List<(int T, int ID)>();
        for (var i = 0; i < N; i++)
        {
            var idx = Array.IndexOf(S[i], n);
            list.AddRange(Enumerable.Range(0, N).Select(x => (x * 10 + idx, i)));
        }

        list.Sort((x, y) => x.T.CompareTo(y.T));
        var used = new HashSet<int>();
        var curr = -1;
        foreach (var (t, i) in list)
        {
            if (t <= curr || used.Contains(i)) continue;
            used.Add(i);
            curr = t;
            if (used.Count == N)
            {
                answer = Math.Min(answer, curr);
                break;
            }
        }
    }

    Console.WriteLine(answer);
}

問題D

コンテスト提出

愚直にi,j,kの全ての組み合わせを全探索してしまうと、数え上げの時間計算量がO(N^3)となり、実行時間制限に間に合わないません。 そこで、出現する数値をまとめて数え上げます。 以下数値をまとめた個数の配列をC、Cの長さをMとします。

Cのうち、0<=i<j<k<Mとなるi,j,kの組み合わせを全探索すると、時間計算量がO(M^3)であり、時間計算量はまだ改善できていません。 まず、Cのうち0<=j<k<Mとなるj,k組み合わせを愚直に考えると、以下のように数え上げることができます。

for(var j = 0; j < M; j++)
{
    for(var k = j + 1; k < M; k++)
    {
        sumJK += C[j] * C[k];
    }
}

この場合、j,kの組み合わせは時間計算量O(M^2)で求めることができますが、jを固定したときの組み合わせの個数は、C[j]*(C[j+1] + C[j+2] + .. + C[M-1])となり、C[j]にj以降の累積和をかけたものであることがわかります。 そのため、C[k]の累積和をあらかじめ求めておくことで、数え上げの時間計算量をO(M)に改善することができます。

for (var k = M - 1; k >= 0; k--)
{
    cumK[k] = C[k] + cumK[k + 1];
}

for(var j = 0; j < M; j++)
{
    sumJK += C[j] * cumK[j + 1];
}

これを利用すると、Cのうち0<=i<j<k<Mとなるi,j,kの組み合わせは時間計算量O(M^2)で求めることができます。

for(var i = 0; i < M; i++)
{
    for(var j = i + 1; j < M; j++)
    {
        sumIJK += C[i] * C[j] * cumK[j + 1];
    }
}

また、iを固定したときの組み合わせは、C[i] * (C[i+1]*cumK[i+2] + C[i+2]*cumK[i+3] + .. + C[M-2]*cumK[M-1])となり、C[i]にi以降のCとC[k]の累積和をかけたものの累積和であることがわかります。 そのため、C[j]にC[k]の累積和をかけたものの累積和をあらかじめ求めておくことで、数え上げの時間計算量をO(M)に改善することができます。

for (var j = M - 1; k >= 0; k--)
{
    cumJ[k] = C[j] * cumK[j + 1] + cumJ[j + 1];
}

for(var i = 0; i < M; j++)
{
    sumIJK += C[i] * cumJ[i + 1];
}

以上により、時間計算量O(M)で答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var count = new int[(int)2e5 + 1];
    foreach (var a in A)
    {
        count[a]++;
    }

    var C = count.Where(x => x > 0).ToArray();
    var M = C.Length;

    var cumK = new long[M + 1];
    var cumJ = new long[M + 1];
    for (var k = M - 1; k >= 0; k--)
    {
        cumK[k] = C[k] + cumK[k + 1];
    }

    for (var j = M - 1; j >= 0; j--)
    {
        cumJ[j] = C[j] * cumK[j + 1] + cumJ[j + 1];
    }

    long answer = 0;
    for (var i = 0; i < M; i++)
    {
        answer += C[i] * cumJ[i + 1];
    }

    Console.WriteLine(answer);
}

問題E

コンテスト提出

頂点1からの最短経路を求め、各頂点への最短経路とその直前の頂点を結ぶN-1本の道が答えとなります。
これは、頂点1から頂点vへの最短経路があるとき、その経路上の頂点uへの経路は、頂点1から頂点uへの最短経路であることからわかります。 ダイクストラ法で頂点1から各頂点への最短経路を求めるときに、各頂点の直前の頂点をメモしておき、頂点vの直前の頂点uをつなぐ道が何番目の道であるかを実装することで答えを求めることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var dict = new Dictionary<(int U, int V), int>();
    var G = new List<(int, long)>[N].Select(x => new List<(int, long)>()).ToArray();
    for (var i = 0; i < M; i++)
    {
        var (a, b, c) = Scanner.Scan<int, int, long>();
        a--; b--;
        G[a].Add((b, c));
        G[b].Add((a, c));

        dict[(a, b)] = dict[(b, a)] = i + 1;
    }

    var costs = new long[N];
    Array.Fill(costs, long.MaxValue);
    costs[0] = 0;
    var queue = new PriorityQueue<(int U, long Cost)>((x, y) => x.Cost.CompareTo(y.Cost));
    queue.Enqueue((0, 0));
    var prev = new int[N];
    while (queue.Count > 0)
    {
        var (u, cu) = queue.Dequeue();
        if (costs[u] < cu) continue;
        foreach (var (v, cv) in G[u])
        {
            var c = costs[u] + cv;
            if (costs[v] <= c) continue;
            costs[v] = c;
            prev[v] = u;
            queue.Enqueue((v, c));
        }
    }

    var answer = new List<int>();
    for (var v = 1; v < N; v++)
    {
        var u = prev[v];
        answer.Add(dict[(u, v)]);
    }

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