ABC260

Published on Sunday, 17 July 2022

Updated on Sunday, 17 July 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc260

問題A

コンテスト提出

文字ごとの出現数を数え上げ、出現数が1つのみ文字を出力します。
C#の場合、char型を数値として扱い、小文字のアルファベットからaを引くことでa,b,c,...を0,1,2,...として管理することができます。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var count = new int[26];
    foreach (var c in S)
    {
        count[c - 'a']++;
    }

    for (var i = 0; i < 26; i++)
    {
        if (count[i] == 1)
        {
            Console.WriteLine((char)('a' + i));
            return;
        }
    }

    Console.WriteLine(-1);
}

受験生の番目、数学のスコア、英語のスコアをTupleなどのデータクラスとして管理します。
i番目の学生が合格したかをフラグとして管理し、それぞれの条件ごとにソートして合格となっていない受験生が対象となるかを判定することで、時間計算量O(NlogN+N)で答えを求めることができます。
C#の場合、Array.Sort メソッドにComparison<T>を指定することで、比較関数を与えてソートすることができます。

public static void Solve()
{
    var (N, X, Y, Z) = Scanner.Scan<int, int, int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var accepts = new bool[N];
    var C = A.Zip(B).Select((x, i) => (A: x.First, B: x.Second, ID: i)).ToArray();

    Array.Sort(C, (x, y) =>
    {
        var result = y.A.CompareTo(x.A);
        return result == 0 ? x.ID.CompareTo(y.ID) : result;
    });
    for (var i = 0; i < N && X > 0; i++)
    {
        if (accepts[C[i].ID]) continue;
        accepts[C[i].ID] = true;
        X--;
    }

    Array.Sort(C, (x, y) =>
    {
        var result = y.B.CompareTo(x.B);
        return result == 0 ? x.ID.CompareTo(y.ID) : result;
    });
    for (var i = 0; i < N && Y > 0; i++)
    {
        if (accepts[C[i].ID]) continue;
        accepts[C[i].ID] = true;
        Y--;
    }

    Array.Sort(C, (x, y) =>
    {
        var result = (y.A + y.B).CompareTo(x.A + x.B);
        return result == 0 ? x.ID.CompareTo(y.ID) : result;
    });
    for (var i = 0; i < N && Z > 0; i++)
    {
        if (accepts[C[i].ID]) continue;
        accepts[C[i].ID] = true;
        Z--;
    }

    for (var i = 0; i < N; i++)
    {
        if (accepts[i])
        {
            Console.WriteLine(i + 1);
        }
    }
}

問題C

コンテスト提出

動的計画法で答えを求めます。赤い宝石と青い宝石のレベルごとの個数をそれぞれ管理し、レベルNからレベル2まで計算します。遷移としては、レベルごとに先に赤い宝石を変換し、次に青い宝石を変換します。

public static void Solve()
{
    var (N, X, Y) = Scanner.Scan<int, long, long>();
    var Red = new long[N + 1];
    var Blue = new long[N + 1];
    Red[N] = 1;
    for (var i = N; i >= 2; i--)
    {
        Red[i - 1] += Red[i];
        Blue[i] += Red[i] * X;
        Red[i - 1] += Blue[i];
        Blue[i - 1] += Blue[i] * Y;
    }

    var answer = Blue[1];
    Console.WriteLine(answer);
}

問題D

コンテスト提出
 復習提出

表になっているカードの集合のうちX以上の値を高速に求められるようなデータ構造と、カードの山を管理するデータ構造を使って何ターン目に食べられるかを判定します。前者のデータ構造では、X以上の値を時間計算量O(N)で探索してしまうと、全体の時間計算量がO(N^2)となってしまい実行時間制限に間に合いません。
そのため、二部探索のような時間計算量O(logN)で探索できるようなデータ構造(C++の場合はset、C#の場合はSortedSet)が必要です。
SortedSetからGetViewBetweenしたサブセットのCountプロパティが、場合によっては時間計算量O(1)ではなさそうなので、LINQのAnyで存在判定をしたほうが良さそうです。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var P = Scanner.ScanEnumerable<int>().ToArray();
    var answer = new int[N + 1];
    Array.Fill(answer, -1);
    var set = new SortedSet<int>();
    var dict = new Dictionary<int, List<int>>();
    var root = new int[N + 1];
    for (var i = 0; i < N; i++)
    {
        var p = P[i];
        var r = root[p] = p;
        var subset = set.GetViewBetween(p, N);

        if (subset.Any())
        {
            var q = subset.Min;
            r = root[p] = root[q];
            set.Remove(q);
        }
        else
        {
            dict[r] = new List<int>();
        }
        
        set.Add(p);
        dict[r].Add(p);

        if (dict[r].Count >= K)
        {
            foreach (var v in dict[r])
            {
                answer[v] = i + 1;
            }

            set.Remove(p);
            dict.Remove(r);
        }
    }

    Console.WriteLine(string.Join("\n", answer.Skip(1)));
}

はじめに

コンテスト

問題A

問題B

問題C

問題D