ABC294参加記

5完32分 959位

A問題

問題名にある通りfilter関数を用いて、偶数の要素を取り出す。

import std;

void main() {
    int N;
    readf("%d\n", N);

    auto A = readln.chomp.split.to!(int[]);

    auto res = A.filter!(a => a % 2 == 0).array;
    writefln("%(%s %)", res);
}

B問題

行列$A$の上から$i$行目、左から$j$列目の要素$A_{ij}$が0であれば.、そうでなければto!dchar('A'+A[i][j]-1)を出力する。

import std;

void main() {
    int H, W;
    readf("%d %d\n", H, W);

    auto A = new int[][](H, W);
    foreach (i; 0 .. H) A[i] = readln.chomp.split.to!(int[]);

    auto res = new dchar[][](H, W);
    foreach (i; 0 .. H) {
        foreach (j; 0 .. W) {
            if (A[i][j] == 0) res[i][j] = '.';
            else res[i][j] = to!dchar('A'+A[i][j]-1);
        }
    }

    writefln("%(%-(%s%)\n%)", res);
}

C問題

配列$A$と$B$を結合させた配列$C$に対して座標圧縮を行う。

import std;

void main() {
    int N, M;
    readf("%d %d\n", N, M);

    auto A = readln.chomp.split.to!(int[]);
    auto B = readln.chomp.split.to!(int[]);

    int[] res = A.dup ~ B.dup;

    void f(ref int[] arr) {
        auto tmp = arr.dup.sort.uniq.array.assumeSorted;
        foreach (ref a; arr) {
            a = tmp.lowerBound(a).length.to!int;
        }
    }

    f(res);

    res[] += 1;

    writefln("%(%s %)", res[0..N]);
    writefln("%(%s %)", res[N..$]);
}

D問題

2本のRedBlackTreeを用いて、人の状態を管理する。 1本は受付に呼ばれていない人を管理、もう1本は受付に呼ばれているが受付に行っていない人を管理する。

import std;

void main() {
    int N, Q;
    readf("%d %d\n", N, Q);

    auto rbt1 = new RedBlackTree!(int, "a < b")();
    foreach (i; 1 .. N+1) rbt1.insert(i);

    auto rbt2 = new RedBlackTree!(int, "a < b")();

    foreach (_; 0 .. Q) {
        auto input = readln.chomp.split.to!(int[]);

        if (input[0] == 1) {
            auto f = rbt1.front;
            rbt1.removeFront;
            rbt2.insert(f);
        }
        else if (input[0] == 2) {
            rbt2.removeKey(input[1]);
        }
        else {
            rbt2.front.writeln;
        }
    }
}

E問題

連長圧縮した長さ$N_{1}$の列のインデックスをidx1、長さ$N_{2}$の列のインデックスをidx2とする。 圧縮した長さが短い方をl = min(l1[idx1], l2[idx2])を取得する。 それぞれの行に対して現在の長さがlならばインデックスを+1し、そうでなければ現在の長さからlを引く。 この処理を$L$行目に到達するまで繰り返し行う。

import std;

void main() {
    long L, N1, N2;
    readf("%d %d %d\n", L, N1, N2);

    auto v1 = new long[](N1), l1 = new long[](N1);
    foreach (i; 0 .. N1) readf("%d %d\n", v1[i], l1[i]);

    auto v2 = new long[](N2), l2 = new long[](N2);
    foreach (i; 0 .. N2) readf("%d %d\n", v2[i], l2[i]);

    long res, pos, idx1, idx2;
    while (pos < L) {
        long mn = min(l1[idx1], l2[idx2]);
        if (v1[idx1] == v2[idx2]) {
            res += mn;
        }

        pos += mn;

        if (l1[idx1] == mn) {
            ++idx1;
        }
        else {
            l1[idx1] -= mn;
        }

        if (l2[idx2] == mn) {
            ++idx2;
        }
        else {
            l2[idx2] -= mn;
        }
    }

    res.writeln;
}