ABC301

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc301

問題A

コンテスト提出

勝った試合の数が多い方が総合勝者ということは、総合勝者は半分以上の試合で勝っていることになります。 また、勝ち数が同じ場合は先にその勝ち数に達したものが総合勝者となるので、順に勝ち数を数え上げ、先に過半数を取得した方が総合勝者になります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = Scanner.Scan<string>();
    var t = 0;
    var a = 0;
    foreach (var c in S)
    {
        if (c == 'T') t++;
        else a++;
        if (t * 2 >= N)
        {
            Console.WriteLine("T");
            return;
        }
        else if (a * 2 >= N)
        {
            Console.WriteLine("A");
            return;
        }
    }
}

問題B

コンテスト提出

数列の1項目はAの1項目になります。
Aの2項目以降を考えます。 数列に最後に追加した値をx、Aの次の項をaとしたとき、

• x<aの間は、次にx+1を追加する。
• x>aの間は、次にx-1を追加する。
• x==aの場合は、aをAの次の項に更新する。

という操作を繰り返すことで、答えとなる数列を生成することができます。

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

    IEnumerable<int> F()
    {
        var x = A[0];
        yield return x;
        foreach (var a in A.Skip(1))
        {
            while (x < a) yield return ++x;
            while (x > a) yield return --x;
        }
    }

    Console.WriteLine(string.Join(" ", F()));
}

問題C

コンテスト提出

二つの文字列を構成する文字の個数が全て一致する必要があります。 atcoderの各文字の個数が一致しない場合、少ない方の個数をその文字列にある@の個数以内で補うことができます。 補う操作を行ったうえでatcoderの文字の個数が一致し、ほかの文字の個数もすべて一致した場合のみ答えはYesになります。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var T = Scanner.Scan<string>();
    var N = S.Length;

    int[] F(string str)
    {
        var used = new int[27];
        foreach (var c in str)
        {
            if (c == '@') used[26]++;
            else used[c - 'a']++;
        }

        return used;
    }

    var usedS = F(S);
    var usedT = F(T);
    var answer = true;

    bool G(int i)
    {
        foreach (var c in "atcoder")
        {
            if (c - 'a' == i) return true;
        }

        return false;
    }

    for (var i = 0; i < 26; i++)
    {
        var s = usedS[i];
        var t = usedT[i];
        if (s == t) continue;
        if (G(i))
        {
            if (s > t)
            {
                var d = s - t;
                answer &= usedT[26] >= d;
                usedT[26] -= d;
            }
            else
            {
                var d = t - s;
                answer &= usedS[26] >= d;
                usedS[26] -= d;
            }
        }
        else
        {
            answer = false;
            break;
        }
    }

    Console.WriteLine(answer ? "Yes" : "No");
}

問題D

コンテスト提出

?の部分を全て0にした値がNより大きい場合、答えは-1となります。 それ以外の場合、桁の大きいところから順にみていき、その?を1にした値がN以下であるかを判定していくことで答えを求めることができます。

public static void Solve()
{
    var S = Scanner.Scan<string>().ToCharArray();
    var N = Scanner.Scan<long>();

    long answer = 0;
    for (var i = 0; i < S.Length; i++)
    {
        if (S[i] != '?') answer |= (long)(S[i] - '0') << (S.Length - 1 - i);
    }

    if (answer > N)
    {
        Console.WriteLine(-1);
        return;
    }

    for (var i = 0; i < S.Length; i++)
    {
        if (S[i] != '?') continue;
        var v = answer | (1L << (S.Length - 1 - i));
        if (v <= N) answer = v;
    }

    Console.WriteLine(answer);
}

問題E

復習提出

スタートマスからゴールマスの最小移動回数がTより大きいとき、答えは-1になります。 それ以外のとき、次のような動的計画法を解きます。

dp[s][u] := 訪れたお菓子のマスの集合がs、現在値がお菓子のマスがuのときの最小移動回数

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

初期値:
dp[1<<u][u] = スタートマスからお菓子のマスuへの最小移動回数

