2021-06-12

AtCoder ABC 023 D - 射撃王 (試験管青色)

AtCoder 旧ABC 二分探索最大値の最小化 Greedy Greedy:どちらも可なら厳しい方スケジューリング順列の最適化問題最小コストけんちょん本演習問題競プロ典型90問とその類題【問題集】二分探索の入門そのまま覚えたい典型問題典型要素を詰め合わせた教育的問題最適化問題

大昔の ABC の問題ですが、今なお色あせない教育的良問。二分探索の練習問題に。

問題へのリンク

問題概要

$N$ 個の風船がそれぞれ初期状態では高度 $H_{1}, H_{2}, \dots, H_{N}$ の位置にあり、1 秒ごとに $S_{1}, S_{2}, \dots, S_{N}$ ずつ上昇する。これらすべての風船を射撃によって割りたい。

競技開始時に 1 個風船を割ることができ、そこから 1 秒ごとに 1 個の風船を割ることができる。最終的にすべての風船を割りたいですが、どの順番に風船を割るかは自由に選べるものとする。

各風船を割るときに発生するペナルティは、そのときの風船の高度とする。最終的なペナルティは、各風船を割ったときに発生するペナルティの最大値とする。

最終的なペナルティとして考えられる最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le H_{i}, S_{i} \le 10^{9}$
入力はすべて整数

考えたこと

けんちょん本 6.7 節「二分探索法の応用例 (3)：最適化問題を判定問題に」で取り上げている。ここではごく簡単に。

一見すると難しい問題に見えてしまうかもしれない。要するに、すべての風船をある程度の高度で割りたいのだ。なので、初めから低い高度にある風船はある程度放置して後回しにしてもよいかもしれない。高い高度にある風船であっても上昇スピードが遅ければ後回しにしてもいいかもしれない。こういうことを考えてると、風船を割る優先順位を定めるのがとても難しそうだ...

しかし、これが次のような判定問題となった途端に、一気に優先順位が決まってくるのだ！！！！！！！

すべての風船を高度 $x$ 以内で割ることは可能か判定せよ。

この判定問題が解けるならば、二分探索法によって十分高速に問題を解くことができる。

判定問題

すべての風船を高度 $x$ 以内に割りたいと、デッドラインを決めた時点で、風船を割る優先順位は自ずと定まってくる。

まず各風船 $i$ について、デッドラインに達するまでの時間を求めることができる。

$t_{i} = (x - H_{i}) / S_{i}$

という感じだ。これが小さい順、つまりデッドラインが最も差し迫っている順に風船を割っていくのが最適だ。デッドラインが差し迫っている順に風船を割っていって、割り切れたら「可能」、割り切れなかったら「不可能」となる。

コード

計算量は、

判定問題を解く回数： $O(\log M)$ 　( $M = \max(H_{1} + NS_{1}, \dots, H_{N} + NS_{N})$ )
判定問題を解く： $O(N \log N)$ 　(デッドラインが逼迫する順にソートする部分がボトルネック)

ということで、全体として $O(N \log N \log M)$ となる。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const long long INF = 1LL << 60; // 十分大きい値を 1 つ決める

int main() {
    // 入力
    int N;
    cin >> N;
    vector<long long> h(N), s(N);
    for (int i = 0; i < N; i++) cin >> h[i] >> s[i];

    // 二分探索
    long long left = 0, right = INF;
    while (right - left > 1) {
        long long mid = (left + right) / 2;
        
        // 判定
        bool ok = true;
        vector<long long> t(N, 0); // 各風船を割るまでの制限時間
        for (int i = 0; i < N; ++i) {
            // そもそも mid が初期高度より低かったらfalse
            if (mid < h[i]) ok = false; 
            else t[i] = (mid - h[i]) / s[i];
        }
        // 時間制限がさし迫っている順にソート
        sort(t.begin(), t.end()); 
        for (int i = 0; i < N; ++i) {
            if (t[i] < i) ok = false; // 時間切れ発生
        }

        if (ok) right = mid;
        else left = mid;
    }

    cout << right << endl;
}

