ABC278参加記

5完1ペナ98分 1916位

A問題

問題文中の操作をそのまま実施する。

import std;

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

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

    foreach (_; 0 .. K) {
        A.popFront;
        A ~= 0;
    }

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

B問題

見間違えやすい時刻になるまで1分ごと時刻をすすめる。

import std;

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

    while (true) {
        int h1 = H / 10, h2 = H % 10;
        int w1 = W / 10, w2 = W % 10;

        int h = h1 * 10 + w1, w = h2 * 10 + w2;

        bool isOK = (h <= 23 && w <= 59);

        if (isOK) break;

        ++W;
        if (W >= 60) {
            H = (H + 1) % 24, W = 0;
        }
    }

    writeln(H, " ", W);
}

C問題

フォロー関係を連想配列を用いて管理する。

import std;

struct Pair {
    int a, b;
}

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

    bool[Pair] list;
    foreach (_; 0 .. Q) {
        int T, A, B;
        readf("%d %d %d\n", T, A, B);

        auto P = Pair(A, B);
        auto R = Pair(B, A);

        if (T == 1) {
            list[P] = true;
        }
        else if (T == 2) {
            list[P] = false;
        }
        else {
            bool isOK = ((P in list) && list[P] && (R in list) && list[R]);
            writeln(isOK ? "Yes" : "No");
        }
    }
}

D問題

上手い実装方法がわからなかったのでこちらの記事を参考に遅延セグ木を実装して解いた。

import std;

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

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

    long L = 1;
    while (L < N) L *= 2;

    long S = L * 2;

    auto data = new long[](S), temp = new long[](S);
    temp[] = long.min;

    foreach (i, a; A) data[L+i-1] = a;

    foreach_reverse (i; 0 .. L-1) data[i] = data[i*2+1] + data[i*2+2];

    void eval(long x) {
        if (temp[x] != long.min) {
            data[x] = temp[x];
            if (x < L - 1) {
                temp[x*2+1] = temp[x*2+2] = temp[x] / 2;
            }
            temp[x] = long.min;
        }
    }

    void sumData(ref long x, long s = 0, long t = N, long l = 0, long r = L, long n = 0) {
        eval(n);
        if (r <= s || t <= l) {
            return;
        }
        else if (s <= l && t >= r) {
            x += data[n];
        }
        else {
            sumData(x, s, t, l, (l+r)/2, n*2+1);
            sumData(x, s, t, (l+r)/2, r, n*2+2);
        }
    }

    void updateData(long x, long s = 0, long t = N, long l = 0, long r = L, long n = 0) {
        eval(n);
        if (r <= s || t <= l) {
            return;
        }
        else if (s <= l && t >= r) {
            temp[n] = (r - l) * x;
            eval(n);
        }
        else {
            updateData(x, s, t, l, (l+r)/2, n*2+1);
            updateData(x, s, t, (l+r)/2, r, n*2+2);
            data[n] = data[n*2+1] + data[n*2+2];
        }
    }

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

    foreach (_; 0 .. Q) {
        auto query = readln.chomp.split.to!(long[]);

        if (query[0] == 1) {
            updateData(query[1]);
        }
        else if (query[0] == 2) {
            long num;
            sumData(num, query[1]-1, query[1]);
            updateData(num+query[2], query[1]-1, query[1]);
        }
        else {
            long num;
            sumData(num, query[1]-1, query[1]);
            num.writeln;
        }
    }
}

E問題

二次元累積和を用いて塗りつぶしたマスに書かれている数の個数を取得して、1以上$N$以下の整数が塗りつぶされていないマスに存在するか確認する。

import std;

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

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

    auto C = new int[][][](H+1, W+1, N+1);
    foreach (i; 0 .. H) {
        foreach (j; 0 .. W) {
            ++C[i+1][j+1][A[i][j]];
        }
    }

    foreach (i; 0 .. H) {
        foreach (j; 0 .. W+1) {
            C[i+1][j][] += C[i][j][];
        }
    }

    foreach (i; 0 .. H+1) {
        foreach (j; 0 .. W) {
            C[i][j+1][] += C[i][j][];
        }
    }

    auto res = new int[][](H-h+1, W-w+1);
    foreach (i; 0 .. H-h+1) {
        foreach (j; 0 .. W-w+1) {
            int[] B = C[H][W][];

            int num;
            foreach (k; 1 .. N+1) {
                int T = C[i+h][j+w][k] - C[i+h][j][k] - C[i][j+w][k] + C[i][j][k];
                if (B[k] > T) ++num;
            }

            res[i][j] = num;
        }
    }

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