ABC294

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc294

問題A

コンテスト提出

LiNQのWhereを使うことで、シーケンスに対してフィルタをかけることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    Console.WriteLine(string.Join(" ", A.Where(x => x % 2 == 0)));
}

問題B

コンテスト提出

F(n)をn番目の英大文字としたとき、ASCIIコードよりF(n)は(char)('A'+n-1)で求めることができます。 また、A[i][j]をi行j列の数字、G[i][j]をi行j列の文字としたとき、

• A[i][j]が0ならば、G[i][j]は'.'
• A[i][j]が0以外ならば、G[i][j]はF(A[i][j])

に置換したものが答えとなります。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var A = new int[H][];
    for (var i = 0; i < H; i++)
    {
        A[i] = Scanner.ScanEnumerable<int>().ToArray();
    }

    char F(int n) => (char)('A' + n - 1);

    var G = new char[H, W];
    for (var i = 0; i < H; i++)
    {
        for (var j = 0; j < W; j++)
        {
            G[i, j] = A[i][j] == 0 ? '.' : F(A[i][j]);
        }
    }

    Printer.Print2D(G);
}

問題C

コンテスト提出

AとBを合わせ、ソートした配列Cにおいて、AとBにおける任意の数値がCにおける何番目かを求められることが必要です。 これは辞書などのデータ構造を使って``dict[C[i]]=i`を管理することで高速に求めることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var (map, _) = Compress(A.Concat(B));
    Console.WriteLine(string.Join(" ", A.Select(x => map[x] + 1)));
    Console.WriteLine(string.Join(" ", B.Select(x => map[x] + 1)));
}

public static (Dictionary<T, int> Map, Dictionary<int, T> ReMap) Compress<T>(IEnumerable<T> source)
{
    var distinct = source.Distinct().ToArray();
    Array.Sort(distinct);
    var map = new Dictionary<T, int>();
    var remap = new Dictionary<int, T>();
    foreach (var (x, i) in distinct.Select((x, i) => (x, i)))
    {
        map[x] = i;
        remap[i] = x;
    }

    return (map, remap);
}

問題D

コンテスト提出
復習提出

受付に呼ばれていない人の集合S1と既に受付に呼ばれているが受付に行っていない人の集合S2としたとき、それぞれの集合を順序付き集合で管理することで、クエリ当たりの時間計算量O(logN)、全体時間計算量でO(QlogN)で答えを求めることができます。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var S1 = new SortedSet<int>(Enumerable.Range(0, N));
    var S2 = new SortedSet<int>();
    while (Q-- > 0)
    {
        var e = Scanner.ScanEnumerable<int>().ToArray();
        if (e[0] == 1)
        {
            var x = S1.Min;
            S1.Remove(x);
            S2.Add(x);
        }
        else if (e[0] == 2)
        {
            var x = e[1] - 1;
            S2.Remove(x);
        }
        else
        {
            var x = S2.Min;
            Console.WriteLine(x + 1);
        }
    }
}

問題E

コンテスト提出
復習提出

各要素Vについて、要素の始まりの位置Lと要素の終わりの位置Rを管理し、対象の範囲を左から順に尺取り法で走査していきます。
1行目のV、L、RをそれぞれV1、L1、R1とし、2行目のV、L、RをそれぞれV2、L2、R2としたとき、対象となる範囲V1とV2が一致しているとき、Min(R1,R2)-Max(L1,L2)個の要素が一致します。
そして、R1<=R2ならば、1行目の対象の範囲を1つずらし、R1>R2ならば2行目の対象の範囲を1つずらします。

public static void Solve()
{
    var (L, N1, N2) = Scanner.Scan<long, int, int>();
    var S1 = new S[N1];
    var S2 = new S[N2];
    for (var k = 0; k < 2; k++)
    {
        var (N, S) = k == 0 ? (N1, S1) : (N2, S2);
        long l = 0;
        for (var i = 0; i < N; i++)
        {
            var (v, len) = Scanner.Scan<long, long>();
            var r = l + len;
            S[i] = new S(v, l, r);
            l = r;
        }
    }

    long answer = 0;
    var (i1, i2) = (0, 0);
    while (i1 < N1 && i2 < N2)
    {
        if (S1[i1].V == S2[i2].V)
        {
            var l = Math.Max(S1[i1].L, S2[i2].L);
            var r = Math.Min(S1[i1].R, S2[i2].R);
            answer += Math.Max(0, r - l);
        }

        if (S1[i1].R <= S2[i2].R) i1++;
        else i2++;
    }

    Console.WriteLine(answer);
}

public readonly struct S
{
    public readonly long V;
    public readonly long L;
    public readonly long R;
    public S(long v, long l, long r) => (V, L, R) = (v, l, r);
}