ABC281参加記

5完1ペナ64分 768位

A問題

D言語のiota関数を用いて0から$N$のRangeを用意し、foreach_reverseで大きい順から出力する。

import std;

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

    auto A = iota(N+1);
    foreach_reverse (a; A) a.writeln;
}

B問題

文字列$S$の先頭と末尾が英大文字であるか確認し、先頭と末尾を消去する。 残った文字列の長さが6で先頭が0でなく全ての文字が数字であればYesを出力する。

import std;

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

    bool isOK = true;

    if (std.uni.isUpper(S.front)) S.popFront;
    else isOK = false;

    if (std.uni.isUpper(S.back)) S.popBack;
    else isOK = false;

    if (S.length == 6) {
        isOK &= (S.front > '0');

        foreach (s; S) {
            isOK &= std.uni.isNumber(s);
        }
    }
    else {
        isOK = false;
    }

    writeln(isOK ? "Yes" : "No");
}

C問題

$N$曲の長さの合計を$S$とする。 $N$曲まで流れ終わっている時間を考慮する必要がないため$T^{\prime} = T % S$とする。 曲1から順に$T^{\prime} = T^{\prime} -$(曲の長さ)の処理をしていき、$T^{\prime} < A_{i}$を満たす$i$が曲の番号であり$T^{\prime}$が曲が流れ始めてからの時間となる。

import std;

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

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

    long S = A.sum;
    T %= S;

    foreach (i, a; A) {
        if (T < a) {
            writeln(i+1, " ", T);
            return;
        }

        T -= a;
    }
}

D問題

動的計画法(DP)で解く。 dp[個数][総和を$D$で割った余り] = 総和の最大値として$D$で割った余り毎の総和の最大値を管理する。 dp[$K$][0]が答えとなる。

import std;

void main() {
    long N, K, D;
    readf("%d %d %d\n", N, K, D);

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

    auto dp = new long[][](K+1, D);
    foreach (i; 0 .. K+1) dp[i][] = -1;
    dp[0][0] = 0;

    foreach (i, x; a) {
        foreach_reverse (j; 0 .. K) {
            foreach (k; 0 .. D) {
                if (dp[j][k] == -1) continue;

                long S = dp[j][k] + x;
                if (dp[j+1][(k+x)%D] < S) {
                    dp[j+1][(k+x)%D] = S;
                }
            }
        }
    }

    long res = dp[K][0];
    res.writeln;
}

E問題

RedBlackTreeを2つ用意する。 1つが$M$個の整数を昇順に並べた時の先頭$K$個を管理し、もう1つが残りの$M-K$個を管理する。

import std;

struct Number {
    long num, idx;
}

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

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

    auto rbt1 = new RedBlackTree!(Number, "a.num == b.num ? a.idx < b.idx : a.num < b.num", true)();
    auto rbt2 = new RedBlackTree!(Number, "a.num == b.num ? a.idx < b.idx : a.num < b.num", true)();

    auto nums = new long[](N);

    auto res = new long[](N-M+1);
    long S;
    foreach (i, a; A) {
        if (rbt1.length < K) {
            S += a;
            rbt1.insert(Number(a, i.to!long));
            nums[i] = 1;
        }
        else{
            auto b = rbt1.back;
            if (b.num > a) {
                S += a - b.num;
                rbt1.removeBack;
                rbt1.insert(Number(a, i.to!long));
                rbt2.insert(b);
                nums[b.idx] = 2, nums[i] = 1;
            }
            else {
                rbt2.insert(Number(a, i.to!long));
                nums[i] = 2;
            }
        }

        if (i >= M - 1) {
            res[i-M+1] = S;

            if (nums[i-M+1] == 1) {
                rbt1.removeKey(Number(A[i-M+1], i-M+1));
                S -= A[i-M+1];
                if (rbt2.empty) continue;

                auto f = rbt2.front;
                S += f.num;
                nums[f.idx] = 1;
                rbt2.removeFront;
                rbt1.insert(f);
            }
            else {
                rbt2.removeKey(Number(A[i-M+1], i-M+1));
            }
        }
    }

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