遷移:
訪れたお菓子のマスの集合がs、お菓子のマスuからお菓子のマスvにD(u,v)の移動回数がかかるとき、
dp[s|(1<<v)][v] = Min(dp[s|(1<<v)][v], dp[s][u]+D(u,v))

そして、各状態からゴールマスへの移動回数を足したものがT回以下であるときの訪れたお菓子のマスの個数の最大値が答えとなります。
お菓子のマスの個数をMとすると、各お菓子のマスを始点とした幅優先探索を行うことで、D(u,v)は時間計算量O(MHW)で求めることができます。 よって、時間計算量O(MHW+(2^M)*M^2)で答えを求めることができます。

public static void Solve()
{
    var (H, W, T) = Scanner.Scan<int, int, int>();
    var A = new char[H][];
    var G = new bool[H][];
    var (sh, sw) = (0, 0);
    var (gh, gw) = (0, 0);
    var map = new Dictionary<(int, int), int>();
    var M = 0;
    var snacks = new List<(int H, int W)>();

    for (var i = 0; i < H; i++)
    {
        A[i] = Scanner.Scan<string>().ToCharArray();
        G[i] = new bool[W];
        for (var j = 0; j < W; j++)
        {
            if (A[i][j] == 'S') (sh, sw) = (i, j);
            if (A[i][j] == 'G') (gh, gw) = (i, j);
            if (A[i][j] == 'o')
            {
                map[(i, j)] = M++;
                snacks.Add((i, j));
            }

            G[i][j] = A[i][j] != '#';
        }
    }

    var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
    const int Inf = (int)1e9;

    int[][] GetDistance(int h, int w)
    {
        var result = new int[H][];
        for (var i = 0; i < H; i++)
        {
            result[i] = new int[W];
            for (var j = 0; j < W; j++)
            {
                result[i][j] = Inf;
            }
        }

        result[h][w] = 0;
        var queue = new Queue<(int, int)>();
        queue.Enqueue((h, w));
        while (queue.Count > 0)
        {
            var (ch, cw) = queue.Dequeue();
            foreach (var (dh, dw) in D4)
            {
                var (nh, nw) = (ch + dh, cw + dw);
                if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
                if (!G[nh][nw] || result[nh][nw] != Inf) continue;
                result[nh][nw] = result[ch][cw] + 1;
                queue.Enqueue((nh, nw));
            }
        }

        return result;
    }

    var startToGoal = GetDistance(sh, sw)[gh][gw];
    if (startToGoal > T)
    {
        Console.WriteLine(-1);
        return;
    }

    var snackDistances = new int[M][][];
    for (var k = 0; k < M; k++)
    {
        var (h, w) = snacks[k];
        snackDistances[k] = GetDistance(h, w);
    }

    var dp = new int[1 << M, M];
    for (var i = 0; i < 1 << M; i++)
    {
        for (var j = 0; j < M; j++)
        {
            dp[i, j] = Inf;
        }
    }

    for (var u = 0; u < M; u++)
    {
        dp[1 << u, u] = snackDistances[u][sh][sw];
    }

    for (var cs = 0; cs < 1 << M; cs++)
    {
        for (var u = 0; u < M; u++)
        {
            if ((cs >> u & 1) == 0) continue;
            for (var v = 0; v < M; v++)
            {
                if ((cs >> v & 1) == 1) continue;
                var (nh, nw) = snacks[v];
                var nd = dp[cs, u] + snackDistances[u][nh][nw];
                var ns = cs | (1 << v);
                dp[ns, v] = Math.Min(dp[ns, v], nd);
            }
        }
    }

    var answer = 0;
    for (var s = 0; s < 1 << M; s++)
    {
        for (var u = 0; u < M; u++)
        {
            var gd = dp[s, u] + snackDistances[u][gh][gw];
            if (gd <= T)
            {
                var count = 0;
                for (var i = 0; i < M; i++)
                {
                    count += (s >> i) & 1;
                }

                answer = Math.Max(answer, count);
            }
        }
    }

    Console.WriteLine(answer);
}