問題概要

$ N (\leq 10^5)$枚の数字が書かれたカード $ A_1 \lt A_2 \lt \cdots \lt A_N$ を高橋くんと青木くんが交互に，カードがなくなるまで取っていく．先攻は高橋くんである．高橋くんは数字の大きいカードから順に，青木くんはあらかじめある数字 $ x$ を決めておき，その数字に近い数字のカードから順に取っていく．

いま， $ x$ の値の候補が$ Q (\leq 10^5)$ 個与えられる．それぞれについて，高橋くんが取るカードの数字の合計を求めよ．

解法概要

A が

青木くんと高橋くんが交互に取るエリア
青木くんが必ず取るエリア
高橋くんが必ず取るエリア

の順に 3 つに分けられることがわかった．このエリアの境界を $ O(log N)$とかで求めることができれば良さそう． (エリアの境界がわかれば，あとは事前にインデックスの偶奇ごとの累積和を取っておけば計算できるため)

エリア 3 の開始インデックスがわかればエリア 3 の長さがわかり，エリア 3 の長さがわかればエリア 2 の開始インデックスもわかる (方法は後述) ので，エリア 3 の開始インデックスについて考察する．

ルールより，青木くんが最初に取るカードは $ x$ に最も近い数字のカードである．これは二分探索で求められる．このカードのインデックスを $ i_\mathit{nearest}$ とすると，$ A_{i_\mathit{nearest}}$は $ A_n$でない限り必ずエリア 2 に含まれる．

$ A_{i_\mathit{nearest}} = A_n$ のときは高橋くんも青木くんも数字の大きなカードから順に取るという同じ戦略を取ることになるので，高橋くんが $ A_{i_\mathit{nearest}}$ を先に取ってしまう．この場合の高橋くんのカードの数字の合計は，カードを 1-indexed で管理しているとすると$ N$が奇数なら奇数インデックス，偶数なら偶数インデックスのカードの数字の合計になる．以下， $ A_{i_\mathit{nearest}} \neq A_n$ を仮定して考察を進める．

この仮定を付け加えると$ A_{i_\mathit{nearest}}$必ずエリア 2 に含まれるから，エリア 3 の開始インデックスは$ i_\mathit{takahashi}$について $ i_\mathit{nearest} \lt i_\mathit{takahashi} \leq n$が成り立つ．これを二分探索で求めることを考える．$ i_\mathit{nearest} \lt j \leq n$ であるカード $ A_j$ を高橋くんが取るために必要な条件は，高橋くんから見た$ A_j$ を取る優先順位 $ r_\mathit{takahashi}$と青木くんから見た$ A_j$ を取る優先順位$ r_\mathit{aoki}$ について　$ r_\mathit{takahashi} \leq r_\mathit{aoki}$ が成り立つことである．$ r_\mathit{takahashi}$ はそのカードの数字が何番目に大きいかを数えれば求まる．$ r_\mathit{aoki}$ はそのカードよりも $ x$との差が小さいカードの枚数を二分探索などで調べれば求まる．これらを利用するとエリア 3 の開始インデックスを二分探索で求めることができる．

エリア 3 の開始インデックスが求められたら，エリア 2 とエリア 3 が同じ長さになるようにエリア 2 の開始インデックスを求める．ただし例外として，カードの枚数が奇数でエリア 3 の長さが$ \lceil \frac{N}{2} \rceil$の場合のみエリア 2 よりエリア 3 が 1 短い．

エリア 2 とエリア 3 の開始インデックスが求められたので，あらかじめ計算しておいた累積和を使って高橋くんのカードの数字の合計を求めることができる．エリア 3 の開始インデックスを求める二分探索の中で，青木くんから見たカードの優先順位を調べるためにまた二分探索をしているので空間計算量は $ O(N (\log N)^2)$ といったところか．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n,m;
    cin >> n >> m;
    vector<int> a(n+1, -(1 << 30));
    for(int i=1;i<=n;++i) cin >> a[i];

    vector<vector<ll>> total(2, vector<ll>(n+1, 0)); // インデックスが偶数の累積和，インデックスが奇数の累積和
    total[1][1] = a[1];
    for(int j=2;j<=n;++j) {
        total[j%2][j] = total[j%2][j-2] + a[j];
        total[1-j%2][j] = total[1-j%2][j-1];
    }


    int q;
    for(int i=0;i<m;++i) {
        cin >> q;

        // 青木くんが最初に取るカードのインデックス
        int nearest_i = distance(a.begin(), lower_bound(all(a), q));
        if(abs(a[nearest_i-1]-q ) <= abs(a[nearest_i]-q)) {
            --nearest_i;
        }

        // 青木くんと高橋くんの戦略が一致
        if(nearest_i >= n) {
            cout << total[n%2][n] << endl;
            continue;
        }

        // 高橋くん区間の開始インデックスを探索
        int ng = nearest_i, ok = n;
        int mid = n;
        while(ok-ng > 1) {
            mid = (ng+ok)/2;
            // 青木くんと高橋くんそれぞれから見た a[mid] の優先順位
            int aoki_rank = mid - distance(a.begin(), lower_bound(all(a), q - (a[mid]-q))) + 1;
            int takahashi_rank = n - mid + 1;
            if(aoki_rank < takahashi_rank) {
                ng = mid;
            } else {
                ok = mid;
            }
        }
        int aoki_left = n - (n-ok+1)*2 + 1;

        cout << (aoki_left?total[1-aoki_left%2][aoki_left-1]:0) + total[0][n]+total[1][n]-total[0][ok-1]-total[1][ok-1] << endl;
    }
}

