ABC293参加記

5完4ペナ105分 1122位

A問題

swapAt関数を用いて、$i = 1, 2, …, \frac{|S|}{2}$に対して順に$S_{2i-1}$と$S_{2i}$を入れ替える。

import std;

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

    auto len = S.length;
    foreach (i; 0 .. len/2) {
        S.swapAt(i*2, i*2+1);
    }

    S.writeln;
}

B問題

人$i (1 \leq i \leq N)$がまだ呼ばれているかどうかを記憶する配列を用意する。 人$i$は自分自身がまだ呼ばれていなければ人${A_{i}}$を呼ぶという処理を人1から順に行う。

import std;

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

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

    auto call = new bool[](N+1);
    call[0] = true;
    foreach (i, a; A) {
        if (call[i+1]) continue;

        call[a] = true;
    }

    auto res = iota(1, N+1).filter!(a => !call[a]).array;
    res.length.writeln;
    writefln("%(%s %)", res);
}

C問題

DFSを用いて視点から終点まで異なる整数が書かれた経路を求める。 連想配列を用いて経路に含まれる整数を管理する。

import std;

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

    auto A = new int[][](H, W);
    foreach (i; 0 .. H) A[i] = readln.chomp.split.to!(int[]);

    int res;
    bool[int] used;
    used[A[0][0]] = true;
    void f(int x, int y) {
        if (x == H - 1 && y == W - 1) {
            ++res;
        }
        else {
            if (x < H - 1 && A[x+1][y] !in used) {
                used[A[x+1][y]] = true;
                f(x+1, y);
                used.remove(A[x+1][y]);
            }
            if (y < W - 1 && A[x][y+1] !in used) {
                used[A[x][y+1]] = true;
                f(x, y+1);
                used.remove(A[x][y+1]);
            }
        }
    }

    f(0, 0);

    res.writeln;
}

D問題

Union-Findを用いて閉路検出を行う。 ロープの端の色を管理するためにUnion-Findの根の個数を$2N$とする。 $i (1 \leq i \leq N)$番目の赤色の端を$2i-1$番目の根、青色の端を$2i$番目の根として管理する。

import std;

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

    auto uf = new UnionFind!int(N*2);
    foreach (i; 0 .. N) {
        uf.unite(i*2, i*2+1);
    }

    int c;
    foreach (_; 0 .. M) {
        int A, C;
        dchar B, D;
        readf("%d %c %d %c\n", A, B, C, D);

        --A, --C;

        A *= 2, C *= 2;
        if (B == 'B') ++A;
        if (D == 'B') ++C;

        if (uf.root(A) == uf.root(C)) {
            ++c;
        }

        uf.unite(A, C);
    }

    int d;
    foreach (i; 0 .. N*2) {
        if (i == uf.root(i)) {
            ++d;
        }
    }

    d -= c;

    writeln(c, " ", d);
}

/// Union-Find
struct UnionFind(T)
if (isIntegral!T) {

    /// Constructor
    this(T n) nothrow @safe {
        len = n;
        par.length = len;
        cnt.length = len;
        foreach (i; 0 .. len) {
            par[i] = i;
        }
        cnt[] = 1;
    }

    /// Returns the root of x.
    T root(T x) nothrow @nogc @safe
    in (0 <= x && x < len) {
        if (par[x] == x) {
            return x;
        }
        else {
            return par[x] = root(par[x]);
        }
    }

    /// Returns whether x and y have the same root.
    bool isSame(T x, T y) nothrow @nogc @safe
    in (0 <= x && x < len && 0 <= y && y < len) {
        return root(x) == root(y);
    }

    /// Unites x tree and y tree.
    void unite(T x, T y) nothrow @nogc @safe
    in (0 <= x && x < len && 0 <= y && y < len) {
        x = root(x), y = root(y);
        if (x == y) {
            return;
        }

        if (cnt[x] > cnt[y]) {
            swap(x, y);
        }

        cnt[y] += cnt[x];
        par[x] = y;
    }

    /// Returns the size of the x tree.
    T size(T x) nothrow @nogc @safe
    in (0 <= x && x < len) {
        return cnt[root(x)];
    }

private:
    T len;
    T[] par;
    T[] cnt;
}

E問題

等比数列の和$\sum_{i=0}^{X-1}A^{i}$を$M$で割った余りを求める問題である。 等比数列の和 modと検索してヒットしたこちらの記事を参考に実装した。

import std;

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

    A %= M;

    long f(long x, long y, long z, long MOD) {
        if (z == 1) {
            return x % MOD;
        }
        long n = f(x, y, z/2, MOD);
        long ret = (n + powMod(y, z/2, M) * n) % MOD;
        if (z % 2 == 1) {
            ret = (x + y * ret) % MOD;
        }
        return ret;
    }

    long res = f(1, A, X, M);
    res.writeln;
}

long powMod(long x, long y, long z) {
    long res = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            res *= x;
            if (res > z) res %= z;
        }
        x *= x;
        if (x > z) x %= z;
        y /= 2;
    }
    return res;
}