ABC289

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc289

問題A

コンテスト提出

各文字の排他的論理和(XOR)を取ることで、0と1を反転させることができます。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var answer = string.Join("", S.Select(x => (x - '0') ^ 1));
    Console.WriteLine(answer);
}

問題B

コンテスト提出

各aの前にa+1を読む必要があるので、aからa+1に対する有効辺を繋いだグラフを作成し、各連結成分の葉から順に読み上げたものが答えとなります。
これは、各連結成分ごとに深さ優先探索を行うことで求めることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();
    foreach (var a in A)
    {
        var b = a + 1;
        G[a].Add(b);
    }

    var answer = new List<int>(N);
    var used = new bool[N];
    void Dfs(int u)
    {
        foreach (var v in G[u])
        {
            Dfs(v);
        }

        answer.Add(u);
        used[u] = true;
    }

    for (var i = 0; i < N; i++)
    {
        if (!used[i]) Dfs(i);
    }

    Console.WriteLine(string.Join(" ", answer.Select(x => x + 1)));
}

問題C

コンテスト提出

集合の数が1<=M<=10と少ないので、2^M-1通りの集合の組み合わせをbit全探索で走査し、1<=x<=Nの全てのxが組み合わせの集合のうちいずれかに存在しているかを調べます。

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

    var answer = 0;
    for (var s = 1; s < 1 << M; s++)
    {
        var exists = new int[N + 1];
        for (var i = 0; i < M; i++)
        {
            if ((s >> i & 1) == 0) continue;
            foreach (var a in A[i])
            {
                exists[a] = true;
            }
        }
        
        var ok = Enumerable.Range(1, N).All(x => exists[x]);
        if (ok) answer++;
    }

    Console.WriteLine(answer);
}

問題D

コンテスト提出

次のような動的計画法を解きます。

dp[i] := i段目に上ることができるか

遷移としては次のようになります。

i段目にもちが設置されている場合、その段からは移動できない。

i段目にもちが設置されていない場合、各A[j](1<=j<=N)において、i+A[j]段に移動できる。
dp[i+A[j]] |= dp[i]

i段目にもちが設置されているかを時間計算量O(1)で求められるようにしておくことで、時間計算量は全体でO(XN)で求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var M = Scanner.Scan<int>();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var X = Scanner.Scan<int>();
    var dp = new bool[X + 1];
    dp[0] = true;
    var mochi = new bool[X + 1];
    foreach (var b in B)
    {
        mochi[b] = true;
    }

    for (var i = 0; i < X; i++)
    {
        if (mochi[i]) continue;
        foreach (var a in A.Where(x => i + x <= X))
        {
            dp[i + a] |= dp[i];
        }
    }

    var answer = dp[X];
    Console.WriteLine(answer ? "Yes" : "No");
}

問題E

コンテスト提出

各クエリにおいてグラフを構築し、高橋君が頂点u、青木君が頂点vにいるときの最小の移動回数を幅優先探索で求めます。

public static void Solve()
{
    var T = Scanner.Scan<int>();
    var queue = new Queue<(int, int)>();
    while (T-- > 0)
    {
        var (N, M) = Scanner.Scan<int, int>();
        var C = Scanner.ScanEnumerable<int>().ToArray();
        var G = new List<int>[N].Select(x => new List<int>()).ToArray();
        for (var i = 0; i < M; i++)
        {
            var (u, v) = Scanner.Scan<int, int>();
            u--; v--;
            G[u].Add(v);
            G[v].Add(u);
        }

        var costs = new int[N, N];
        for (var i = 0; i < N; i++)
        {
            for (var j = 0; j < N; j++)
            {
                costs[i, j] = -1;
            }
        }

        costs[0, N - 1] = 0;
        queue.Enqueue((0, N - 1));
        while (queue.Count > 0)
        {
            var (u1, u2) = queue.Dequeue();
            foreach (var v1 in G[u1])
            {
                foreach (var v2 in G[u2])
                {
                    if (C[v1] == C[v2]) continue;
                    if (costs[v1, v2] != -1) continue;
                    costs[v1, v2] = costs[u1, u2] + 1;
                    queue.Enqueue((v1, v2));
                }
            }
        }

        var answer = costs[N - 1, 0];
        Console.WriteLine(answer);
    }
}