ABC293

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc293

問題A

コンテスト提出

全ての奇数番目の文字と偶数番目の文字を入れ替えたものを出力します。 0-indexedの場合、偶数番目と奇数番目であることに注意が必要です。

public static void Solve()
{
    var S = Scanner.Scan<string>().ToCharArray();
    var N = S.Length;
    for (var i = 0; i < N / 2; i++)
    {
        (S[i * 2], S[i * 2 + 1]) = (S[i * 2 + 1], S[i * 2]);
    }

    var T = new string(S);
    Console.WriteLine(T);
}

問題B

コンテスト提出

1<=i<=Nについて、i番目の人が呼ばれているかを配列で保持しながら、iが呼ばれていなければA[i]を呼ぶという操作を行います。
そして、呼ばれていないiを列挙します。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var called = new bool[N];
    for (var i = 0; i < N; i++)
    {
        if (!called[i]) called[A[i] - 1] = true;
    }

    var answers = Enumerable.Range(0, N).Where(x => !called[x]).ToArray();
    Console.WriteLine(answers.Length);
    Console.WriteLine(string.Join(" ", answers.Select(x => x + 1)));
}

問題C

コンテスト提出

(1,1)から(H,W)に移動するために必要な移動回数は、右移動H-1回、下移動W-1回の計H+W-2回です。
右移動を0、下移動を1としたとき、2^(H+W-2)通りの移動方法をbit全探索し、右H-1回、下W-1回になる移動方法を調べます。 全体の時間計算量はO(2^(H+W-2)(H+W-2))となり、最大でも2^18*18==4718592の計算で済み、十分高速です。

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

    var K = H + W - 2;
    var answer = 0;

    for (var s = 0; s < 1 << K; s++)
    {
        var delta = new List<(int, int)>(K);
        for (var i = 0; i < K; i++)
        {
            if ((s >> i & 1) == 0) delta.Add((1, 0));
            else delta.Add((0, 1));
        }

        var ok = true;

        var set = new HashSet<long>();
        var (ch, cw) = (0, 0);
        set.Add((A[0][0]));
        foreach (var (dh, dw) in delta)
        {
            var (nh, nw) = (ch + dh, cw + dw);
            if (nh < 0 || H <= nh || nw < 0 || W <= nw || set.Contains(A[nh][nw]))
            {
                ok = false;
                break;
            }

            set.Add(A[nh][nw]);
            ch = nh;
            cw = nw;
        }

        if (ok)
        {
            answer++;
        }
    }

    Console.WriteLine(answer);
}

問題D

コンテスト提出

頂点aと頂点bが連結であり、頂点aと頂点cが連結であるとき、頂点bと頂点c間に辺を追加すると閉路ができます。
これは、DisjointSetUnionで高速に判定することができます。

問題について、各ロープには赤と青の区別された端があることから、赤と青の端をそれぞれ別の頂点としたとき、赤と青の頂点間に辺があると言えます。
あらかじめ各ロープの赤と青の頂点を連結し、各クエリごとにロープとその色に対応する頂点同士を閉路ができるかを判定しながら連結していくことで、環状になっているロープの組の数を数え上げることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var dsu = new DisjointSetUnion(N * 2);
    for (var i = 0; i < N; i++)
    {
        dsu.Merge(i * 2, i * 2 + 1);
    }

    var x = 0;
    for (var i = 0; i < M; i++)
    {
        var query = Scanner.ScanEnumerable<string>().ToArray();
        var (u, v) = ((int.Parse(query[0]) - 1) * 2, (int.Parse(query[2]) - 1) * 2);
        var (uc, vc) = (query[1], query[2]);
        if (uc == "B") u++;
        if (vc == "B") v++;
        if (dsu.IsSame(u, v)) x++;
        dsu.Merge(u, v);
    }

    var y = dsu.GetGroups().Count() - x;
    Console.WriteLine($"{x} {y}");
}