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; } }