ABC286参加記

5完1ペナ88分 1413位

A問題

$A[P..Q]$と$A[R..S]$を入れ替えた数列を求める。

import std;

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

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

    foreach (i; 0 .. Q-P+1) {
        A.swapAt(P+i-1, R+i-1);
    }

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

B問題

replace関数を用いて、文字列$S$に含まれるnaをnyaに置き換える。

import std;

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

    auto res = S.replace("na", "nya");
    res.writeln;
}

C問題

制約が$1 \leq N \leq 5000$であるから、時間計算量$O(N^{2})$で解くことができる。 文字列$S$を回文にするために必要なお金を求めて$S_{1}S_{2}…S_{N}$を$S_{2}…S_{N}S_{1}$にする処理を$N$回実施し、回文にするために必要な最低料金を求める。

import std;

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

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

    long res = long.max, h = N / 2;
    foreach (i; 0 .. N) {
        long num = i * A;
        foreach (j; 0 .. h) {
            if (S[j] != S[N-j-1]) num += B;
        }

        res = min(res, num);

        auto f = S.front;
        S.popFront;
        S ~= f;
    }

    res.writeln;
}

D問題

DPで解く。

import std;

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

    auto list = new bool[](X+1);
    list[0] = true;
    foreach (_; 0 .. N) {
        int A, B;
        readf("%d %d\n", A, B);

        foreach_reverse (i, l; list) {
            if (!l) continue;

            int rem = B;
            foreach (j; iota(i+A, X+1, A)) {
                if (rem <= 0) break;
                list[j] = true;
                --rem;
            }
        }
    }

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

E問題

ワーシャル–フロイド法を用いて全都市間における直行便の個数が最小で購入するお土産の価値が最大になる経路を前計算しておく。 中継地のお土産の価値を二重に数え上げていることに気づくのが遅かった。

import std;

struct City {
    long cnt, num;
}

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

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

    auto S = new string[](N);
    foreach (i; 0 .. N) readf("%s\n", S[i]);

    auto list = new City[][](N, N);
    foreach (i; 0 .. N) {
        list[i][] = City(long.max/4, 0);
        list[i][i] = City(0, A[i]);
    }

    foreach (i; 0 .. N) {
        foreach (j; 0 .. N) {
            if (S[i][j] == 'N') continue;

            list[i][j] = City(list[i][i].cnt+1, list[i][i].num+A[j]);
        }
    }

    foreach (i; 0 .. N) {
        foreach (j; 0 .. N) {
            if (j == i) continue;

            foreach (k; 0 .. N) {
                if (k == i || k == j) continue;

                City tmp = list[j][i];
                tmp.cnt += list[i][k].cnt, tmp.num += list[i][k].num;
                tmp.num -= A[i];

                if (tmp.cnt < list[j][k].cnt || (tmp.cnt == list[j][k].cnt && tmp.num > list[j][k].num)) {
                    list[j][k] = tmp;
                }
            }
        }
    }

    long Q;
    readf("%d\n", Q);

    foreach (_; 0 .. Q) {
        long U, V;
        readf("%d %d\n", U, V);

        --U, --V;

        if (list[U][V].cnt == long.max / 4) {
            writeln("Impossible");
        }
        else {
            writeln(list[U][V].cnt, " ", list[U][V].num);
        }
    }
}