ABC268

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc268

問題A

コンテスト提出

0から100までの長さ101のbool配列を用意して、与えられた整数の位置をtrueにし、そのtrueの数を数え上げます。

public static void Solve()
{
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var exists = new bool[101];
    for (var i = 0; i < 5; i++)
    {
        exists[A[i]] = true;
    }
    var answer = exists.Count(x => x);
    Console.WriteLine(answer);
}

問題B

コンテスト提出

Sの長さ>Tの長さの場合はfalseであり、それ以外の時にSの長さの範囲で文字がすべて一致するかを判断します。
C#では、String.StartWithメソッドで引数に与えられた文字列で文字列が始まっているかを判断できます。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var T = Scanner.Scan<string>();
    var answer = T.StartsWith(S);
    Console.WriteLine(answer ? "Yes" : "No");
}

問題C

コンテスト提出

始点を全探索して全ての値がi-1、i、i+1のいずれかの目の前にあるかを探索してしまうと、時間計算量がO(N^2)となり実行時間制限に間に合いません。 そこで、人iと料理P[i]の距離(P[i]-i)%Nの個数に変換することで、距離d-1、d、d+1にある個数の和の最大値を求める問題に変換することで、時間計算量O(N)で答えを求めることができます。

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

    var count = new int[N];
    for (var i = 0; i < N; i++)
    {
        count[(P[i] - i + N) % N]++;
    }

    var answer = 0;
    for (var i = 0; i < N; i++)
    {
        var c = 0;
        for (var j = 0; j < 3; j++)
        {
            c += count[(i + j) % N];
        }

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

    Console.WriteLine(answer);
}

問題D

復習提出

N個の文字列の順列として並べ替えたものの間に1以上の任意の数の_を追加した文字列を全て列挙し、M個の文字列に存在しない文字列があるかどうかを判定します。 _を追加する文字列を生成する方法として、現在の_の個数、現在_を追加しようとしてる位置、残りの追加できる_の数を管理しながら深さ優先探索を行うことができます。 また、N=1の時がコーナーケースで、3文字以上16文字以下であることの確認が必要です。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var S = new string[N];
    var remains = 16 - (N - 1);
    for (var i = 0; i < N; i++)
    {
        S[i] = Scanner.Scan<string>();
        remains -= S[i].Length;
    }

    var T = new HashSet<string>();
    for (var i = 0; i < M; i++)
    {
        var s = Scanner.Scan<string>();
        T.Add(s);
    }

    if (N == 1)
    {
        Console.WriteLine(!T.Contains(S[0]) && 3 <= S[0].Length && S[0].Length <= 16 ? S[0] : "-1");
        return;
    }

    var set = new HashSet<string>();
    var count = new int[N - 1];
    Array.Fill(count, 1);
    foreach (var perm in Enumerable.Range(0, N).Permute(N))
    {
        void Dfs(int curr, int rem)
        {
            if (rem < 0) return;
            if (curr >= N - 1)
            {
                var builder = new StringBuilder();
                for (var i = 0; i < N; i++)
                {
                    builder.Append(S[perm[i]]);
                    if (i < N - 1) builder.Append('_', count[i]);
                }

                var x = builder.ToString();
                set.Add(x);
                return;
            }

            for (var k = 0; k <= rem; k++)
            {
                count[curr] += k;
                Dfs(curr + 1, rem - k);
                count[curr] -= k;
            }
        }

        Dfs(0, remains);
    }

    foreach (var x in set)
    {
        if (!T.Contains(x))
        {
            Console.WriteLine(x);
            return;
        }
    }

    Console.WriteLine("-1");
}

以下のような順列を列挙するメソッドを使用しました。

public static partial class EnumerableExtension
{
    public static IEnumerable<TSource[]> Permute<TSource>(this IEnumerable<TSource> source, int count)
    {
        if (source is null) throw new ArgumentNullException(nameof(source));
        IEnumerable<TSource[]> Inner()
        {
            var items = source.ToArray();
            if (count <= 0 || items.Length < count) throw new ArgumentOutOfRangeException(nameof(count));
            var n = items.Length;
            var indices = new int[n];
            for (var i = 0; i < indices.Length; i++)
            {
                indices[i] = i;
            }
            var cycles = new int[count];
            for (var i = 0; i < cycles.Length; i++)
            {
                cycles[i] = n - i;
            }
            TSource[] Result()
            {
                var result = new TSource[count];
                for (var i = 0; i < count; i++)
                {
                    result[i] = items[indices[i]];
                }
                return result;
            }
            yield return Result();
            while (true)
            {
                var done = true;
                for (var i = count - 1; i >= 0; i--)
                {
                    cycles[i]--;
                    if (cycles[i] == 0)
                    {
                        for (var j = i; j + 1 < indices.Length; j++)
                        {
                            (indices[j], indices[j + 1]) = (indices[j + 1], indices[j]);
                        }
                        cycles[i] = n - i;
                    }
                    else
                    {
                        (indices[i], indices[^cycles[i]]) = (indices[^cycles[i]], indices[i]);
                        yield return Result();
                        done = false;
                        break;
                    }
                }
                if (done) yield break;
            }
        }
        return Inner();
    }
}