ABC234

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc234

問題A

コンテスト提出

F(x)を定義し、求める式をG(x)とした時に、G(T)の値が答えとなります。

public static void Solve()
{
    var T = Scanner.Scan<int>();
    long F(long x) => x * x + 2 * x + 3;
    long G(long x) => F(F(F(x) + x) + F(F(x)));
    var answer = G(T);
    Console.WriteLine(answer);
}

問題B

コンテスト提出

すべての点の組み合わせを試すことで求めることができます。 最後にSqrtを取ることで誤差を回避しました。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var P = new (double X, double Y)[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y) = Scanner.Scan<double, double>();
        P[i] = (x, y);
    }

    var answer = 0d;
    foreach (var (x1, y1) in P)
    {
        foreach (var (x2, y2) in P)
        {
            var (dx, dy) = (x2 - x1, y2 - y1);
            answer = Math.Max(answer, dx * dx + dy * dy);
        }
    }

    answer = Math.Sqrt(answer);
    Console.WriteLine(answer);
}

問題C

コンテスト提出

Kを2進数表記したとき、1の値を2にしたものが答えとなります。

public static void Solve()
{
    var K = Scanner.Scan<long>();
    var list = new List<long>();
    while (K > 0)
    {
        list.Add(K & 1);
        K >>= 1;
    }
    list.Reverse();
    var answer = string.Join("", list.Select(x => x * 2));
    Console.WriteLine(answer);
}

問題D

コンテスト提出
復習提出

優先度付きキューを使い、キューのサイズがK個の時の最小の値がそれぞれの状態の答えとなります。 最初は、先頭からK個の値を入れたときの最小の値を表示し、それ以降は追加される値がキューの最小よりも小さい場合はK番目より小さいので無視し、大きい場合はキューを更新することでK個を維持しつつ最小の値を管理できます。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var P = Scanner.ScanEnumerable<int>().ToArray();
    var queue = new PriorityQueue<int>();
    for (var i = 0; i < K; i++)
    {
        queue.Enqueue(P[i]);
    }

    Console.WriteLine(queue.Peek());

    for (var i = K; i < N; i++)
    {
        if (queue.Peek() < P[i])
        {
            queue.Dequeue();
            queue.Enqueue(P[i]);
        }

        var answer = queue.Peek();
        Console.WriteLine(answer);
    }
}

問題E

復習提出

答えとしてあり得る値を考えたとき、

• 等差が-9から9 (19通り)
• 最上位の桁が0から9 (10通り)
• 桁数が17桁 (17通り)

すべて合わせて3230(19*10*17)通りのうち、各桁の値が0から9の条件をもつ値すべてを全探索しすることで、X以上を最小の値を求めることができる。

public static void Solve()
{
    var X = Scanner.Scan<long>();
    var hashset = new HashSet<long>(Enumerable.Range(0, 10).Select(x => (long)x));
    for (var d = -9; d <= 9; d++)
    {
        for (var i = 0L; i <= 9; i++)
        {
            var x = i;
            for (var t = 1; t < 18; t++)
            {
                var mod = x % 10;
                if (mod + d < 0 || 10 <= mod + d) break;
                x *= 10;
                x += mod + d;
                hashset.Add(x);
            }
        }
    }

    var answer = hashset.Where(x => x >= X).Min();
    Console.WriteLine(answer);
}

E問題を解こうとしてたはずなのにF問題やってたのでコンテスト中には解けませんでした。コンテスト後に気づいて解いてみたら解けてたので悔しいです。

問題E

復習提出

コンテスト中の考察

• 制約がN<=5000だからdpと組み合わせ?
• 2^Nから重複を引く?
• 重複組み合わせ?
• 長さが1からNのそれぞれの時に数え上げ?

for(var s = 1; s < S.Length; s++)
{
    var sum = 0;
    for(var i = 0; i < 26; i++)
    {
        sum = Math.Min(count[i], s);
    }

    // ToDo
}

解説では、i番目までのアルファベットを使った時の文字列の合計がjである時の組み合わせを数え上げる動的計画法でした。

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

    var N = S.Length;
    var fact = new mint[N + 1];
    var ifact = new mint[N + 1];
    fact[0] = ifact[0] = 1;
    for (var i = 1; i <= N; i++)
    {
        fact[i] = fact[i - 1] * i;
        ifact[i] = 1 / fact[i];
    }

    mint Combination(int n, int k)
    {
        if (n < k || n < 0 || k < 0) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }

    var count = new int[26];
    foreach (var c in S)
    {
        count[c - 'a']++;
    }

    var dp = new mint[27, N + 1];
    dp[0, 0] = 1;

    for (var i = 0; i < 26; i++)
    {
        for (var j = 0; j <= N; j++)
        {
            for (var k = 0; k <= Math.Min(j, count[i]); k++)
            {
                dp[i + 1, j] += dp[i, j - k] * Combination(j, k);
            }
        }
    }

    mint answer = 0;
    for (var i = 1; i <= N; i++)
    {
        answer += dp[26, i];
    }

    Console.WriteLine(answer);
}