yukicoder : No.1834 1D Gravity

最初の考察から難しめ？
https://yukicoder.me/problems/no/1834

問題

1次元の座標上、1～Nの各座標に、異なる質量の星がある。
この星は、以下のように動く。

• 整数の時刻tの時点で、各星は自身の位置xに対し(x-1)または(x+1)のいずれかのうち、より大きな質量のある星の位置に移動する。この移動は全星同時に発生する。

最終的に、各星は2つのx座標を交互に移動するようになる。その際

• 最終状態に至る最短時刻を答えよ
• 同じ2点を往復する星を同一グループとみなしたとき、グループ数はいくつか。

解法

N≦2の時は自明なので、N≧3のケースを考える。
この場合、t=0で最終状態にはなりえない。

まず前提として、t≧1以降においては、隣接位置にある星同士が2以上離れることはない。逆に、グループの間には、星のないx座標が必ず存在する。
よって、グループ数はt=0における移動をシミュレートするだけで確定できる。

あとは最終状態になる最短時刻だが、グループ毎にその時間を求めよう。
t=1において、(最終的に同じグループになる)各座標の星の重さからなる数列を考える。
奇数番目の要素と偶数番目の要素だけを抜き出した部分列を考えると、いずれも途中まで単調増加で、その後単調減少するとする。

この数列を○○○○○X△△△△△△Y□□□□□□□と表現したとする。
XとYは、奇数番目の要素と偶数番目の要素いずれかの最大値とする。
この場合、時刻1枚に、XとYの間の△が2個ずつ減る。△が消滅後は、○と□が1個ずつ減る。
よって最終状態に至る時間は(△の数/2)+max(○の数,□の数)となる。

int N;
int P[202020];
int Q[202020];

int hoge(vector<int> V) {
	int C[2]={0,1};
	int i;
	int N=V.size();
	FOR(i,N) {
		if(V[i]>V[C[i%2]]) C[i%2]=i;
	}
	
	if(C[0]<C[1]) {
		return (C[1]-C[0])/2+max(C[0],(N-1-C[1]));
	}
	else {
		return (C[0]-C[1])/2+max(C[1],(N-1-C[0]));
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i+1];
	if(N==2) {
		cout<<0<<" "<<1<<endl;
		return;
	}
	for(i=1;i<=N;i++) {
		if(P[i-1]<P[i+1]) Q[i+1]=max(Q[i+1],P[i]);
		else Q[i-1]=max(Q[i-1],P[i]);
	}
	int g=0;
	int ma=1;
	vector<int> V;
	FOR(i,N+3) {
		if(Q[i]==0) {
			if(V.size()) {
				g++;
				ma=max(ma,hoge(V)+1);
				V.clear();
			}
		}
		else {
			V.push_back(Q[i]);
		}
	}
	
	cout<<ma<<" "<<g<<endl;
	
}

まとめ

考察がいろいろと賢いな。