ABC249

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc249

問題A

コンテスト提出

高橋君の進む距離を考えます。 歩く+休むを1セットとすると、X秒間にX/(A+C)セット(端数切り捨て)できるため、距離は合計でセット数*A*B進むことができます。 また、Xから進んだセット数を引いたあまりX%(A+C)のうち、最大A秒間進むこともできるため、Min(あまり,A)*B進むことができます。 この二つを合わせた距離が高橋君の進む距離となります。 A秒間秒速Bメートルで歩き、C秒間休むことを繰り返した時のX秒後の距離を関数にすると、F(A,B,C) = X/(A+C)*A*B + Min(X%(A+C),A)*Bに定義できます。
同様に青木君の距離を求め、どちらが長い距離を進んだかを比較して答えを求めます。

public static void Solve()
{
    var line = Scanner.ScanEnumerable<int>().ToArray();
    var (A, B, C) = (line[0], line[1], line[2]);
    var (D, E, F) = (line[3], line[4], line[5]);
    var X = line[6];
    int G(int a, int b, int c)
    {
        return (X / (a + c) * a * b) + Math.Min(X % (a + c), a) * b;
    }

    var takahashi = G(A, B, C);
    var aoki = G(D, E, F);
    var answer = "Draw";
    if (takahashi > aoki) answer = "Takahashi";
    if (takahashi < aoki) answer = "Aoki";
    Console.WriteLine(answer);
}

問題B

コンテスト提出

一つずつ条件を判定していきます。
C#では、char.IsUpper関数で文字の大文字判定、char.IsLower関数で文字の小文字判定を行うことができます。 また、全ての文字が相異なるということは、元の文字列の長さ=重複を除いたときの文字列の長さといえます。

1. すべての文字をみて大文字が存在するかを判定する
2. すべての文字をみて小文字が存在するかを判定する
3. 元の文字列の長さ=重複を除いたときの文字列の長さが成り立つかを判定する

これらすべてが成り立っているかを判定します。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var N = S.Length;
    var M = S.Distinct().Count();
    var ok = N == M;
    var big = false;
    var small = false;
    foreach (var c in S)
    {
        big |= char.IsUpper(c);
        small |= char.IsLower(c);
    }

    ok &= big && small;
    Console.WriteLine(ok ? "Yes" : "No");
}

問題C

コンテスト提出

各文字列に対して使うor使わないの2択なため、2^N個の組み合わせがあり得ます。 制約がN<=15と少ないので、bit全探索を行うことで全ての組み合わせを走査することができます。 sを使用するiの集合としたとき、sにおいてiが使われているかを判定するには、(s>>i&1)==1で求めることができます。 そして、それぞれの組み合わせにおいて、使う文字列集合を全て走査し、文字の個数がK個の文字の種類の最大値を求めます。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var answer = 0;
    var exists = new bool[N, 26];
    for (var i = 0; i < N; i++)
    {
        var S = Scanner.Scan<string>();
        foreach (var c in S)
        {
            exists[i, c - 'a'] = true;
        }
    }


    for (var s = 0; s < 1 << N; s++)
    {
        var count = new int[26];
        for (var i = 0; i < N; i++)
        {
            if ((s >> i & 1) == 1)
            {
                for (var j = 0; j < 26; j++)
                {
                    count[j] += exists[i, j] ? 1 : 0;
                }
            }
        }

        var sum = 0;
        for (var i = 0; i < 26; i++)
        {
            if (count[i] == K) sum++;
        }

        answer = Math.Max(answer, sum);
    }
    Console.WriteLine(answer);
}

問題D

コンテスト提出

愚直に全てのi,j,kを走査する方法では、計算量がO(N^3)となり、A[j]*A[k]=A[i]となるj,kを走査する方法では、計算量がO(N^2)となりますが、制約が1<=N<=2e5と大きいため、実行時間制限内に処理を終わらせることができません。
そこで、あらかじめAの値の出現回数を数えておき、1<=p,q,r<=2e5のうち、p=q*rとなるp,q,rの組における組み合わせの個数の総和を求めます。 組み合わせの個数はpの個数 * qの個数 * rの個数でもとめることができます。 qを固定したとき、rはp/q (p<=2e5)まで走査すればよいため、計算量O(MlogM)で求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var max = (int)2e5;
    var count = new long[max + 1];
    foreach (var a in A)
    {
        count[a]++;
    }

    var answer = 0L;
    for (var q = 1; q <= max; q++)
    {
        for (var r = 1; q * r <= max; r++)
        {
            var p = q * r;
            answer += count[p] * count[q] * count[r];
        }
    }

    Console.WriteLine(answer);
}