ABC 390

Table of Contents

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

dp の遷移方法が思いつかなかった。