ABC250

Published on Sunday, 08 May 2022

Updated on Sunday, 08 May 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc250

問題A

コンテスト提出

隣接するマスは上下左右なので、(R,C)にx軸とy軸の差分4方向((+1,0), (-1,0), (0,+1),(0,-1))を確認し、1<=R+d<=H && 1<=R+d<=Wに含まれている個数を数え上げます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var (R, C) = Scanner.Scan<int, int>();
    R--;
    C--;
    var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
    var answer = 0;
    foreach (var (dh, dw) in D4)
    {
        var (nh, nw) = (R + dh, C + dw);
        if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
        answer++;
    }

    Console.WriteLine(answer);
}

問題B

コンテスト提出

N=1, A=1, B=1としたとき、

.#
#.

のようになり、iとjがそれぞれ偶奇をとるとき、つまり(0,0), (0,1), (1,0), (1,1)の4パターンが存在することがわかります。
また、AとBの値を変更したとき、それぞれのタイルは縦Aマス、横Bマスになるので、iとjそれぞれAとBで割ったときの偶奇によってタイルを指定すれば、答えとなるタイルが求められます。

public static void Solve()
{
    var (N, A, B) = Scanner.Scan<int, int, int>();
    var G = new char[N * A, N * B];
    for (var i = 0; i < N * A; i++)
    {
        for (var j = 0; j < N * B; j++)
        {
            var x = i / A % 2;
            var y = j / B % 2;
            G[i, j] = (x, y) switch
            {
                (0, 0) => '.',
                (0, 1) => '#',
                (1, 0) => '#',
                (1, 1) => '.',
                _ => '.',
            };
        }
    }

    Printer.Print2D(G);
}

クエリごとにxの位置を全探索してしまうと、計算量がO(N)かかってしまい、全体計算量がO(QN)となり実行時間制限に間に合いません。そこで、あらかじめxの位置をキーとした辞書や配列などを用意しておきます。
クエリが与えられたら、xの位置をiとし、iが端(i=N-1)ならi-1、それ以外ならばi+1の位置をjとして、iとjの位置にある要素を入れ替え、位置をキーとした辞書の要素も入れ替えることで、クエリ当たりの計算量をO(1)にすることができ、全体計算量O(Q+N)に改善することができます。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var A = Enumerable.Range(1, N).ToArray();
    var dict = new Dictionary<int, int>();
    for (var i = 0; i < N; i++)
    {
        dict[A[i]] = i;
    }

    for (var k = 0; k < Q; k++)
    {
        var x = Scanner.Scan<int>();
        var i = dict[x];
        var j = i + 1 != N ? i + 1 : i - 1;
        var y = A[j];
        (A[i], A[j]) = (A[j], A[i]);
        dict[x] = j;
        dict[y] = i;
    }

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

問題D

コンテスト提出
 復習提出

問題文における最大の素数を考えたとき、k=p*q^3, N<=1e18から、q^3<=Nまでの素数を考えればいいため、q以下となる素数群を昇順にソートしたものをあらかじめ用意しておきます。
それらの素数をp<qの範囲で走査したときの、p*q^3<=Nとなる組み合わせの数が答えとなります。
このとき、全探索してしまうと、素数の数をMとしたとき計算量O(M^2)となり、N=1e18のときにM=78498となって実行時間制限に間に合いませんが、p*q^3>Nのときのq以降の対象となりえない組み合わせを枝刈りすることで、実行時間制限に間に合わせることができます。
あるいは、p<qの範囲でqを二部探索することで計算量O(MlogM)、p*q^3>=Nならば(p+1)*q^3>=Nからqを大きいほうから尺取り法で求めることでO(M)で求めることができます。また、p*q^3の値が、64bit整数に収まらない場合もあるので、多倍長整数を使ったり、オーバーフローした場合の処理が必要となる場合があります。
C#の場合、整数のオーバーフローは例外が発生しませんが、checkedブロックを使うことで例外を明示的に発生させることができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var primes = Prime.Sieve((int)1e6).ToArray();
    var M = primes.Length;
    var answer = 0;
    var j = M - 1;
    for (var i = 0; i < j; i++)
    {
        while (i < j)
        {
            var p = (long)primes[i];
            var q = (long)primes[j] * primes[j] * primes[j];
            try
            {
                checked
                {
                    if (p * q <= N)
                    {
                        break;
                    }
                    else
                    {
                        j--;
                    }
                }
            }
            catch
            {
                j--;
            }
        }

        answer += j - i;
    }

    Console.WriteLine(answer);
}

public static IEnumerable<int> Sieve(int value)
{
    if (value < 2) yield break;
    yield return 2;
    var sieve = new bool[(value + 1) / 2];
    for (var i = 1; i < sieve.Length; i++)
    {
        if (sieve[i]) continue;
        yield return i * 2 + 1;
        for (var j = i; j < sieve.Length; j += i * 2 + 1) sieve[j] = true;
    }
}

問題E

コンテスト提出
 復習提出

Aのx番目までの要素に対応するBの最小の出現位置の最大がy以下であり、Bのy番目までの要素に対応するAの最小の出現位置の最大がx以下であれば答えはYesとなります。

あらかじめ、Aの各要素のBにおける最小の出現位置(AtoB)と、Bの各要素のAにおける最小の出現位置(BtoA)を求めておき、クエリごとにAtoBのxまでの最大値とBtoAのyまでの最大値を求められるようにします。
このとき愚直にx番目とy番目までを走査してしまうとクエリ当たりの計算量がO(N)となってしまうため、累積最大値をもとめておくことでクエリ当たりの計算量をO(1)に抑えることができ、全体でO(Q+NlogN)で求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var dictAB = new Dictionary<int, int>();
    var dictBA = new Dictionary<int, int>();
    const int inf = (int)1e9;
    for (var i = 0; i < N; i++)
    {
        dictAB[A[i]] = inf;
        dictAB[B[i]] = inf;
        dictBA[A[i]] = inf;
        dictBA[B[i]] = inf;
    }

    for (var i = 0; i < N; i++)
    {
        dictAB[B[i]] = Math.Min(dictAB[B[i]], i + 1);
        dictBA[A[i]] = Math.Min(dictBA[A[i]], i + 1);
    }

    var cumAB = new int[N + 1];
    var cumBA = new int[N + 1];
    for (var i = 0; i < N; i++)
    {
        cumAB[i + 1] = Math.Max(cumAB[i], dictAB[A[i]]);
        cumBA[i + 1] = Math.Max(cumBA[i], dictBA[B[i]]);
    }

    var Q = Scanner.Scan<int>();
    for (var i = 0; i < Q; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        var answer = cumAB[x] <= y && cumBA[y] <= x;
        Console.WriteLine(answer ? "Yes" : "No");
    }
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E