AtCoder部 2026-03-11

ABC357 D - 88888888

ダブリング。

int main() {
    ll N;
    cin >> N;
    ull w = 1;
    while (w <= N) w *= 10;
    vector<mint> a(60);
    a[0] = N;
    for (int i = 1; i < 60; i++) {
        a[i] = a[i - 1] * mint(w).pow(1LL << (i - 1)) + a[i - 1];
    }
    mint ans = 0;
    for (int i = 59; i >= 0; i--) {
        if (BIT(N, i)) {
            ans = ans * mint(w).pow(1LL << i) + a[i];
        }
    }
    cout << ans.val() << NL;
}

ABC359 C - Tile Distance 2

スタートとゴールをタイルの左側に寄せておく（これは x+y が奇数なら x を 1 減らすとすればいい）。

y 方向に 1 移動するときは必ずコスト 1 かかる。ただし、y 方向に 1 移動するとき、追加コストなしで x 方向に 1 移動できる。それで足りない分については、 x 方向に 2 移動するごとにコスト 1 かかる。結局、合計コストは $|t_y-s_y|+\max(|t_x-s_x|-|t_y-s_y|, 0)/2$ となる。

int main() {
    ll sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    if ((sx + sy) % 2) sx--;
    if ((tx + ty) % 2) tx--;
    ll dx = abs(tx - sx), dy = abs(ty - sy);
    ll ans = dy + max(dx - dy, 0LL) / 2;
    cout << ans << NL;
}

ABC389 D - Squares in Circle

対称性から $i \ge 0, j \ge 0$ かつ $(i+1/2)^2+(j+1/2)^2 \le R$ を満たす $(i, j)$ を数えればよい。 各 $i$ について条件を満たす $j$ の個数を数えて足し合わせることにする。 $i$ を固定すると、$j$ が満たすべき条件は $j \le \sqrt{R^2-(i+1/2)^2}-1/2$ となる。$i \ge R$ のときは明らかに条件を満たす $j$ が存在しないから、$R$ 未満の $i$ だけ考えればいい。

int main() {
    double R;
    cin >> R;
    ll ans = 0;
    for (int i = 0; i < R; i++) {
        double j = sqrt(R * R - (i + 0.5) * (i + 0.5)) - 0.5;
        int cnt = 0;
        if (j >= 0) {
            cnt += floor(j) * 2 + 1;
        }
        if (i == 0)
            ans += cnt;
        else
            ans += cnt * 2;
    }
    cout << ans << NL;
}