WARush

SRMの結果とか、解けた問題のコードを書いていきます

AtCoder Regular Contest #014 D "grepマスター"

考えた事

なんかRMQ(だっけ?)とかそーゆーのデータ構造を使うんだろうなーという考えから抜け出せなくてOUT。考えが固くなる・視野が狭くなると駄目!ってtyokudaiさんが言っていたが、まさにそれ。



ACしてるソースコードをカンニング

optionBをB,optionAをA,見つけた場所をN個でgrepをオラー!ってやると、基本的には(B + A + 1) * N行出力される。


見つけた行をL[ i ] ( 0 <= i < N )として、L[i+1] - L[i]がB + Aより少ないと、その部分はマージされる。

例えば、L[m]とL[m+1]の区間でマージが起こると(B + A + 1) * (N - 1) + L[m+1] - L[m]となる。さらに加えてL[n]とL[n+1]の区間でマージが起こると(B + A + 1) * (N - 2) + L[m+1] - L[m] + L[n+1] - L[n]となる。さらに加えてL[o]とL[o+1]の区間でマージが起こると(B + A + 1) * (N - 3) + L[m+1] - L[m] + L[n+1] - L[n] + L[o+1] - L[o]となる。

という訳で、何個マージされるかと、その時の区間の距離の総和を高速に数えられるとよいので、区間の距離をソートするのと、そのi番目までの総和を出しておく。何個マージされるかはlower_boundを使えば高速で簡単。総和は一発で出る。



ソースコード

vector<int> f;
vector<int> d;
int s[100050];

int main() {
    // 入力
    int L, F, Q;
    cin >> L >> F >> Q;
    for( int i = 0; i < F; i++ ){
        int t;
        cin >> t;
        f.push_back( t );
    }
    int min_f = f[0];
    int max_f = f[F-1];

    // d初期化(区間の距離をソートする)
    for( int i = 0; i < F - 1; i++ ){
        d.push_back( f[i+1] - f[i] );
    }
    sort( d.begin(), d.end() );

    // s初期化(区間の距離の総和を出しておく)
    s[0] = 0;
    for( int i = 0; i < F - 1; i++ ){
        s[i+1] = s[i] + d[i];
    }

    // クエリ
    for( int i = 0; i < Q; i++ ){
        int B, A;
        cin >> B >> A;
        int w = B + A + 1;
        int k = lower_bound( d.begin(), d.end(), w ) - d.begin();
        int r = s[k] + w * ( F - k );
        r -= max( B - min_f + 1, 0 );
        r -= max( A - L + max_f, 0 );
        cout << r << endl;
    }
}