ABC289参加記

4完30分 1936位

A問題

文字列$s$の各文字を置き換えるのに、map関数を使用した。

import std;

void main() {
    auto s = readln.chomp.to!(dchar[]);

    auto res = s.map!(a => to!dchar((a.to!int+1)%2+'0')).array;
    res.writeln;
}

B問題

個人的にA~Dの中で1番難しかった。

初期位置を1、答えの配列$p$を最初に空として、現在位置から「レ」が続く位置までの逆順を$p$に追加し現在位置変更するという処理を繰り返す。

import std;

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

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

    auto used = new bool[](N+1);
    foreach (x; a) used[x] = true;

    int i, pos = 1;
    int[] res;
    while (i < N) {
        int next = pos;
        while (next <= N && used[next]) {
            ++next;
        }

        auto arr = iota(pos, next+1).array;
        arr.reverse;

        res ~= arr;
        i = res.length.to!int;
        pos = next + 1;
    }

    writefln("%(%s %)", res);
}

C問題

bit全探索を行って解く。 集合$S_{i}$に含まれる整数をbitで管理することで、$1 \leq x \leq N$を満たす全ての整数を含む集合であるかを素早く判断することができる。

import std;

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

    auto list = new int[](M);
    foreach (i; 0 .. M) {
        int C;
        readf("%d\n", C);

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

        a[] -= 1;
        int num;
        foreach (x; a) num += (1 << x);

        list[i] = num;
    }

    int res;
    foreach (i; 0 .. 1<<M) {
        int num;
        foreach (j; 0 .. M) {
            if ((i >> j) & 1) num |= list[j];
        }

        if (num == (1 << N) - 1) ++res;
    }

    res.writeln;
}

D問題

$0 \leq i < X$を満たす$i$段目において$i$段目に到達可能で$i + A_{j} (i \leq j \leq N)$段目にモチが設置されていなければ$i + A_{j} (i \leq j \leq N)$段目を到達可能であるとする処理を行う。

import std;

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

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

    int M;
    readf("%d\n", M);

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

    int X;
    readf("%d\n", X);

    bool[int] used;
    foreach (b; B) used[b] = true;

    auto dp = new bool[](X+1);
    dp[0] = true;
    foreach (i; 0 .. X) {
        if (!dp[i]) continue;

        foreach (a; A) {
            int pos = i + a;
            if (pos > X || pos in used) continue;

            dp[pos] = true;
        }
    }

    writeln(dp[X] ? "Yes" : "No");
}