Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-06-22

[][] Codeforces Beta Round #75 Div. 2 D. Queue 09:32 はてなブックマーク -  Codeforces Beta Round #75 Div. 2 D. Queue - 練習帳

問題文:http://codeforces.ru/problemset/problem/92/D

要約

 n人の人が縦一列に並んでいる.i番目の人はa[i]歳で,自分のよりも真に若い人が前(この場合は番号が大きい方が前)に並んでいると不満を言う.その不満の大きさは数値化すると,「自分より前にいる中で最も若い人」と「自分」の間にいる人の数に等しい.ただし,自分より前の人がすべて自分と同年齢or年上の時は不満の大きさは-1とする.それぞれの人の不満の大きさを答えよ.nは2以上10**5以下.それぞれの人の年齢a[i]は1歳以上10**9歳(!)以下.

方針

 ナイーブに全探索を行ったらもちろんO(n**2)で計算量的に間に合わない.そこで,過去に使った情報を再利用できないかを考える,今回で言えば i < j < kについて,j番目の人とk番目の人の大小関係はj番目の人より前での最小年齢の計算だけでなくi番目より前での計算にも使える.ここでは,それを[i, n]の最小値を求める事で利用している(完全にeditorial読んだのでこんな天下り的な事を言っています).

 mns[i]を[i, n]での最小値とすれば,mns[i]はiについて単調増加なので,2分探索でa[i]の入る位置を求められる.その入る位置とiとの距離-2(i番目の人と最小年齢の人を除いている)が求める答え.

分析

 前にこれに似た問題(特定の区間の最小値を求める)にstd::setを使った記憶があって,これもそうに違いないと思い込んでいたのが失敗でした.editorialにある,[i, n]の最小値はiについて単調減少に気づければ,二分探索でプラスマイナス1の差に悶絶しながらも解けはしたような気がします.

コード例
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <climits>

using namespace std;

typedef long long ll;

int inf = INT_MAX;

int main(){
  int n;
  while(cin >> n){
    vector<int> a(n);
    for(int i = 0;i < n;i++){
      cin >> a[i];
    }
    vector<int> ans(n);
    vector<int> mns(n);
    vector<int> pos(n);
    int mn = inf;
    for(int i = n-1;i >= 0;i--){
      if(mn > a[i]){
	pos[i] = i;
	mn = a[i];
      }else{
	pos[i] = pos[i+1];
      }
      mns[i] = mn;
      if(i == n-1){
	ans[i] = -1;
      }else{
	int p = lower_bound(mns.begin() + i, mns.end(), a[i]) - mns.begin();
	int dist = p - i - 2; 
	ans[i] = dist >= 0 ? dist : -1; 
      }
    }
    for(int i = 0;i < n;i++){
      cout << ans[i] << " " ;
    }
    cout << endl;

  }
}