2021-06-12

AtCoder ARC 117 C - Tricolor Pyramid (青色, 600 点)

AtCoder AtCoder600点 ARC-C 青色diff ピラミッド不変量倍数判定や九去法二項係数係数を考える色に関する問題変数変換して扱いやすい同型な問題を見出す 0と1と2の問題操作後の結果を求める問題

面白かった。リハビリになった。

問題へのリンク

問題概要

長さ $N$ の "B", "W", "R" からなる文字列が与えられます。これに対して、次の操作を $N-1$ 回繰り返して、最終的に得られる文字 (1 文字) を答えよ。

それぞれの隣り合う 2 文字に対して
- それらが同じ文字ならば、その文字を対応させる
- それらが異なる文字ならば、残りの文字を対応させる

f:id:drken1215:20210611222958p:plain

制約

$2 \le N \le 4 \times 10^{5}$

考えたこと

この手の問題は、まずは

"B" → 0
"W" → 1
"R" → 2

という風に変換して考えたくなる。そしてきっと操作の前後で、「なんらかの量」を考えると、それが不変になってるんだろうな...という想像を働かせていくのが良さそう。

さて、0, 1, 2 で考えると、

(0, 0) → 0
(1, 1) → 1
(2, 2) → 2
(0, 1), (1, 0) → 2
(1, 2), (2, 1) → 0
(2, 0), (0, 2) → 1

となっている。mod. 3 で考えると良さそうだとあたりをつけると、

$(a, b)$ → $- (a + b)$

となっていることに気づく。たとえば

(1, 1) → -2 ≡ 1 (mod. 3)
(1, 2) → -3 ≡ 0 (mod. 3)

という感じ。

二項係数の重複度

$N = 5$ くらいで具体的に書き出してみると、

$(a, b, c, d, e)$
→ $(-a-b, -b-c, -c-d, -d-e)$
→ $(a+2b+c, b+2c+d, c+2d+e)$
→ $(-a-3b-3c-d, -b-3c-3d-e)$
→ $(a+4b+6c+4d+e)$

という風になっていく。一般に、パスカルの三角形と同じ原理で、 $c_{0}, c_{1}, \dots, c_{N-1}$ に対して、 ${}_{N-1}{\rm C}_{0}, {}_{N-1}{\rm C}_{1}, \dots, {}_{N-1}{\rm C}_{N-1}$ を係数にかけて総和をとった値になるのだ。ただし、 $N$ が偶数のときは $-1$ 倍になる。

まとめ

以上から、

${}_{N-1}{\rm C}_{r}$ (mod. 3)

が計算できればよいことがわかった。これは任意 mod nCr のライブラリを使った。

全体として計算量は、 $O(N)$ になる。

github.com

#include <bits/stdc++.h>
using namespace std;

