ABC247

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc247

問題A

コンテスト提出

S[i+1] (0<=i<=2)の値をS[i]に移動し、S[0]は誰もいなくなるので0にしたものが答えとなります。 つまり、Sの先頭に0を追加した先頭4文字が答えとなります。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var T = "0" + S[0..3];
    Console.WriteLine(T);
}

問題B

コンテスト提出

i番目のあだ名aiを付けることができる条件は、あるあだ名がj!=i番目の姓sjと名tjのいずれも一致しないことであり、あだ名にsiを使った場合と、tiを使った場合をすべてチェックしてどちらか一方でも使うことができれば、そのあだ名を使うことができます。 これを全ての人に対して判定を行い、全ての人にあだ名を付けることができるかを判定します。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var Names = new (string S, string T)[N];
    var answer = true;
    for (var i = 0; i < N; i++)
    {
        var (s, t) = Scanner.Scan<string, string>();
        Names[i] = (s, t);
    }

    for (var i = 0; i < N; i++)
    {
        var s = true;
        var t = true;
        for (var j = 0; j < N; j++)
        {
            if (i == j) continue;
            s &= Names[i].S != Names[j].S && Names[i].S != Names[j].T;
            t &= Names[i].T != Names[j].S && Names[i].T != Names[j].T;
        }

        answer &= s || t;
    }

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

問題C

コンテスト提出
復習提出

初期値をSi=1 (i=1)とし、2<=i<=NではS(i-1) i S(i-1)を文字列として構築することで答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var answer = "1";
    for (var i = 2; i <= N; i++)
    {
        answer = $"{answer} {i} {answer}";
    }

    Console.WriteLine(answer);
}

問題D

コンテスト提出

連結リストなどのデータ構造を使って、データを管理します。
cの値が大きいため、リストにc個の値を入れてしまうとクエリ当たりの計算量がO(c)、全体でO(Qc)となり、実行時間制限内に処理を終えることができません。 そこで、xとcをペアとして管理することで、クエリ当たりの計算量がO(1)、全体でO(Q)となり、実行時間制限内に解くことができるようになります。
クエリが1のときはxとcをペアとしてリストの後方に追加し、クエリが2のときは、c個消費できるまでリストの先頭から消費していきます。

public static void Solve()
{
    var Q = Scanner.Scan<int>();
    var deq = new Deque<(long X, long C)>();
    while (Q-- > 0)
    {
        var query = Scanner.ScanEnumerable<long>().ToArray();
        if (query[0] == 1)
        {
            deq.PushBack((query[1], query[2]));
        }
        else
        {
            var c = query[1];
            long sum = 0;
            while (c > 0)
            {
                var top = deq.PopFront();
                var use = Math.Min(c, top.C);
                c -= use;
                sum += top.X * use;
                if (use < top.C)
                {
                    deq.PushFront((top.X, top.C - use));
                }
            }

            Console.WriteLine(sum);
        }
    }
}

問題E

コンテスト提出

Ai<Y && X<Aiとなる値が範囲に存在する場合、その範囲は無視することができるので、Y<=Ai<=Xのみで構成される連続部分列に分割し、連続部分列ごとに部分問題として数え上げることができるようになります。 例えば、X=3, Y=2, A=[4,1,3,2,3,2,1,2]の場合、A=[[3,2,3,2], [2]]と分割できます。
部分問題では、愚直に全探索してしまうと計算量O(N^3)になりますが、尺取り法を用いることで計算量O(N)で区間の数を数え上げることができます。

1. はじめL=1とする。
2. 1<=R<=Nにおいて次のことを行う。
   1. 区間[L,R]にXとYがそれぞれ1つ以上存在する場合次のことを行う。
      1. 区間[L,R<=r<=N]は全て条件を満たし、この個数はN-R+1(計算量O(1))で求めることができる。
      2. Lを1進める。

計算量は全体でO(N)で答えを求めることができます。

public static void Solve()
{
    var (N, X, Y) = Scanner.Scan<int, int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();

    bool IsInRange(int v) => Y <= v && v <= X;

    var list = new List<List<int>>();
    var tmp = new List<int>();
    foreach (var a in A)
    {
        if (IsInRange(a))
        {
            tmp.Add(a);
        }
        else
        {
            list.Add(tmp.ToList());
            tmp = new List<int>();
        }
    }

    list.Add(tmp.ToList());
    list = list.Where(x => x.Count > 0).ToList();
    long answer = 0;
    foreach (var group in list)
    {
        var l = 0;
        var M = group.Count;
        var used = new int[X + 1];
        for (var r = 0; r < M; r++)
        {
            used[group[r]]++;
            while (l <= r && used[X] > 0 && used[Y] > 0)
            {
                answer += M - r;
                used[group[l]]--;
                l++;
            }
        }
    }

    Console.WriteLine(answer);
}