所感

水曜日からずっと悩んでいた問題だが，考察でわかったことを素直に実装すれば案外素直な問題だった．

2019-03-21

yukicoder No.802 だいたい等差数列

競技プログラミング (問題解説)

問題文: No.802 だいたい等差数列 - yukicoder

Writer 解説: https://yukicoder.me/problems/no/802/editorial

問題概要

長さ$ N (\leq 3 \times 10^5)$の整数列$ A_1, A_2, \cdots, A_N$で，次の 2 つの条件の両方を満たすものの数をを$ 10^9+7 $で割ったものを求めよ．

$ 1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq M \leq 10^6$
$ 1 \leq i \leq N-1$ なるすべての i について$ D_1 \leq A_{i+1} - A_i \leq D_2 $

解法概要

しばらくサンプルで遊んでみたが行き詰まったので，テスターである heno_code さんのソースコードをチラ見．どうやら包除原理を利用するらしいというヒントを得たのでそこから考えてみた．

各隣接要素間の差 $ A_{i+1} - A_i $ について，条件を満たす / 満たさないものがいくつあるかについて包除原理を適用して計算したい．

このとき，隣接要素間の差の上限と下限の両方に条件付けがされていると扱いづらそうなので，どちらか片方だけにしたい．上限をどうにかするのは難しそうなので，いかなる入力においても隣接要素間の差の最小$ D_1 = 0$となるような問題にあらかじめ変換する．

元の問題を $ (N, M, D_1, D_2) $と表現すると，返還後の問題は $ (N, M - D_1(N-1), 0, D_2 - D_1) $ のように表現できる．これならどうにかなりそう．

あとは，「条件を満たす (または満たさない) "隣接要素間の差" が i 個あるような整数列の数」を求めることができれば，包除原理が適用できる．

これは (N-1) 個ある "隣接要素間の差" のうち i 個を $ D_2 - D_1 + 1$以上であると考えて，条件を満たさない整数列について考えるとやりやすい．

「条件を満たす (または満たさない) "隣接要素間の差" が i 個あるような整数列の数」は，

(N-1) 個の "隣接要素間の差" のうち，条件を満たさないもの i 個の選び方が $ {}_{N-1} C_{i}$ 通り
隣接要素間の差のうち i 個が条件を満たさない ($ D_2 - D_1 + 1$以上) であるような整数列は，条件を満たさないものがどれかが決まっていれば $ {}_{N+1} H_{M_{rest}} = {}_{N+M_{rest}} C_{M_{rest}} $個．ただし$ M_{rest} = M - 1 - (D_2 - D_1 + 1)*i$．あらかじめ i 個の要素に $ D_2 - D_1 + 1$ ずつ値を割り振っておいて，残りを好きに割り振ると考える．ただし，整数列の最初は最低 1 なので少なくとも 1 は1番最初の要素に割り当てられる (いちいち-1しているのはそのため)．

これで「条件を満たす (または満たさない) "隣接要素間の差" が i 個あるような整数列の数」がわかったので，あとは

(条件を満たさないものが 0 個以上の整数列の数) - (条件を満たさないものが 1 個以上の整数列の数) + (条件を満たさないものが 2 個以上の整数列の数) - (条件を満たさないものが 3 個以上の整数列の数) ...

のように包除原理を使って計算すれば良い．

ソースコード

#include <iostream>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const int FACT_MAX = 1300001;

ll fact[FACT_MAX], rfact[FACT_MAX];

ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