// mod function
long long mod(long long a, long long mod) {
    return (a % mod + mod) % mod;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    long long b = mod, u = 1, v = 0;
    while (b) {
        long long t = a/b;
        a -= t * b, swap(a, b);
        u -= t * v, swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

// binomial coefficient
struct BiCoef {
    // max size of n of nCr
    int n_;
    
    // pm = p^k, p is prime
    // mod pm
    long long p_, pm_;
    
    // i! = p^ord[i] * fact[i] (mod. m)
    vector<long long> ord_, fact_;

    // constructor
    BiCoef(int n) : n_(n), ord_(n), fact_(n) {}
    BiCoef(long long p, long long pm, int n) :
        n_(n), p_(p), pm_(pm), ord_(n), fact_(n) {
        init(p, pm);
    }
    void init(int n) {
        ord_.resize(n);
        fact_.resize(n);
    }
    void init(long long p, long long pm) {
        p_ = p, pm_ = pm;
        ord_[0] = ord_[1] = 0;
        fact_[0] = fact_[1] = 1;
        for (int i = 2; i < n_; i++) {
            long long add = 0;
            long long ni = i;
            while (ni % p == 0) ++add, ni /= p;
            ord_[i] = ord_[i-1] + add;
            fact_[i] = fact_[ni-1] * ni % pm;
        }
    }
    void init(long long p, long long pm, int n) {
        init(n);
        init(p, pm);
    }

    // nCr mod. pm
    long long com(long long n, long long r) {
        if (n < 0 || r < 0 || n < r) return 0;
        long long e = ord_[n] - ord_[r] - ord_[n-r];
        long long res = fact_[n] * modinv(fact_[r] * fact_[n-r] % pm_, pm_) % pm_;
        res = res * modpow(p_, e, pm_) % pm_;
        return res;
    }
};

string check = "BWR";
int main() {
    int N;
    string S;
    cin >> N >> S;

    BiCoef bf(3, 3, N);
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        int val = 0;
        if (S[i] == 'W') val = 1;
        else if (S[i] == 'R') val = 2;
        res += bf.com(N - 1, i) * val % 3;
    }
    res %= 3;
    if (N % 2 == 0) res = (3 - res) % 3;
    cout << check[res] << endl;
}

2021-05-10

AtCoder AGC 053 A - >< again (水色, 400 点)

AtCoder AtCoder400点 AGC-A 水色diff >< 構築構築:数列最適化テク:自明な上界が最適解鳩の巣原理均等に分ける絶対値やminを扱う問題数列最大スコア最適化問題

自明な上界を達成できるパターンだった！

問題へのリンク

問題概要

長さ $N+1$ の非負整数列 $A_{0}, A_{1}, \dots, A_{N}$ が与えられる。この数列はどの隣接する二項も値が異なる。

この数列をなるべく多くの $N+1$ 項の非負整数列へと分解せよ。分解とは

分解された各非負整数列の各項を足すと、もとの数列 $A$ に一致する
どの分解された非負整数列も、隣接二項間の大小関係が、もとの数列 $A$ に一致する

という条件を満たすことを指す。

制約

$1 \le N \le 100$
$0 \le A_{i} \le 10^{4}$

考えたこと

サンプルを見てみる。 $A = (3, 8, 6, 10)$ は、次の 2 つの整数列に分解できる。

$(2, 4, 3, 5)$
$(1, 4, 3, 5)$

3 つには分解できない。なぜならば、8 - 6 = 2 だからだ。もし 3 つに分解できたとすると、合計したときに、二項目と三項目との差が 3 以上にならなければならない。しかし $A_{1} - A_{2} = 2$ なのでそれは不可能だ。以上から

$K = \min_{i = 0, 1, \dots, N-1} |A_{i} - A_{i+1}|$ より多く分解することはできない

ということがいえた。

$K = \min_{i = 0, 1, \dots, N-1} |A_{i} - A_{i+1}|$ は達成可能

逆に、 $K$ 個に分解することは常に可能だ。それが示されれば、 $K$ 個が最大値ということで確定する。

まずなるべく多く分解するためには、「各 $A_{i}$ をなるべく均等に $K$ 分割したい」という気持ちになる。そして余った分は上から配っていく感じで OK。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N;
    string S;
    cin >> N >> S;
    vector<long long> x(N+1);
    for (int i = 0; i < N+1; ++i) cin >> x[i];

    long long M = 1LL<<60;
    for (int i = 0; i < N; ++i) chmin(M, abs(x[i]-x[i+1]));

    vector<vector<long long>> res(M, vector<long long>(N+1));
    for (int j = 0; j <= N; ++j) {
        long long r = x[j] % M;
        for (int i = 0; i < M; ++i) {
            res[i][j] = x[j] / M;
            if (i < r) ++res[i][j];
        }
    }

    cout << M << endl;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j <= N; ++j) cout << res[i][j] << " ";
        cout << endl;
    }
}

