ABC300参加記

4完1ペナ57分 1374位

デバッグ用コードをそのまま提出して1ペナしてしまったのが、とても勿体無い。

A問題

for文を使って$C$内に$A+B$の位置を全探索する。

import std;

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

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

    foreach (i, c; C) {
        if (A + B == c) {
            writeln(i+1);
        }
    }
}

B問題

4重ループを用いて$A$の座標をずらして$B$と一致するか確認する。

import std;

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

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

    auto B = new dchar[][](H);
    foreach (i; 0 .. H) B[i] = readln.chomp.to!(dchar[]);

    bool isOK = false;
    foreach (i; 0 .. H) {
        foreach (j; 0 .. W) {
            bool flag = true;
            foreach (k; 0 .. H) {
                foreach (l; 0 .. W) {
                    if (A[(i+k)%H][(j+l)%W] != B[k][l]) {
                        flag = false;
                    }
                }
            }

            if (flag) {
                isOK = true;
            }
        }
    }

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

C問題

まず、バツ印の中心となる位置を探索する。 その位置から再帰関数を用いてバツ印のサイズを求める。

import std;

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

    auto C = new dchar[][](H);
    foreach (i; 0 .. H) C[i] = readln.chomp.to!(dchar[]);

    auto res = new int[](min(H, W));

    int f(int x, int y) {
        if (x < H && y < W && C[x][y] == '#') {
            return f(x+1, y+1) + 1;
        }
        return 0;
    }

    foreach (i; 1 .. H-1) {
        foreach (j; 1 .. W-1) {
            if (C[i][j] == '.') continue;

            if (C[i-1][j-1] == '#' && C[i-1][j+1] == '#' && C[i+1][j-1] == '#' && C[i+1][j+1] == '#') {
                ++res[f(i, j)-2];
            }
        }
    }

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

D問題

エラトステネスの篩を用いて$\sqrt(10^{12}) = 10^6$以下の素数を求める。 そこから、$(a < c)$かつ$(a^{2} * c^{2} \leq N)$を満たすように素数の配列を2重ループさせて$b = N / (a^{2} * c^{2})$として、二分探索を使って$a < p < min(b+1, c)$を満たす素数$p$の総和を求める。

import std;

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

    long L = 10 ^^ 6;
    auto sieve = new bool[](L+1);
    sieve[2..L+1] = true;
    long d = 2;
    while (d * d <= L) {
        if (sieve[d]) {
            foreach (i; iota(d*d, L+1, d)) {
                sieve[i] = false;
            }
        }
        ++d;
    }

    auto primes = iota(L+1).filter!(i => sieve[i]).array;
    auto sorted = primes.assumeSorted;
    auto squares = primes.map!(x => x * x).array;

    long res;
    foreach (c, c2; zip(primes, squares)) {
        foreach (a, a2; zip(primes, squares)) {
            if (a >= c) break;
            if (a2 * c2 >= N) break;

            long b = N / (c2 * a2);
            if (b <= a) continue;

            auto lba = sorted.lowerBound(a+1);
            auto lbc = sorted.lowerBound(min(c, b+1));

            res += lbc.length.to!long - lba.length.to!long;
        }
    }

    res.writeln;
}