ABC244

Published on Sunday, 20 March 2022

Updated on Monday, 21 March 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc244

問題A

コンテスト提出

文字列の長さがNなので、文字列のN-1のインデックスにアクセスすることで、末尾を参照することができます。
また、C#8.0以降の環境では配列に対してA[^i]のような記述をすることにより、後ろからi番目の要素を参照することができるので、これを使うことでも末尾を参照することができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = Scanner.Scan<string>();
    var answer = S[^1];
    Console.WriteLine(answer);
}

東西南北それぞれ移動するときのxとy移動量を用意し、現在の移動がどの向きに対して行われるかをインデックスとして管理することで簡単に記述することができます。
はじめの向きは東で、ti=Rならば右に90度回転するため、東、南、西、北、東、...の順番で向きが変化することがわかります。そのため、東、南、西、北の順で移動量を用意し、回転させたときに北の次は東になるようにインデックスを4で割ったあまりとすることでインデックスをループさせることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var T = Scanner.Scan<string>();
    var D4 = new[] { (1, 0), (0, -1), (-1, 0), (0, 1) }; // 東、南、西、北
    var (x, y) = (0, 0);
    var curr = 0;
    foreach (var c in T)
    {
        if (c == 'S')
        {
            x += D4[curr].Item1;
            y += D4[curr].Item2;
        }
        else
        {
            curr++;
            curr %= 4;
        }
    }

    Console.WriteLine($"{x} {y}");
}

問題C

コンテスト提出

インタラクティブな問題なので、出力を毎回Flushする必要があることに注意しましょう。
既に使った数字を記録しておき、まだ使っていない数字を出力すればよいです。
制約は1<=N<=1000なので、数字をすべて走査し使っていない数字を探す方法でもO(N^2)で間に合います。
また、Queueのようなデータ構造を使って、既に使用したものをDequeueしていくことで、O(N)で解答することもできます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var queue = new Queue<int>(Enumerable.Range(1, N * 2 + 1));
    var used = new bool[N * 2 + 2];
    while (true)
    {
        while (queue.Count > 0 && used[queue.Peek()]) queue.Dequeue();
        var x = queue.Dequeue();
        used[x] = true;
        Console.WriteLine(x);
        var y = Scanner.Scan<int>();
        if (y == 0)
        {
            return;
        }
        used[y] = true;
    }
}

問題D

コンテスト提出

SをRGBに並べ替えても対応するTは変わらないので、S=RGBとしたときのTを考えます。
このとき、Tがなりえる値はRGB、RBG、BRG、BGR、GRB、GBRの6通りしかありません。
S=RGBからそれぞれの値になるためのスワップ回数を見ると、

0回: RGB
1回: RBG、BGR、GRB
2回: RGB、BRG、GBR
3回: RBG、BGR、GRB
...

のように分類できます。
このことから、スワップのグループを奇数回、偶数回で分けることができ、ぴったり1e18回目にSがTになるようにスワップ操作をするには、Tが偶数グループに所属していることが条件となります。

実装では、SとTの対応する値が異なる数が2である(スワップ回数が1回)ときは答えはNoになり、それ以外の場合はYesとなるような実装を行いました。

public static void Solve()
{
    var (S1, S2, S3) = Scanner.Scan<char, char, char>();
    var (T1, T2, T3) = Scanner.Scan<char, char, char>();
    var S = new[] { S1, S2, S3 };
    var T = new[] { T1, T2, T3 };
    var x = 0;
    for (var i = 0; i < 3; i++)
    {
        if (S[i] != T[i]) x++;
    }

    var answer = x != 2;
    Console.WriteLine(answer ? "Yes" : "No");
}

問題E

コンテスト提出

dp[k][u][x] := k回目の移動で頂点uにいるとき、頂点Xに訪れた回数の偶奇(x)の通り数とした動的計画法を解いたときのdp[K][T][0]が答えとなります。

グラフにたいして状態を(現在の頂点、移動回数、頂点Xに訪れた回数の偶奇)として幅優先探索を行い、既に訪れた状態を重複して数えないようし、遷移先がXの場合は、遷移先のXの偶奇を変更し、それ以外の場合は遷移先の偶奇を変えずに遷移させます。 mintは指定したあまりを取った値を持つ整数型です。

public static void Solve()
{
    var (N, M, K, S, T, X) = Scanner.Scan<int, int, int, int, int, int>();
    S--; T--; X--;
    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 dp = new mint[K + 1, N, 2];
    dp[0, S, 0] = 1;
    var used = new bool[K + 1, N, 2];
    var queue = new Queue<(int U, int T, int X)>();
    queue.Enqueue((S, 0, 0));
    while (queue.Count > 0)
    {
        var (u, t, x) = queue.Dequeue();
        if (t == K || used[t, u, x]) continue;
        used[t, u, x] = true;
        foreach (var v in G[u])
        {
            if (v == X)
            {
                dp[t + 1, v, x ^ 1] += dp[t, u, x];
                queue.Enqueue((v, t + 1, x ^ 1));
            }
            else
            {
                dp[t + 1, v, x] += dp[t, u, x];
                queue.Enqueue((v, t + 1, x));
            }
        }
    }

    var answer = dp[K, T, 0];
    Console.WriteLine(answer);
}

問題F

コンテスト提出

状態sを(パスの状態, 頂点)としたときのパスの長さの最小値を考えます。これは、各頂点を始点として、現在の(パスの状態、頂点、パスの長さ)を持ち、状態sにおけるパスの最小値を記録しながら幅優先探索を行うことで、全ての状態を求めることができます。
このとき、現在のパスの長さが、記録されている状態sの長さよりも短い場合のみ探索することで、O(N^2*2^N)で探索することができます。
そして、全てのパスの状態における各頂点を終点としたときの長さがわかるので、各パスの状態ごとのパスの長さの最小値の和が求める答えとなります。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    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);
    }

    const int inf = (int)1e9;
    var dp = new int[1 << N, N];
    for (var i = 1; i < 1 << N; i++)
    {
        for (var j = 0; j < N; j++)
        {
            dp[i, j] = inf;
        }
    }

    var queue = new Queue<(int U, int S, int L)>();
    for (var i = 0; i < N; i++)
    {
        var s = 1 << i;
        var l = 1;
        dp[s, i] = l;
        queue.Enqueue((i, s, l));
        while (queue.Count > 0)
        {
            var (u, cs, cl) = queue.Dequeue();
            if (l > dp[cs, u]) continue;
            foreach (var v in G[u])
            {
                var ns = (cs >> v & 1) == 0 ? cs + (1 << v) : cs - (1 << v);
                var nl = cl + 1;
                if (nl >= dp[ns, v]) continue;
                dp[ns, v] = nl;
                queue.Enqueue((v, ns, nl));
            }
        }
    }

    var answer = 0;
    for (var i = 0; i < 1 << N; i++)
    {
        var min = inf;
        for (var j = 0; j < N; j++)
        {
            min = Math.Min(min, dp[i, j]);
        }

        answer += min;
    }
    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E

問題F