ABC271

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc271

問題A

コンテスト提出

C#では、整数を文字列に変換するときに、書式指定子Xを指定することで16進数文字列に変換することができ、書式指定子の後に数字を加えることで桁数を指定できます。 16 進書式指定子 (X)

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

問題B

コンテスト提出

全ての配列を、配列の配列として保持しておき、s番目の配列の、t番目の値を出力します。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var A = new int[N][];
    for (var i = 0; i < N; i++)
    {
        var line = Scanner.ScanEnumerable<int>().ToArray();
        A[i] = line[1..];
    }

    while (Q-- > 0)
    {
        var (s, t) = Scanner.Scan<int, int>();
        s--;
        t--;
        Console.WriteLine(A[s][t]);
    }
}

問題C

復習提出

x巻まで読むことができるかという二部探索を行います。 判定式としては、持っている単行本のうち重複を除いたx以下の巻数をc1、xより大きい巻数や重複した2冊目以降の数をc2 (c2==N-c1)としたとき、足りない数の2倍がc2以下であるか(x-c1)*2<=c2を判定します。

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

    bool F(int x)
    {
        var c1 = A.Count(v => v <= x);
        var c2 = N - c1;
        return (x - c1) * 2 <= c2;
    }

    var answer = BinarySearch((int)1e9, 0, F);
    Console.WriteLine(answer);
}

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

    return ok;
}

問題D

コンテスト提出

dp[i,j,k]:=i番目までのカードみたとき状態がk(表裏)のときにの合計がjが成り立つかという動的計画法をとき、dp[N,S,0]かdp[N,S,1]が成り立つかを判定し、成り立つときは経路復元を行います。 経路復元では、dp[i,j,k]が成り立つときのi-1番目のjとkをメモしておきます。

public static void Solve()
{
    var (N, S) = Scanner.Scan<int, int>();
    var dp = new bool[N + 1, S + 1, 2];
    var prev = new (int, int)[N + 1, S + 1, 2];
    dp[0, 0, 0] = dp[0, 0, 1] = true;

    for (var i = 0; i < N; i++)
    {
        var (a, b) = Scanner.Scan<int, int>();
        for (var j = 0; j <= S; j++)
        {
            if (j + a <= S)
            {
                for (var k = 0; k < 2; k++)
                {
                    if (dp[i, j, k])
                    {
                        dp[i + 1, j + a, 0] |= dp[i, j, k];
                        prev[i + 1, j + a, 0] = (j, k);
                    }
                }
            }

            if (j + b <= S)
            {
                for (var k = 0; k < 2; k++)
                {
                    if (dp[i, j, k])
                    {
                        dp[i + 1, j + b, 1] |= dp[i, j, k];
                        prev[i + 1, j + b, 1] = (j, k);
                    }
                }
            }
        }
    }

    if (dp[N, S, 0] || dp[N, S, 1])
    {
        var list = new List<int>();
        var curr = dp[N, S, 0] ? (S, 0) : (S, 1);
        for (var i = N; i > 0; i--)
        {
            list.Add(curr.Item2);
            curr = prev[i, curr.Item1, curr.Item2];
        }

        list.Reverse();
        var answer = string.Join("", list.Select(x => x == 0 ? 'H' : 'T'));
        Console.WriteLine("Yes");
        Console.WriteLine(answer);
    }
    else
    {
        Console.WriteLine("No");
    }
}

問題E

復習提出

dp[i][j]:=Eのi番目までの道を使った時の都市jへの最小コストとした動的計画法をときます。 良い経路はEの部分列であり、E[1]->E[2]やE[1]->E[3]のようなことも可能であるため、iごとにコストを保持する必要はなく、一次元のみで求めることができます。

public static void Solve()
{
    var (N, M, K) = Scanner.Scan<int, int, int>();
    var G = new List<(int, long)>[N].Select(x => new List<(int, long)>()).ToArray();
    const long inf = (long)1e18;
    var Edges = new (int U, int V, long C)[M];
    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));
        Edges[i] = (a, b, c);
    }

    var E = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
    var dp = new long[N];
    Array.Fill(dp, inf);
    dp[0] = 0;

    for (var i = 0; i < K; i++)
    {
        var (a, b, c) = Edges[E[i]];
        if (dp[a] != inf)
        {
            dp[b] = Math.Min(dp[b], dp[a] + c);
            set.Add(b);
        }
    }

    var answer = dp[N - 1];
    if (answer == inf) answer = -1;
    Console.WriteLine(answer);
}