Codeforces Round #189 Div1B　Psychos in a Line

Codeforces

問題

ｎ（≦10^5）人のサイコ野郎が一列に並んでいます。彼らにはそれぞれ1, 2, ... ,nのユニークなIDが与えらてています。

10
10 9 7 8 6 5 3 4 2 1

みたいにｎと並んでるｎ人のIDが与えられます。
サイコ野郎はサイコなので、自分の右隣の人が自分より小さいIDを持っていた場合、その人を殺してしまいます。
ちなみに１ステップ内に殺してる人が同時に殺される、ということも起こります（例えば上の例では９は７を殺しながら10に殺されます）。

何ステップ経ったらSATSUGAIが起こらなくなるか求めなさい。
上の例では、列が[10 9 7 8 6 5 3 4 2 1] -> [10 8 4] -> [10]となり、２ステップで安定します。


解法
愚直に全ステップを全員舐めながらエミュレートすると、

100000
100000 1 2 3 ...

みたいなケースで10^10オーダーになってしまうのでTLEです。
しかし、最終的に殺人は高々n-1回しか起きないので、１ステップをO(殺害の数)でエミュレートできれば間に合う、という計算になります。

ところで最初に隣の人を殺さなかった場合、隣の人の数字が勝手に小さくなったりはしないので、それ以降その人が人殺しになることはありません。
同様に、殺害を続けるうちに隣の人が自分より大きい数字になった人はそれ以降殺害できなくなります。

というわけで、最初に人殺し候補を全員列挙しておき、
各ステップで「そいつらの左隣が誰か」を常に記憶しながら殺害をエミュレートしていくことで間に合う解法となります。
以下のプログラムでは左隣の覚え方が連結リスト使えよって感じな実装になっていますが、各ステップで殺人者にO(1)ランダムアクセスする必要があるのでこうなっています。


プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

li id[100001];
li L[100001];
li R[100001];
bool alive[100001];

li killer2[100001];



int main(){
	li n;
	cin>>n;
	li res=0;
	
	vector<li> killer;
	
	rep(i,n){
		cin>>id[i];
		alive[i]=true;
		L[i]=i-1;
		R[i]=i+1;
	}
	R[n-1]=-1;
	
	rep(i,n-1){
		if(id[i]>id[i+1]){
			killer.pb(i);
		}
	}
	
	
	
	li killers=sz(killer);
	
	while(killers>0){
		for(li i=killers-1; i>=0; i--){
			if(R[killer[i]]>0 && id[killer[i]]>id[R[killer[i]]]){
				alive[R[killer[i]]]=false;
				L[R[R[killer[i]]]]=killer[i];
				R[killer[i]]=R[R[killer[i]]];
			}
		}
		
		li idx=0;
		rep(i,killers){
			if(alive[killer[i]] && R[killer[i]]>0 && id[killer[i]]>id[R[killer[i]]]){
				killer2[idx]=killer[i];
				idx++;
			}
		}
		killers=idx;
		rep(i,killers){
			killer[i]=killer2[i];
		}
		res++;
	}
	
	
	cout<<res<<endl;
	
	return 0;
}


雑感
TLEケースを考えたときに「連続する増加列の長さを求めて・・・でも色々と場合分けが面倒だぞ、ぐぬぬ・・・」って感じで90分くらい悩み通して結局この解法は人のコード見るまで思いつきませんでした。
問題を見て発想する解法のバリエーションをもっと増やしていきたいです。