ABC277参加記

5完1ペナ89分 1245位

D言語の関数についての理解が足りなかった。 使用する言語への理解も十分に必要であると再認識させられた。

A問題

for文を使って$P_{k} = X$を満たす$k$を見つける。

import std;

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

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

    foreach (i, p; P) {
        if (p == X) writeln(i+1);
    }
}

B問題

文字列$S_{i}$に対して1文字目と2文字目が条件を満たしているかをそれぞれ確認し、$i \neq j$ならば$S_{i} \neq S_{j}$の確認には連想配列を用いる。

import std;

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

    bool isOK = true;

    string A = "HDCS";
    string B = "A23456789TJQK";

    bool[string] list;
    foreach (i; 0 .. N) {
        string S;
        readf("%s\n", S);

        isOK &= A.canFind(S[0]);
        isOK &= B.canFind(S[1]);

        if (S in list) isOK = false;

        list[S] = true;
    }

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

C問題

今いる階のはしごを使って移動できる階のうち今まで移動したことのない階に移動をするという処理を繰り返し、最高で何階へ登ることができるかを求める。

import std;

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

    int[][int] ladders;

    foreach (i; 0 .. N) {
        int A, B;
        readf("%d %d\n", A, B);

        if (!(A in ladders)) ladders[A] = [];
        ladders[A] ~= B;

        if (!(B in ladders)) ladders[B] = [];
        ladders[B] ~= A;
    }

    int res;
    bool[int] seen;

    void f(int pos) {
        res = max(res, pos);
        seen[pos] = true;

        if (pos in ladders) {
            foreach (l; ladders[pos]) {
                if (l in seen) continue;
                f(l);
            }
        }
    }

    f(1);

    res.writeln;
}

D問題

$A_{i}$の大きい順から$A_{i}$の合計と$A_{i} + 1 \, \text{mod} \, M$の合計を再帰関数で求めていき、その最大値を$A_{i}$の合計から引いたものが最小値となると考察した。

import std;

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

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

    BinaryHeap!(Array!long, "a < b")[long] heaps;
    long[] list;
    foreach (a; A) {
        long m = a % M;

        if (!(m in heaps)) {
            auto tmp = Array!long([a]);
            heaps[m] = heapify!"a < b"(tmp);
            list ~= a;
        }
        else {
            heaps[m].insert(a);
        }
    }

    list.sort!"a > b";

    long[long] nums;
    bool[long] seen;

    long func(long x) {
        seen[x] = true;
        long m = x % M, f = heaps[m].front, s = f;
        heaps[m].popFront;

        while (!heaps[m].empty && heaps[m].front == f) {
            s += f;
            heaps[m].popFront;
        }

        long nxt = (x + 1) % M;
        if (nxt in heaps) {
            if (nxt in nums) s += nums[nxt];
            else {
                if (!heaps[nxt].empty) s += func(nxt);
            }
        }

        nums[x] = s;
        return s;
    }

    long num;
    foreach (l; list) {
        if (l in seen) continue;
        num = max(num, func(l));
    }

    long res = A.sum - num;
    res.writeln;
}

E問題

ダイクストラ法を用いて頂点$N$に到達するまでに行う移動の回数の最小値を求める。

import std;

struct Move {
    int to, sw, cnt;
}

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

    auto edges = new int[][][](N, 2);
    foreach (_; 0 .. M) {
        int u, v, a;
        readf("%d %d %d\n", u, v, a);

        --u, --v;
        edges[u][a] ~= v, edges[v][a] ~= u;
    }

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

    auto list = new bool[](N);
    foreach (x; s) list[x-1] = true;

    auto cnts = new int[][](N, 2);
    foreach (i; 0 .. N) cnts[i][] = int.max;
    cnts[0][1] = 0;

    auto heap = new BinaryHeap!(Array!Move, "a.cnt > b.cnt")();
    heap.insert(Move(0, 1, 0));
    while (!heap.empty) {
        auto f = heap.front;
        heap.popFront;

        foreach (e; edges[f.to][f.sw]) {
            if (cnts[e][f.sw] > f.cnt + 1) {
                cnts[e][f.sw] = f.cnt + 1;
                heap.insert(Move(e, f.sw, f.cnt+1));
            }
        }

        if (list[f.to]) {
            if (cnts[f.to][(f.sw+1)%2] > f.cnt) {
                cnts[f.to][(f.sw+1)%2] = f.cnt;
                heap.insert(Move(f.to, (f.sw+1)%2, f.cnt));
            }
        }
    }

    int mn = cnts[N-1].minElement;

    int res = (mn == int.max ? -1 : mn);
    res.writeln;
}