ABC312参加記

4完2ペナ66分 1929位

A問題

canFind関数を用いて入力$S$が条件に当てはまるか確認する。

import std;

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

    string[] list = ["ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"];

    writeln(list.canFind(S) ? "Yes" : "No");
}

B問題

グリッドの条件が$9 \leq N, M \leq 100$であるため、2重ループで$S[i][j] (0 \leq i \leq N - 9, 0 \leq j \leq M - 9)$を左上とする$9 \times 9$の領域において条件を満たすか全探索する。

import std;

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

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

    int[] x, y;
    foreach (i; 0 .. N-8) {
        foreach (j; 0 .. M-8) {
            int b, w;
            foreach (k; 0 .. 3) {
                foreach (l; 0 .. 3) {
                    if (S[i+k][j+l] == '#') ++b;
                    if (S[i+k+6][j+l+6] == '#') ++b;

                    if (k == 0 && S[i+k+5][j+l+6] == '.') ++w;
                    if (k == 2 && S[i+k+1][j+k] == '.') ++w;
                    if (l == 0 && S[i+k+6][j+l+5] == '.') ++w;
                    if (l == 2 && S[i+k][j+l+1] == '.') ++w;
                }
            }

            if (S[i+3][j+3] == '.') ++w;
            if (S[i+5][j+5] == '.') ++w;

            if (b == 18 && w == 14) {
                x ~= i + 1, y ~= j + 1;
            }
        }
    }

    foreach (u, v; zip(x, y)) {
        writeln(u, " ", v);
    }
}

C問題

$X$円以下で売ってもよいと考える売り手の人数 $\geq$ $X$円以上で買ってもよいと考える買い手の人数を満たす最小の整数$X$を二分探索で求める。

import std;

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

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

    auto C = A.sort, D = B.sort;

    long ok = B[M-1] + 1, ng;
    while (ok - ng > 1) {
        long mid = (ok + ng) / 2;

        auto x = C.lowerBound(mid+1).length;
        auto y = D.upperBound(mid-1).length;

        (x >= y ? ok : ng) = mid;
    }

    ok.writeln;
}

D問題

文字列$S$において、$|S| \leq 3000$であるため$\mathcal{0}(|S|^{2})$で解くことができる。 動的計画法により0文字目から$i (0 \leq i < |S|)$文字目までにとりうる(の個数 - )の個数を管理することで解くことができる。

import std;

enum long MOD = 998244353;

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

    auto l = S.length;

    auto dp = new long[][](l+1, l+1);
    dp[0][0] = 1;
    foreach (i, s; S) {
        foreach (j; 0 .. i+1) {
            if (s == '(') {
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD;
            }
            else if (s == ')') {
                if (j > 0) {
                    dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD;
                }
            }
            else {
                dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD;
                if (j > 0) {
                    dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % MOD;
                }
            }
        }
    }

    long res = dp[l][0];
    res.writeln;
}