2021-03-22

AtCoder ARC 115 B - Plus Matrix (茶色, 400 点)

AtCoder AtCoder400点 ARC-B 茶色diff 行列数列どれか1つ求める復元決めてから整合性を確認する Yes/No判定問題最大値や最小値に着目する

「決めてから、整合性を確認する」というタイプの問題の典型例ですね！

問題へのリンク

問題概要

$N \times N$ の非負整数を成分とする行列 $C$ が与えられる。

すべての $(i,j)$ について $C_{i,j} = A_{i} + B_{j}$ を満たすような非負整数列 $A_{1}, \dots, A_{N}$ と $B_{1}, \dots, B_{N}$ の組が存在するか判定し、存在するなら一つ出力せよ。

制約

$1 \le N \le 500$

考えたこと

条件を満たすような行列 $C$ であれば、

1 7 5
3 9 7

というようになっている。つまり、

2 行目 1 列目の 3 は、1 行目 1 列目の 1 に +2 したもの
2 行目 2 列目の 9 は、1 行目 2 列目の 7 に +2 したもの
2 行目 3 列目の 7 は、1 行目 3 列目の 5 に +2 したもの

というように、2 行目の値は一律に 1 行目に同じ値を足し引きしたものとなっている。つまり、

$A_{2} = A_{1} + 2$

という風にするのが適切だということだ。

同じ理屈で、次のようなことが言える。

$A_{1}, \dots, A_{N}$ の各隣接項の差分については、1 列目のみを見れば一意に決まる
$B_{1}, \dots, B_{N}$ の各隣接項の差分については、1 行目のみを見れば一意に決まる

ということがわかる。たとえばサンプル 1 の

4 3 5
2 1 3
3 2 4

というケースであれば、

$A_{2} = A_{1} - 2$ 　(4 と 2 を比較)
$A_{3} = A_{2} + 1$ 　(2 と 3 を比較)
$B_{2} = B_{1} - 1$ 　(4 と 3 を比較)
$B_{3} = B_{2} + 2$ 　(3 と 5 を比較)

という関係が成立することが必要だと考えることができるのだ。ただしこの時点では、 $A$ や $B$ の相対的な値の関係がわかるのみであって、値が完全に決まるわけではないことに注意しよう。

とりあえず、相対的な値の関係がわかるので、最小値をとるところを 0 に設定してあげることにしよう。たとえば上のケースであれば、1 列目が (4, 2, 3) なので

$A = (2, 0, 1)$

としてあげるのが良さそうだ。同様に

$B = (1, 0, 2)$

としてあげれば OK。これだと行列 $C$ に対して「ちょうど 1 だけ足りない」という感じなので、A か B のどちらかに一律に 1 を足せば OK。B に 1 ずつ足すと

$A = (2, 0, 1)$
$B = (2, 1, 3)$

となる。

ダメな場合

逆に、

$A = (2, 0, 1)$
$B = (1, 0, 2)$

というように、一行目と一列目のみを見て決定した $A, B$ に対して、

$C_{i, j}$ と $A_{i} + B_{j}$ との差

が一定でない場合は "No" ということになる。

