ABC257

Published on Saturday, 25 June 2022

Updated on Saturday, 25 June 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc257

問題A

コンテスト提出

長さN*26の文字列のX番目の文字は何かと言い換えられるので、Xを0-indexedに変換したX-1番目をNで割った番目のアルファベットが答えとなります。

public static void Solve()
{
    var (N, X) = Scanner.Scan<int, int>();
    var answer = (char)((X - 1) / N + 'A');
    Console.WriteLine(answer);
}

問題B

コンテスト提出

Aの位置と番号のペアとして位置を昇順にソートしたものをB、駒のあるマスをX、各クエリをl番目の駒に対する操作としたとき、

l+1<Kのとき、B[l]のXとB[l+1]のXが隣り合っていなければB[l]のXを+1する。
l==Kのとき、B[l]のXがN未満であればB[l]のXを+1する。

のように操作し、すべての操作が終わったときのXが答えとなります。

public static void Solve()
{
    var (N, K, Q) = Scanner.Scan<int, int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var L = Scanner.ScanEnumerable<int>().ToArray();
    var B = A.Select((x, i) => (x, i)).ToArray();
    Array.Sort(B, (x, y) => x.x.CompareTo(y.x));
    foreach (var l in L.Select(x => x - 1))
    {
        if (l + 1 < K)
        {
            if (B[l].x + 1 != B[l + 1].x) B[l].x++;
        }
        else
        {
            if (B[l].x < N) B[l].x++;
        }
    }

    Console.WriteLine(string.Join(" ", B.Select(x => x.x)));
}

X=0のときf(X)=大人の数であり、X=infinityのときf(X)=子供の数であることから、答えは最小でもMax(f(0), f(1e9+1))であることがわかります。そして、子供と大人の座標を別々に管理しそれぞれを昇順でソートしておくことで、体重X未満の子供の数と体重X以上の大人の数を二部探索で調べることができるようになるので、境界としてありえるN人全てのWについて調べることで答えを求めることができます。計算量は子供と大人の分類にO(N)、ソートに(NlogN)、各クエリごとにO(logN)なので、全体でO(NlogN)で答えを求めることができます。

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

    var child = new List<int>();
    var adult = new List<int>();
    for (var i = 0; i < N; i++)
    {
        (S[i] == '0' ? child : adult).Add(W[i]);
    }

    child.Sort();
    adult.Sort();

    var answer = Math.Max(child.Count, adult.Count);
    foreach (var w in W)
    {
        var c1 = LowerBound(child, w);
        var c2 = adult.Count - LowerBound(adult, w);
        answer = Math.Max(answer, c1 + c2);
    }

    Console.WriteLine(answer);
}

問題D

コンテスト提出

各始点について、全てのジャンプ台に移動可能な最小のSについて二部探索をおこない、その最小を求めます。二部探索の判定式として、始点から幅優先探索を行うことでO(N^2)で全てのジャンプ台に移動可能かを判定することができます。全体計算量O(N^3logN)で答えを求めることができます。あるジャンプ台から別のジャンプ台へ移動可能か判定する際に、P*S>=|x0-x1|+|y0-x1|の右辺は最大で4e9であることに注意しましょう。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var Jumps = new Jump[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y, p) = Scanner.Scan<long, long, long>();
        Jumps[i] = new Jump(x, y, p);
    }

    bool CanMove(Jump from, Jump to, long s)
    {
        var d = Math.Abs(from.X - to.X) + Math.Abs(from.Y - to.Y);
        return s >= d || from.P * s >= d;
    }

    const long inf = (long)4e9;
    var answer = inf;
    for (var k = 0; k < N; k++)
    {
        bool F(long s)
        {
            var queue = new Queue<Jump>();
            var used = new bool[N];

            used[k] = true;
            queue.Enqueue(Jumps[k]);

            while (queue.Count > 0)
            {
                var u = queue.Dequeue();
                for (var i = 0; i < N; i++)
                {
                    if (!used[i] && CanMove(u, Jumps[i], s))
                    {
                        used[i] = true;
                        queue.Enqueue(Jumps[i]);
                    }
                }
            }

            return used.All(x => x);
        }

        var s = BinarySearch(-1, inf, F);
        answer = Math.Min(answer, s);
    }

    Console.WriteLine(answer);
}

public readonly struct Jump
{
    public readonly long X;
    public readonly long Y;
    public readonly long P;
    public Jump(long x, long y, long p) => (X, Y, P) = (x, y, p);
}

public static long BinarySearch(long ng, long ok, Func<long, bool> func)
{
    while (Math.Abs(ok - ng) > 1)
    {
        var m = (ok + ng) / 2;
        if (func(m)) ok = m;
        else ng = m;
    }

    return ok;
}

問題E

復習提出

Cの最小をminとしたとき、桁数は最大でもN/minになります。その桁数が構成できるもののうち、ある桁の値dは、C[d]とその桁より右側をminにしたときの和であり、その和がその時点で採用することができれば、その桁をdとすることができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var C = Scanner.ScanEnumerable<long>().ToArray();

    var min = C.Min();
    var length = N / min;
    var builder = new StringBuilder();
    for (var i = 0; i < length; i++)
    {
        for (var d = 9; d >= 1; j--)
        {
            if (min * (length - 1 - i) + C[d - 1] <= N)
            {
                N -= C[d - 1];
                builder.Append((char)(d + '0'));
                break;
            }
        }
    }

    var answer = builder.ToString();
    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E