ABC270

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc270

問題A

コンテスト提出

整数を2進数表記したとき、2^0==1、2^1==2、2^2=4となり、入力AとBの各ビットが立っているかをみることで、その問題に正解しているかどうかがわかります。 そのため、AとBの各ビットの論理和をとることで、答えを求めることができます。

public static void Solve()
{
    var (A, B) = Scanner.Scan<int, int>();
    var C = A | B;
    Console.WriteLine(C);
}

問題B

コンテスト提出
復習提出

Xが負のとき、X、Y、Zを反転させることでXが正の時として考えることができます。
このとき、X<YまたはY<0であれば、0からXの間に壁はないので、答えはXとなります。 それ以外のとき、Y<Zであれば、ハンマーを拾うことはできないので、答えは-1となります。 それ以外のとき、ハンマーを拾ってからXに向かうことができるので、答えはAbs(Z)+Abs(X-Z)となります。

public static void Solve()
{
    var (X, Y, Z) = Scanner.Scan<int, int, int>();
    if (X < 0)
    {
        X = -X;
        Y = -Y;
        Z = -Z;
    }

    if (X < Y || Y < 0)
    {
        Console.WriteLine(X);
    }
    else
    {
        if (Y < Z)
        {
            Console.WriteLine(-1);
        }
        else
        {
            Console.WriteLine(Math.Abs(Z) + Math.Abs(X - Z));
        }
    }
}

問題C

コンテスト提出

訪れた直前の頂点をメモしながら、始点であるXから幅優先探索を行い、終点のYから直前の頂点をたどることでパスを復元することができます。 復元した頂点は逆順であることに注意が必要です。

public static void Solve()
{
    var (N, X, Y) = Scanner.Scan<int, int, int>();
    X--; Y--;
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();
    for (var i = 0; i < N - 1; i++)
    {
        var (u, v) = Scanner.Scan<int, int>();
        u--; v--;
        G[u].Add(v);
        G[v].Add(u);
    }

    var prev = new int[N];
    Array.Fill(prev, -1);
    var queue = new Queue<int>();
    queue.Enqueue(X);
    while (queue.Count > 0)
    {
        var u = queue.Dequeue();
        foreach (var v in G[u])
        {
            if (prev[v] != -1) continue;
            prev[v] = u;
            queue.Enqueue(v);
        }
    }

    var route = new List<int>();
    var curr = Y;
    while (true)
    {
        route.Add(curr + 1);
        curr = prev[curr];
        if(curr == X) break;
    }

    route.Reverse();
    Console.WriteLine(string.Join(" ", route));
}

問題D

復習提出

dp[i]:=石がi個のときの先手が取れる石の最大個数とした動的計画法をときます。 遷移としては、石がi-A[j]個のときの後手が取れる石の最大個数にA[j]個足したものであることに注意が必要です。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var dp = new int[N + 1];
    for (var i = 0; i <= N; i++)
    {
        for (var j = 0; j < K; j++)
        {
            if (i - A[j] >= 0)
            {
                dp[i] = Math.Max(dp[i], (i - A[j] - dp[i - A[j]]) + A[j]);
            }
        }
    }

    var answer = dp[N];
    Console.WriteLine(answer);
}

問題E

コンテスト提出

愚直にシミュレーションしてしまうと実行時間制限に間に合いません。 現在のかごにあるりんごの最小値がv、りんごが1個以上あるかごの数をcのときにはMin(K/c,v)周することができ、りんごはMin(K/c,v)周*c個食べることができます。 そして、食べられるKが現在のりんごが1個以上あるかごの数未満になった場合は端数となるので、りんごが1個以上あるかごの番号が小さい順に数を減らすことで答えを求めることができます。 全体計算量はりんごの数をソートするためのO(NlogN)となり、実行時間制限に間に合います。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, long>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    var basket = N;
    var lap = 0L;
    foreach (var v in A.OrderBy(x => x))
    {
        if (K < basket) break;
        var d = Math.Min(K / basket, v - lap);
        K -= d * basket;
        lap += d;
        basket--;
    }

    for (var i = 0; i < N; i++)
    {
        A[i] = Math.Max(0, A[i] - lap);

        if (A[i] > 0 && K > 0)
        {
            A[i]--;
            K--;
        }
    }

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