kmjp's blog

競技プログラミング参加記です

Looksery Cup 2015 : G. Happy Line

わかってしまえばあっさり。
http://codeforces.com/contest/549/problem/G

問題

N人の人が並んでおり、列の後ろからi番の人はお金をA[i]持つ。
A[i]>A[i+1]の場合、後ろからi番の人は(i+1)番の人にお金を1払って位置を交換できる。
A[i]が昇順になった場合、列は安定する(すなわちそれ以上位置の交換が発生しない)。

初期状態のA[i]が与えられたとき、この列は安定するか。
安定するなら、各位置の人はどれだけのお金を持つか答えよ。

解法

本番はSegTreeを使ってガリガリやったが、その後Hackの過程でもっと簡単な方法があることがわかったのでそちらを紹介。

列の前にいる人は、後ろにいる人と位置を交換してお金を1得られるので、実質位置1あたりお金1の価値があると考えられる。
そこでA[i]+=iで位置の分の価値を加算しよう。

その後、AをソートしてA[i]-=iで価値の加算分を引く。
この時Aが昇順ならそれが解。
A[i]=A[i+1]-1となるケースがあるが、この場合i番と(i+1)番は永遠に位置の交代を繰り返し安定しない。

int N,A[202000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], A[i]+=i;
	sort(A,A+N);
	FOR(i,N) A[i]-=i;
	FOR(i,N-1) if(A[i]>A[i+1]) return _P(":(\n");
	
	FOR(i,N) _P("%d ",A[i]);
	_P("\n");
}

まとめ

本番かなりSegTree頑張ったんだけどな。
まぁ正解したからいいけど…。