ABC291参加記

6完2ペナ95分 931位

初めてABCで6完できたのでめちゃくちゃ嬉しいです。

A問題

isUpper関数を用いて大文字判定を行う。

import std;

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

    foreach (i, s; S) {
        if (std.uni.isUpper(s)) {
            writeln(i+1);
        }
    }
}

B問題

配列$X$をソートして$X_{N}$から$X_{4N-1}$までの合計を$3N$で割った値が答えとなる。

import std;

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

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

    X.sort;

    real res = 0.0;
    foreach (i; N .. N*4) {
        res += X[i].to!real;
    }

    res /= N * 3.0;

    writefln("%.10f", res);
}

C問題

連想配列を用いて同じ座標にいたことがあるかどうかを判定する。

import std;

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

    auto L = S.length + 1;

    long pos;
    bool[long] seen;
    seen[pos] = true;
    bool isOK;
    foreach (s; S) {
        if (s == 'R') pos += L;
        if (s == 'L') pos -= L;
        if (s == 'U') ++pos;
        if (s == 'D') --pos;

        if (pos in seen) isOK = true;

        seen[pos] = true;
    }

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

D問題

DPで解く。 配列を$A$と$B$の2つ持つのではなく二次元配列として持つことで加算処理をfor文で書くことができたと反省。

import std;

enum long MOD = 998244353;

void addMod(ref long x, long y) {
    x = (x + y) % MOD;
}

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

    auto A = new long[](N), B = new long[](N);
    foreach (i; 0 .. N) readf("%d %d\n", A[i], B[i]);

    auto dp = new long[][](N, 2);
    dp[0][] = 1;
    foreach (i; 1 .. N) {
        if (A[i] != A[i-1]) addMod(dp[i][0], dp[i-1][0]);
        if (A[i] != B[i-1]) addMod(dp[i][0], dp[i-1][1]);
        if (B[i] != A[i-1]) addMod(dp[i][1], dp[i-1][0]);
        if (B[i] != B[i-1]) addMod(dp[i][1], dp[i-1][1]);
    }

    long res = dp[$-1].sum % MOD;
    res.writeln;
}

E問題

順序を確認するためにトポロジカルソートを行う。 トポロジカルソートの処理途中で発見した入次数$0$の頂点が複数ある状態があれば配列$A$は一意に特定できないため、Noと出力して処理を終了する。

import std;

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

    auto cnts = new int[](N+1);
    auto edges = new int[][](N+1);
    foreach (_; 0 .. M) {
        int X, Y;
        readf("%d %d\n", X, Y);

        ++cnts[Y];
        edges[X] ~= Y;
    }

    int[] heap;
    foreach (i; 1 .. N+1) {
        if (cnts[i] == 0) {
            heap ~= i;
        }
    }

    int[] A;
    while (!heap.empty) {
        if (heap.length >= 2) {
            writeln("No");
            return;
        }

        auto f = heap.front;
        heap.popFront;

        A ~= f;

        foreach (e; edges[f]) {
            --cnts[e];
            if (cnts[e] == 0) heap ~= e;
        }
    }

    auto res = iota(1, N+1).array;
    zip(A, res).sort!"a[0] < b[0]";

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

F問題

都市$1$から各都市への移動に必要なテレポーターの使用回数の最小値と都市$N$から各都市への移動に必要なテレポーターの使用回数の最小値をBFSで前計算する。 各都市から他の都市へ移動できる個数が最大で$M(\leq 10)$であるため、都市間の個数から$k = 2,3,…N-1$に対して、kを通らずに都市$1$から都市$N$へ移動できるかを全探索で求める。

import std;

enum int L = 10 ^^ 9;

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

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

        foreach (j; 0 .. M) {
            if (S[j] == '1' && i + j + 1 < N) {
                edges1[i] ~= i + j + 1;
                edges2[i+j+1] ~= i;
            }
        }
    }

    auto dist1 = new int[](N);
    dist1[1..$] = L;

    int[] heap1;
    heap1 ~= 0;
    while (!heap1.empty) {
        auto f = heap1.front;
        heap1.popFront;

        foreach (e; edges1[f]) {
            if (dist1[e] > dist1[f] + 1) {
                dist1[e] = dist1[f] + 1;
                heap1 ~= e;
            }
        }
    }

    auto dist2 = new int[](N);
    dist2[0..$-1] = L;

    int[] heap2;
    heap2 ~= N - 1;
    while (!heap2.empty) {
        auto f = heap2.front;
        heap2.popFront;

        foreach (e; edges2[f]) {
            if (dist2[e] > dist2[f] + 1) {
                dist2[e] = dist2[f] + 1;
                heap2 ~= e;
            }
        }
    }

    auto res = new int[](N-2);
    foreach (i; 1 .. N-1) {
        if (dist1[N-1] >= L) {
            res[i-1] = -1;
            continue;
        }

        int num = L;
        long p = max(0, i-M);
        foreach (j; p .. i) {
            if (dist1[j] >= L) continue;

            foreach (e; edges1[j]) {
                if (e <= i) continue;
                if (dist2[e] >= L) continue;

                num = min(num, dist1[j]+dist2[e]+1);
            }
        }

        res[i-1] = (num >= L ? -1 : num);
    }

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