ABC242

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc242

問題A

コンテスト提出

それぞれどの条件に当てはまるかで確率を求めます。

• X <= Aならば確率は1
• A+1 <= X <= B ならば確率はC/(B-A)
• B < Xならば確率は0

public static void Solve()
{
    var (A, B, C, X) = Scanner.Scan<int, int, int, int>();
    var answer = 0d;
    if (X <= A) answer = 1d;
    if (A + 1 <= X && X <= B) answer = (double)C / (B - A);
    Console.WriteLine(answer);
}

問題B

コンテスト提出

辞書順最小となる文字列は、文字列Sを構成する文字のうち、小さいものを左から順に並べたものになります。 そのため、文字列Sをソートした文字列が答えとなります。

public static void Solve()
{
    var S = Scanner.Scan<string>().ToCharArray();
    Array.Sort(S);
    var answer = new string(S);
    Console.WriteLine(answer);
}

問題C

コンテスト提出

動的計画法で答えとなる個数を数え上げます。 初期値として、1桁目は1から9である個数をそれぞれ1とします。

• i桁目の数値がjのとき、i+1桁目には、j-1、j、j+1に遷移することができます。 N桁目まで確定したときの、1から9までの個数の和が答えとなります。

数え上げのときに0と10に遷移できるスペースを確保しておくと、j=0の時のj-1の遷移とj=9のときのj+1でif文が不要になります。 mintは、Modとして指定した数値で余りをとった整数をもつ構造体です。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var dp = new mint[N + 1, 11];
    for (var i = 1; i < 10; i++)
    {
        dp[1, i] = 1;
    }

    for (var i = 1; i < N; i++)
    {
        for (var j = 1; j < 10; j++)
        {
            dp[i + 1, j - 1] += dp[i, j];
            dp[i + 1, j] += dp[i, j];
            dp[i + 1, j + 1] += dp[i, j];
        }
    }

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

    Console.WriteLine(answer);
}

問題D

復習提出

コンテスト中の考察です。

• t=0ならば、S[k]
• k=0ならば、S[0]+t
• t>60ならば、S[0]から派生したところになりそう。
• t>0かつk>0のときの周期は?

解説では、F(t,k)となる文字は、再帰的に求めることができるそうです。

• t=0ならば、F(t,k)=S[k]
• k=0ならば、F(t,k)=S[0]+t
• それ以外ならば、F(t,k)=F(t-1,k/2)+k%2+1

FはO(logk)で求めることができます。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var N = S.Length;
    var Q = Scanner.Scan<int>();
    while (Q-- > 0)
    {
        var (t, k) = Scanner.Scan<long, long>();
        var answer = F(t, k - 1);
        Console.WriteLine(answer);
    }

    char G(char c, long d)
    {
        return (char)((c - 'A' + d) % 3 + 'A');
    }

    char F(long t, long k)
    {
        if (t == 0) return S[(int)k];
        if (k == 0) return G(S[0], t);
        return G(F(t - 1, k / 2), k % 2 + 1);
    }
}

問題E

復習提出

辞書順で文字列S以下の文字列を考えます。 回文のため、文字列Sの前半分の文字列S'において、S'未満の個数を数え上げを行います。 この数え上げは、S'の文字をそれぞれ0-25の26進数としたときの個数として数え上げることができます。 また、文字列Sの前半分を回文にした文字列をTとしたとき、S以下ならば、答えを1増やします。

例えば、S=ABCDEならば、S'=ABCなので、前半の数え上げは26^2*0 + 26^1*1 + 26^0*2 = 28となり、T=ABCBA<=Sなので答えは29になります。

public static void Solve()
{
    var Q = Scanner.Scan<int>();
    while (Q-- > 0)
    {
        var N = Scanner.Scan<int>();
        var S = Scanner.Scan<string>();
        var T = S.ToCharArray();

        for (var i = 0; i < (N + 1) / 2; i++)
        {
            T[N - 1 - i] = T[i];
        }

        mint answer = 0;
        for (var i = 0; i < (N + 1) / 2; i++)
        {
            answer *= 26;
            answer += T[i] - 'A';
        }

        if (new string(T).CompareTo(S) <= 0) answer++;
        Console.WriteLine(answer);
    }
}