ABC261

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc261

問題A

コンテスト提出

0から100の範囲を全て見て、値xのときにどちらの色も塗られている(L1<=x<=R1 && L2<=x<=R1)場合の数を数え上げることで答えを求めることができます。 また、共通する範囲のうち、LはMax(L1,L2)、RはMin(R1,R2)で求められるので、Min(R1,R2)-Max(L1,L2)で答えを求めることができます。
この場合、L>Rになる場合があるので、0未満にならないように注意が必要です。

public static void Solve()
{
    var (L1, R1, L2, R2) = Scanner.Scan<int, int, int, int>();
    var answer = Math.Max(0, Math.Min(R1, R2) - Math.Max(L1, L2));
    Console.WriteLine(answer);
}

問題B

コンテスト提出

i!=jにおいて、表のi行j列を見たとき、表のj行i列の値が対応するものになっているかを判断します。

• A[i][j]==WのときA[j][i]==Lである。
• A[i][j]==LのときA[j][i]==Wである。
• A[i][j]==DのときA[j][i]==Dである。

全ての値が対応するものになっていればcorrect、そうでなければincorrectとなります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var answer = true;
    var A = new string[N];
    for (var i = 0; i < N; i++)
    {
        A[i] = Scanner.Scan<string>();
    }

    for (var i = 0; i < N; i++)
    {
        for (var j = i + 1; j < N; j++)
        {
            answer &= A[i][j] == 'W' && A[j][i] == 'L' ||
                      A[i][j] == 'L' && A[j][i] == 'W' ||
                      A[i][j] == 'D' && A[j][i] == 'D';
        }
    }

    Console.WriteLine(answer ? "correct" : "incorrect");
}

問題C

コンテスト提出

文字列が既に何回出ているかを愚直に探索してしまうと、1回の探索の時間計算量がO(N)、全体の時間計算量がO(N^2)となってしまい、実行時間制限に間に合いません。 辞書のようなデータ構造を使って文字列が何回出ているかを管理することで、データ構造の構築にO(logN)、値の取得にO(1)、全体の時間計算量をO(NlogN)に抑えることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var dict = new Dictionary<string, int>();
    for (var i = 0; i < N; i++)
    {
        var S = Scanner.Scan<string>();
        if (dict.ContainsKey(S))
        {
            Console.WriteLine($"{S}({dict[S]})");
            dict[S] += 1;
        }
        else
        {
            Console.WriteLine(S);
            dict[S] = 1;
        }
    }
}

問題D

コンテスト提出

コインの表裏の状態がN回あるので、あり得る場合の数は2^N通りとなり、全探索をしてしまうと時間計算量がO(2^N)となり実行時間制限内に答えを求めることはできません。
そこで、dp[i][j] := i回目のコイントスを終えてカウンタの数値がjのときのもらえる円の最大値とした動的計画法を解くことで時間計算量を抑えます。 X[i]をi回目のコイントスで表が出たときもらえる円、C[j]をカウンタの数値がjのときのボーナスでもらえる円としたとき、i+1回目への遷移は次のようになります。

• i回目のコイントスで表の時: Max(dp[i+1][j+1], dp[i][j]+X[i]+C[j+1])
• i回目のコイントスで裏の時: Max(dp[i+1][0], dp[i][j])

N回遷移が終わった後のそれぞれのカウンタ状態の最大値が答えとなり、全体の時間計算量はO(N^2)で求めることができます。

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

    var dp = new long[N + 1, N + 1];
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j <= i; j++)
        {
            dp[i + 1, j + 1] = Math.Max(dp[i + 1, j + 1], dp[i, j] + X[i] + C[j + 1]);
            dp[i + 1, 0] = Math.Max(dp[i + 1, 0], dp[i, j]);
        }
    }

    var answer = 0L;
    for (var i = 0; i <= N; i++)
    {
        answer = Math.Max(answer, dp[N, i]);
    }

    Console.WriteLine(answer);
}

問題E

復習提出

操作が全てビット演算なので、ビットごとに操作が独立していることがわかります。
k番目のビットが0と1の二通りの状態にi番目までの操作を累積したものを用意し、Cのk番目のビットの値にi番目まで累積した操作を適用したものが、i行目の答えのk番目ビット目になります。

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

    var answer = new int[N];
    for (var k = 0; k < 30; k++)
    {
        var bit = C >> k & 1;
        var cum = new int[] { 0, 1 };
        for (var i = 0; i < N; i++)
        {
            var (t, a) = Ops[i];
            var b = a >> k & 1;
            var f = new int[] { 0, 1 };
            for (var j = 0; j < 2; j++)
            {
                if (t == 1) f[j] &= b;
                if (t == 2) f[j] |= b;
                if (t == 3) f[j] ^= b;
            }

            for (var j = 0; j < 2; j++)
            {
                cum[j] = f[cum[j]];
            }

            bit = cum[bit];
            answer[i] |= bit << k;
        }
    }

    Console.WriteLine(string.Join("\n", answer));
}