もう一つ、その差が負の値になる可能性 (= $A$ か $B$ に負の整数が混ざってしまう可能性) があるのではないかと気になってしまうかもしれない。しかしそれはあり得ない。なぜなら、上記のような $A, B$ の作り方をした場合、 $A_{i} + B_{j}$ の最小値は 0 になるのだ。 $C_{i, j}$ の値はすべて 0 以上であることが保証されているので、 $C_{i, j} - (A_{i} + B_{j})$ が負になることはあり得ない。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N; cin >> N;
    vector<vector<long long>> C(N, vector<long long>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> C[i][j];
    vector<long long> X(N), Y(N);
        
    auto solve = [&]() -> bool {        
        long long mix = C[0][0], miy = C[0][0];
        for (int i = 0; i < N; ++i) chmin(mix, C[i][0]), chmin(miy, C[0][i]);
        for (int i = 0; i < N; ++i) X[i] = C[i][0] - mix, Y[i] = C[0][i] - miy;

        // 差分を一律に足す
        long long dif = C[0][0] - X[0] - Y[0];
        for (int i = 0; i < N; ++i) X[i] += dif;

        // 整合性を確認する
        for (int i = 0; i < N; ++i) 
            for (int j = 0; j < N; ++j) 
                if (X[i] + Y[j] != C[i][j])
                    return false;
        return true;
    };
    
    if (solve()) {
        cout << "Yes" << endl;
        for (int i = 0; i < N; ++i) cout << X[i] << " "; cout << endl;
        for (int i = 0; i < N; ++i) cout << Y[i] << " "; cout << endl;
    }
    else cout << "No" << endl;
}

2021-03-22

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

AtCoder AtCoder500点茶色diff 彩色問題 Dilworthの定理 DAG 最大安定集合問題数学(整数問題) クリーク最適化テク:自明な上界が最適解素因数分解 mex グラフ構築どれか1つ求める数列復元最大値の最小化非自明な線形時間 ARC-C

これ茶色はさすがにびっくりした！

問題へのリンク

問題概要

整数 $N$ が与えられる。

正の整数からなる数列 $A_{1}, \dots, A_{N}$ であって、

$i$ が $j$ の約数であるような任意の $i, j$ に対して $A_{i} \neq A_{j}$

という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるようなものを一つ求めよ。

考えたこと

たとえば $N = 24$ のとき、1, 2, 4, 12, 24 というように、隣接する二要素が約数倍数関係であるようなものをとってくると、どの 2 つも約数倍数であるようになっている。

つまりこの場合、

$A_{1} = 1$
$A_{2} = 2$
$A_{4} = 3$
$A_{12} = 4$
$A_{24} = 5$

というように、絶対に「5」までは必要になるのだ。

一般に、 $N$ 以下の整数のうち、「素因数分解したときの指数の和の最大値 + 1」だけの値までは必ず必要になることが示せる。たとえば

$24 = 2^{3} \times 3^{1}$

なので、24 を含むなら 3 + 1 + 1 = 5 までは必ず必要というわけだ。

十分性

逆に、 $N$ 以下の整数のうち、「素因数分解したときの指数の和の最大値 + 1」が答えとなるような数列を具体的に作ることもできる。

具体的には、各 $n$ に対して

$A_{n}$ = $n$ を素因数分解したときの指数の和 + 1

としてあげれば、条件を満たすことになる！！！

$p$ が $q$ の約数であるとき、 $p$ を素因数分解したときの指数の和は、 $q$ を素因数分解したときの指数の和よりも真に小さいことからわかる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    auto calc = [&](long long n) -> long long {
        long long res = 1;
        if (n == 1) return res;
        for (long long p = 2; p * p <= n; ++p) {
            while (n % p == 0) {
                ++res;
                n /= p;
            }
        }
        if (n > 1) ++res;
        return res;
    };
    
    int N;
    cin >> N;
    for (long long n = 1; n <= N; ++n) cout << calc(n) << " ";
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 023 D - 射撃王 (試験管青色)

問題概要

制約

考えたこと

判定問題

コード

AtCoder ARC 117 C - Tricolor Pyramid (青色, 600 点)

問題概要

制約

考えたこと

二項係数の重複度

まとめ

AtCoder AGC 053 A - >< again (水色, 400 点)

問題概要

制約

考えたこと

$K = \min_{i = 0, 1, \dots, N-1} |A_{i} - A_{i+1}|$ は達成可能

コード

AtCoder ARC 115 B - Plus Matrix (茶色, 400 点)

問題概要

制約

考えたこと

ダメな場合

コード

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

問題概要

考えたこと

十分性

コード