ABC 239

Table of Contents

A - Horizon

問題

問題分通りの値を出力するだけ.

提出コード

B - Integer Division

問題

$X > 0$ のときは素直に整数除算 $X / 10$ を出力する.

$X < 0$ のとき, $X \equiv 0 \mod 10$ なら整数除算 $X / 10$ を出力し, $X % 10 \neq 0$ なら $X / 10 - 1$ を出力する.

void solve() {
    ll x;
    cin >> x;
    if (x < 0 && x % 10 != 0) {
        cout << x / 10 - 1 << endl;
    } else {
        cout << x / 10 << endl;
    }
}

余談

午前中に勉強していた coursera の講義 Competitive Programmer’s Core Skills Week 3 の課題で $\lceil \frac{x}{y} \rceil$ を出力する問題があって, それを解いていたおかげで $x / y$ が負のときは場合分けが必要とわかっていたため比較的にすぐに解くことができた.

提出コード

C - Knight Fork

問題

注記の図に書いてある通りで, 格子点 $(x, y)$ からの距離が $\sqrt{5}$ になる格子点の座標は $(x+1, y+2)$, $(x+2, y+1)$, $(x+2, y-1)$, $(x+1, y-2)$, $(x-1, y-2)$, $(x-2, y-1)$, $(x-2, y+1)$, $(x-1, y+2)$ の8点である.

$(x_1, y_1)$ からの距離が $\sqrt{5}$ となる格子点の集合と, $(x_2, y_2)$ からの距離が $\sqrt{5}$ となる格子点と集合に 共通要素があれば Yes, そうでなければ No を出力する.

提出コード

D - Prime Sum Game

問題

$A, B, C, D \leq 100$ と小さいので全探索する. 任意の高橋君が選んだ数字 $x$ に対して, 青木くんが常に素数を作ることができれば青木くんの勝ち. そうでなければ高橋君の勝ち.

素数判定のためにエラトステネスのふるいで素数判定配列を作っておくと楽だが, 愚直に $O(\sqrt{N})$ のアルゴリズムでの判定でも十分間に合う.

E - Subtree K-th Max

問題

解説 AC

葉から各部分木に含まれる数の上位20個を配列に保存する. このとき, 配列は降順にソートしておく. 各クエリに対してノード $V$ の $K$ 番目を出力すれば良い.

vvint graph;
vint score;
vvint child;
const int MAX_KTH = 20;

void dfs(int x, int p) {
    child[x].push_back(score[x]);

    for (int nx : graph[x]) {
        if (nx == p)
            continue;
        dfs(nx, x);
        for (int i = 1; i <= min((int)child[nx].size(), MAX_KTH); i++) {
            child[x].push_back(child[nx][i - 1]);
        }
    }

    sort(rall(child[x]));
}

提出コードだと配列に上位20個でなく, $\text{子ノードの数} \times 20 + 1$ の数が入ってくるが $k-d$ tree の $k = 20$ みたいなものなので空間計算量も大したことないので問題ない(多分).

直感的には

最悪計算量が $N\log_{20}N$ くらいになりそうな気がするが証明はできていない.

提出コード