ABC235

Published on Saturday, 15 January 2022

Updated on Sunday, 16 January 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc235

問題A

コンテスト提出

各桁を移動させて足します。

public static void Solve()
{
    var V = Scanner.Scan<string>().Select(x => x - '0').ToArray();
    var answer = 0;
    answer += V[0] * 100 + V[1] * 10 + V[2];
    answer += V[1] * 100 + V[2] * 10 + V[0];
    answer += V[2] * 100 + V[0] * 10 + V[1];

    Console.WriteLine(answer);
}

問題B

コンテスト提出

順にみて前回より大きい場合はcurrを更新し、小さい場合は移動することができないため、currを表示します。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var H = Scanner.ScanEnumerable<long>().ToArray();
    var curr = 0L;
    for (var i = 0; i < N; i++)
    {
        if (curr < H[i])
        {
            curr = H[i];
        }
        else
        {
            Console.WriteLine(curr);
            return;
        }
    }

    Console.WriteLine(curr);
}

クエリのたびにすべてを走査するとO(N*Q)となりTLEになるので、高速化する必要があります。あらかじめ値をキーとした出現場所をもつ辞書を作成し、その値が何番目に出現するかを保持しておき、クエリによるxの値が存在して、kの値が辞書内に存在するxの個数以内ならばその出現場所を表示し、それ以外の場合は-1を表示することで、クエリ当たりO(logN)で実行することができるようになります。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var dict = new Dictionary<int, List<int>>();
    for (var i = 0; i < N; i++)
    {
        if (!dict.ContainsKey(A[i])) dict[A[i]] = new List<int>();
        dict[A[i]].Add(i + 1);
    }

    while (Q-- > 0)
    {
        var (x, k) = Scanner.Scan<int, int>();
        k--;
        if (dict.ContainsKey(x))
        {
            if (k < dict[x].Count)
            {
                Console.WriteLine(dict[x][k]);
            }
            else
            {
                Console.WriteLine(-1);
            }
        }
        else
        {
            Console.WriteLine(-1);
        }
    }
}

問題D

コンテスト提出

各操作をBFSで走査することにより、各値の更新は高々1回のみで十分になります。
シフト操作によって、Nの値より大きい数からNより小さい値に変化する可能性もあるので、Nを文字列としてみたときの長さより大きい場合は無視することに注意します。
Shiftメソッドは配列を与えられた値だけシフトする関数です。

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

    var queue = new Queue<long>();
    queue.Enqueue(1);
    const int inf = (int)1e7;

    void Push(long curr, long next)
    {
        if (next > inf) return;
        if (dp.ContainsKey(next)) return;
        dp[next] = dp[curr] + 1;
        queue.Enqueue(next);
    }

    while (queue.Count > 0)
    {
        var u = queue.Dequeue();
        if (u >= 10 && u % 10 != 0)
        {
            var v = long.Parse(Shift(u.ToString().AsSpan(), 1));
            Push(u, v);
        }
        Push(u, u * A);
    }
    
    if (dp.ContainsKey(N))
    {
        Console.WriteLine(dp[N]);
    }
    else
    {
        Console.WriteLine(-1);
    }
}

問題E

コンテスト提出

クエリごとに最小全域木を求めると、ソートに(MlogM)、クラスカル法で最小全域木を求めるためにO(Ea(V))となり、TLEになってしまいます。クエリに対してグラフはそれぞれ独立なため、あらかじめクエリを先読みしてすべての辺をまとめてソートし、クラスカル法で辺を見てその辺が有効な場合、もしその辺がクエリの辺である場合はそのクエリは有効であり、そうではない場合は最小全域木としてマージしていくことで、計算量を抑えることができます。

public static void Solve()
{
    var (N, M, Q) = Scanner.Scan<int, int, int>();
    var E1 = new Edge[M];
    var E2 = new Edge[Q];
    for (var i = 0; i < M; i++)
    {
        var (a, b, c) = Scanner.Scan<int, int, int>();
        a--; b--;
        E1[i] = new Edge(-1, a, b, c);
    }

    for (var i = 0; i < Q; i++)
    {
        var (a, b, c) = Scanner.Scan<int, int, int>();
        a--; b--;
        E2[i] = new Edge(i, a, b, c);
    }

    var answer = new bool[Q];
    var dsu = new DisjointSetUnion(N);
    foreach (var e in E1.Concat(E2).OrderBy(x => x.Cost))
    {
        if (dsu.IsSame(e.U, e.V)) continue;
        if (e.ID == -1)
        {
            dsu.Merge(e.U, e.V);
        }
        else
        {
            answer[e.ID] = true;
        }
    }

    Console.WriteLine(string.Join("\n", answer.Select(x => x ? "Yes" : "No")));
}

問題F

復習提出

コンテスト中の考察です。

桁dp?
1<<10(1024)通りの場合分け?
総和の数え方がわからない...

var dp = new mint[N + 1, 1 << 10];
for(var i = 0; i < S.Length; i++)
{
    for(var j = 0; j < 1 << 10; j++)
    {
        for(var k = 0; k < 10; k++)
        {
            // dp[i + 1, j | (1 << k)] = ?;
        }
    }
}

解説では、総和と個数をそれぞれ別に数え上げるそうです。 mintは、あまりをとる整数型です。

public static void Solve()
{
    var V = Scanner.Scan<string>().Select(x => x - '0').ToArray();
    var N = V.Length;
    var M = Scanner.Scan<int>();
    var C = Scanner.ScanEnumerable<int>().ToArray();

    var ok = 0;
    foreach (var c in C)
    {
        ok |= 1 << c;
    }

    var max = 1 << 10;
    var count = new mint[2][] { new mint[max], new mint[max] };
    var sum = new mint[2][] { new mint[max], new mint[max] };
    mint curr = 0;
    var digits = 0;

    var t = 1;
    for (var i = 0; i < N; i++)
    {
        t ^= 1;
        var tt = t ^ 1;
        var c = V[i];
        Array.Fill(count[tt], 0);
        Array.Fill(sum[tt], 0);
        for (var j = 0; j < max; j++)
        {
            for (var d = 0; d < 10; d++)
            {
                var next = j | (1 << d);
                count[tt][next] += count[t][j];
                sum[tt][next] += sum[t][j] * 10 + count[t][j] * d;
            }
        }

        if (i > 0)
        {
            for (var d = 1; d < 10; d++)
            {
                var next = 1 << d;
                count[tt][next]++;
                sum[tt][next] += d;
            }
        }

        for (var d = 0; d < c; d++)
        {
            if (i == 0 && d == 0) continue;
            var next = digits | (1 << d);
            count[tt][next]++;
            sum[tt][next] += curr * 10 + d;
        }

        digits |= 1 << c;
        curr = curr * 10 + c;
    }

    t ^= 1;
    var answer = 0L;
    for (var j = 0; j < max; j++)
    {
        if ((j & ok) == ok)
        {
            answer += sum[t][j];
        }
    }

    if ((digits & ok) == ok)
    {
        answer += curr;
    }

    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E

問題F