Distributed Code Jam 2016 Round 2 : C. lisp_plus_plus

まぁここらへんまではね。
https://code.google.com/codejam/contest/7244486/dashboard#s=p2

問題

N文字の括弧からなる文字列が与えられる。
文字列のprefixのうち、後ろに何文字か付け加えて整合性の取れる括弧列になるようにしたい。
条件を満たすprefixは最長何文字か。

解法

括弧列の定番テクとして、開き括弧を+1、閉じ括弧を-1として先頭から開き括弧が余分にある数をカウントするものがある。
後ろに文字を追加できても前に追加できないことを考えると、初めて上記カウントが負になる場合、その手前が条件を満たす最大のprefixとなる。

そこで、文字列をノード数で分割し、各ノードにおけるカウントの増減数の合計及び途中経過の最小値を求めよう。
その結果を先頭ノードに集めると、これらの情報からどのノードの担当区間でカウントが負になりうるかを求めることができる。
あとはその区間で再度カウントを計算し、具体的に負になる場所を求めるとよい。

以下のコードは再度のカウントは元の担当ノードで行ってるけど、０番のノードで行えば良かったね。

int TN,MY;
ll N;
int id[1010];

void solve(){
	int i,j,k,l,r,x,y; string s;
	N=GetLength();
	
	if(N<=1010) {
		if(MY!=0) return;
		x=0;
		FOR(i,N) {
			y = GetCharacter(i);
			if(y=='(') x++;
			if(y==')') x--;
			if(x<0) return _P("%d\n",i);
		}
		if(x==0) return _P("-1\n");
		return _P("%d\n",N);
	}
	else {
		TN--;
		FOR(i,TN+1) id[i]=1LL*i*N/TN;
		
		if(MY!=TN) {
			int mi=0;
			x=0;
			for(i=id[MY];i<id[MY+1];i++) {
				y = GetCharacter(i);
				if(y=='(') x++;
				if(y==')') x--;
				mi=min(mi,x);
			}
			
			PutLL(TN, x);
			PutLL(TN, mi);
			Send(TN);
		}
		
		if(MY==TN) {
			int cur=0;
			int mimi=0;
			FOR(i,TN) {
				Receive(i);
				x = GetLL(i);
				y = GetLL(i);
				mimi=min(mimi,cur+y);
				if(mimi<0) {
					FOR(j,TN) {
						if(j==i) PutLL(j,cur);
						else PutLL(j,-1);
						Send(j);
					}
					return;
				}
				cur += x;
			}
			
			FOR(j,TN) PutLL(j,-1), Send(j);
			if(cur==0) _P("-1\n");
			else _P("%d\n",N);
		}
		
		if(MY!=TN) {
			Receive(TN);
			x = GetLL(TN);
			if(x==-1) return;
			for(i=id[MY];i<id[MY+1];i++) {
				y = GetCharacter(i);
				if(y=='(') x++;
				if(y==')') x--;
				if(x<0) return _P("%d\n",i);
			}
			
		}
		
	}
	
}


int main(int argc,char** argv){
	
	TN=NumberOfNodes();
	MY=MyNodeId();
	solve();
	return 0;
	
}

まとめ

ローカル環境作ろうかなぁ…。