ABC230

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc230

問題A

コンテスト提出

入力を取り、Nが42以上なら答えをインクリメントします。C#では出力をフォーマットできるので、0埋めフォーマットを行います。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    if (N >= 42) N++;
    // var answer = $"AGC{N.ToString("000")}";
    var answer = $"AGC{N:000}";
    Console.WriteLine(answer);
}

問題B

コンテスト提出
復習提出

3つ連続した部分文字列において、xが3つ連続した場合、oxoのようにoが2つ以上含まれている場合は答えはNoになります。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var answer = true;
    for (var i = 0; i + 2 < S.Length; i++)
    {
        answer &= (S[i], S[i + 1], S[i + 2]) != ('x', 'x', 'x');
        answer &= (S[i], S[i + 1], S[i + 2]) != ('o', 'x', 'o');
    }

    for (var i = 0; i + 1 < S.Length; i++)
    {
        answer &= (S[i], S[i + 1]) != ('o', 'o');
    }

    Console.WriteLine(answer ? "Yes" : "No");
}

解説では、Yesになるテンプレートは高々3つなので、そのテンプレートの順番でoとxが出現しているかを判定します。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    foreach (var t in new[] { "oxx", "xox", "xxo" })
    {
        var ok = true;
        for (var i = 0; i < S.Length; i++)
        {
            ok &= S[i] == t[i % 3];
        }
    
        if (ok)
        {
            Console.WriteLine("Yes");
            return;
        }
    }
    
    Console.WriteLine("No");
}

問題C

コンテスト提出
復習提出

黒く塗りつぶすべきマスは、xの交点となる(A,B)からの距離dxとdyの絶対値が一致する箇所になります。 そのため、対象となるマスを見ていくとき、Abs(dx) == Abs(dy)になるマスを黒く塗れば、求められる出力が得られます。

public static void Solve()
{
    var (N, A, B) = Scanner.Scan<long, long, long>();
    var (P, Q, R, S) = Scanner.Scan<long, long, long, long>();

    for (var i = P; i <= Q; i++)
    {
        for (var j = R; j <= S; j++)
        {
            Console.Write(Math.Abs(A - i) == Math.Abs(B - j) ? '#' : '.');
        }
        Console.WriteLine();
    }
}

問題D

コンテスト提出

D列まとめてダメージを与えられるということは、壁の当たり判定をD-1伸ばして、パンチを1列にすることと同じことになります。 そのため、壁のRにD-1を追加したときの区間スケジューリング問題として扱うことができます。 Rで壁を昇順ソートして順にみたとき、Lが有効な場合に壁を叩くことができれば無効をRに更新することで数え上げることができます。

public static void Solve()
{
    var (N, D) = Scanner.Scan<int, long>();
    var W = new (long L, long R)[N];
    for (var i = 0; i < N; i++)
    {
        var (l, r) = Scanner.Scan<long, long>();
        r += D - 1;
        W[i] = (l, r);
    }

    Array.Sort(W, (x, y) => x.R.CompareTo(y.R));
    var answer = 0;
    var rr = 0L;
    foreach (var (l, r) in W)
    {
        if (rr >= l) continue;
        rr = r;
        answer++;
    }

    Console.WriteLine(answer);
}

問題E

復習提出

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

• Sqrt(N)まで見ればよさそう。
• Sqrt(N)以降はi*countで求められそう
• countはどうやって求められるか

時間切れになりました。

N/iをkとしたとき、k <= N/i < k+1となるiの個数はN/i >= i > N/(K+1)となるため、N/i - N/(i+1)で求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var answer = 0L;
    for (var i = 1L; i * i <= N; i++)
    {
        if (i != N / i) answer += N / i;
        var count = (N / i) - (N / (i + 1));
        answer += i * count;
    }

    Console.WriteLine(answer);
}