void init(ll n){
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

int main() {
    ll N,M,D1,D2;
    cin >> N >> M >> D1 >> D2;

    init(FACT_MAX);

    ll Mrest = M - 1 - D1*(N-1);
    ll ans = 0LL;
    for(int i=0;i<N&&Mrest>=0;++i) {
        ans += MOD + (i%2?-1:1) * (comb(N-1, i) * comb(N+Mrest, Mrest)) % MOD;
        ans %= MOD;
        Mrest -= (D2-D1+1);
    }
    cout << ans << endl;
}

所感

こんな綺麗に解けるのか〜〜．包除原理の教育的良問では．

2019-03-18

yukicoder No.801 エレベーター

競技プログラミング (問題解説)

問題文: No.801 エレベーター - yukicoder

Writer 解説: https://yukicoder.me/problems/no/801/editorial

問題概要

ある$ N (\leq 3000)$階建てビルに$ M (\leq 3000) $台のエレベーターがあり，それぞれ$ L_i $階から$ R_i $階まで各階に移動することができる．

初め 1 階にいるとして，$ K (\leq 3000) $回の移動の後に$ N $階にいるような移動の仕方の通り数を$ 10^9+7 $で割ったものを求めよ．

解法概要

dp[何回移動したか][最後に何階にいるか] の動的計画法で解くことができるが，そのまま素直に実装しようとすると (例えば，i階からj階まで移動するのに使えるエレベーターの数a[i][j]のような配列を持っていても) $ O(KN^2) $ となってしまい TLE する．

そこで，エレベーターごとに$ L_i $，$ R_i $を保持しておき，エレベーターごとに dp[現在の移動回数][$ L_i $〜$ R_i $] の和を dp[現在の移動回数+1][$ L_i $〜$ R_i $] にそれぞれ足しこむことを考える．なぜならば，現在$ L_i $〜$ R_i $階のどこかにいるなら，エレベーターiを使って$ L_i $〜$ R_i $階のどこでも好きな階に動くことができるためである．

dp[現在の移動回数+1][$ L_i $〜$ R_i $] にそれぞれ足す処理は，いもす法を用いて計算量を $ O(MN^2) $ から $ O(MN) $ へと落とすことができる．しかし，これでもまだ$ O(KMN) $で，TLEしてしまう．

そこでさらに，あらかじめdp[現在の移動回数][j]についての累積和を取っておくことによってdp[現在の移動回数][$ L_i $〜$ R_i $] の和を計算する処理を高速化する．

累積和を取る処理が$ O(N) $で，そこから和を求める1回の処理が$ O(1) $なので，これで全体の計算量は $ O(K(M+N)) $ となり，時間内に処理を終えることができる．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

typedef long long ll;
typedef pair<int, int> Pii;

const ll MOD = 1000000007;

int main() {
    int N,M,K;
    cin >> N >> M >> K;

    vector<Pii> elevators(M);
    for(int i=0;i<M;++i) {
        cin >> elevators[i].first >> elevators[i].second;
    }

    vector< vector<ll> > dp(K+1, vector<ll>(N+2, 0LL));
    dp[0][1] = 1LL;
    for(int i=0;i<K;++i) {
        for(int j=1;j<=N+1;++j) {
            dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
    
        for(int j=0;j<M;++j) {
            if(!dp[i][elevators[j].first]) continue;
            ll total = (dp[i][elevators[j].second] - dp[i][elevators[j].first-1] + MOD) % MOD;
            dp[i+1][elevators[j].first] += total;
            dp[i+1][elevators[j].first] %= MOD;
            dp[i+1][elevators[j].second+1] += MOD - total;
            dp[i+1][elevators[j].second+1] %= MOD;
        }

        for(int j=1;j<=N+1;++j) {
            dp[i+1][j] += dp[i+1][j-1];
            dp[i+1][j] %= MOD;
        }
    }

    cout << dp[K][N] << endl;
}

所感

これ面白い．シンプルな問題ながら累積和と imos 法で計算量がゴリゴリ落ちるのが爽快．

コンテスト中は行列累乗だと思っていて，必死に$ O(N^3 \log K) $解を書いてしまっていた．

ところで，ブログに yukicoder の問題の解説を書くのは初めてです．

NoiminのNoise

エイシングプログラミングコンテスト 2019 D - Nearest Card Game

問題概要

解法概要

ソースコード

所感

yukicoder No.802 だいたい等差数列

問題概要

解法概要

ソースコード

所感

yukicoder No.801 エレベーター

問題概要

解法概要

ソースコード

所感