AtCoder ARC #120 : D - Bracket Score 2

これはすんなりだった。
https://atcoder.jp/contests/arc120/tasks/arc120_d

問題

2N要素の整数列Aが与えられる。
今ここで、2N文字の整合性のとれた括弧列を任意に作るとする。
もしi文字目とj文字目が対応する開き括弧・閉じ括弧の関係にあるとき、スコアに|A[i]-A[j]|だけ増加するとする。
総スコアを最大化する文字列を答えよ。

解法

Aのうち上位N要素と下位N要素が互いに開き括弧・閉じ括弧を成すようにすれば、明らかにスコアは最大である。
この対応付けはスタックを使えばO(N)で行える。
ただ、上位/下位N要素を決めるのにO(NlogN)かかるので、全体ではO(NlogN)

int N;
int A[404040];
pair<int,int> P[404040];
int T[404040];

string R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>A[i];
		P[i]={A[i],i};
	}
	sort(P,P+2*N);
	FOR(i,N) T[P[i].second]=1;
	
	vector<int> stack;
	FOR(i,2*N) {
		if(stack.empty()||T[stack.back()]==T[i]) {
			R+="(";
			stack.push_back(i);
		}
		else {
			R+=")";
			stack.pop_back();
		}
		
	}
	cout<<R<<endl;
}

まとめ

さっと解けてよかった。