ABC 390

Sat, Jan 25, 2025

B - Geometric Sequence

https://atcoder.jp/contests/abc390/tasks/abc390_b

等比数列の問題

解き方が思いつかなくてテンパった。

$\lfloor \frac{A_{i+1}}{A_i} \rfloor$ を $i = 1\sim N-1$ ですべて一致するか見ようとしたが項比が非整数のときに対応できなくてサンプルでまず落ちる。項比を double で扱ったとしても 999999998 999999999 1000000000 のような数列のときに誤差のせいで $\frac{999999998}{999999999} == \frac{999999999}{1000000000}$ が true を返してしまう。有理数だったらちゃんと比較できるのだけれどもということを思いついてようやく整数演算で確かめる方法を思いついた。

$\displaystyle \frac{A_{i+1}}{A_{i}} = \frac{A_{i+2}}{A_{i+1}} \rightarrow A_{i+1}^{2} = A_{i} A_{i+2}$ が成り立っているかを確かめればいい

void solve() {
    ll N;
    cin >> N;

    vector<double> v(N);
    rep(i, N) {
        cin >> v[i];
    }

    if (N <= 2) {
        yesno(true);
        return;
    }

    rep(i, N - 2) {
        ll a = v[i], b = v[i + 1], c = v[i + 2];
        if (b * b != a * c) {
            yesno(false);
            return;
        }
    }
    yesno(true);
}

C - Paint to make a rectangle

黒マスがある行番号の最小値、最大値をそれぞれ $i_{\mathrm{ min }}, i_{\mathrm{ max }}$ とし, 黒マスのある列番号の最小値、最大値をそれぞれ $j_{\mathrm{ min }}, j_{\mathrm{ max }}$ とする。

黒マス全体で長方形をなすときの最小の長方形は $i_{\mathrm{min}} \leq i \leq i_{\mathrm{max}}$, $j_{\mathrm{min}} \leq j \leq j_{\mathrm{max}}$ を満たす領域が全て黒マスのときである。よってこの領域に白マスがあれば No, なければ Yes.

void solve() {
    ll H, W;
    cin >> H >> W;

    vector<string> grid(H);
    rep(i, H) cin >> grid[i];

    ll minh = INF, maxh = -1, minw = INF, maxw = -1;
    rep(i, H) {
        rep(j, W) {
            if (grid[i][j] == '#') {
                chmin(minh, i);
                chmax(maxh, i);
                chmin(minw, j);
                chmax(maxw, j);
            }
        }
    }

    int ok = 1;
    for (ll i = minh; i <= maxh; i++) {
        for (ll j = minw; j <= maxw; j++) {
            if (grid[i][j] == '.') {
                ok = 0;
                break;
            }
        }
    }
    yesno(ok);
}

D - Stone XOR

考えられる数の組み合わせの数はおそらく大した数じゃないから全列挙すればいいのだろうとは思ったが、全列挙の仕方がわからなかった。

E - Vitamin Balance

2025/01/29 memo dp の遷移方法が思いつかなかった。

2025/6/18 自力で AC. 模範解答とは違う方針で解いた。

$dp(i, j)$ をカロリー $j$ を使って接種できるビタミン $i$ の量の最大値として DP テーブルを構築しておく。各ビタミンを $x$ 以上摂取するときに必要になるカロリーの最小値を求め、合計が $X$ 以下であれば求める下限は $x$ となる。 $X$ を超えたときは $x$ を下げていく。 $x$ は二分探索で求めることができる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, X;
    cin >> N >> X;

    vector<vector<pair<ll, ll>>> vitamin(3);
    rep(i, N) {
        ll v, a, c;
        cin >> v >> a >> c;
        v--;
        vitamin[v].emplace_back(a, c);
    }

    ll cmax = 5000;
    vvll dp(3, vll(cmax + 1, -1));
    rep(i, 3) {
        dp[i][0] = 0;
        for (auto [a, c] : vitamin[i]) {
            for (int j = cmax; j - c >= 0; j--) {
                if (dp[i][j - c] >= 0)
                    chmax(dp[i][j], dp[i][j - c] + a);
            }
        }
    }

    auto f = [&](ll x) -> bool {
        ll tot = 0;
        rep(i, 3) {
            ll t = X + 1;
            rep(j, cmax + 1) {
                if (dp[i][j] >= x) {
                    t = j;
                    break;
                }
            }
            tot += t;
        }
        return tot <= X;
    };

    ll ac = 0, wa = INF;
    while (wa - ac > 1) {
        ll wj = (wa + ac) / 2;
        if (f(wj)) {
            ac = wj;
        } else {
            wa = wj;
        }
    }
    cout << ac << endl;
}

ABC 390

Table of Contents

B - Geometric Sequence

C - Paint to make a rectangle

D - Stone XOR

E - Vitamin Balance