Google Code Jam 2018 Round1B : B. Mysterious Road Signs

これ本番出てたら解けたんかな…。
https://codejam.withgoogle.com/2018/challenges/0000000000007764/dashboard/000000000003675b

問題

東西方向の道路にいくつかの標識がある。
各標識iは位置順に並んでいて、位置D[i]にあり、西向きの面にA[i]、東向きの面にB[i]の数値が書かれている。

標識の連続した部分列について、以下を満たすものがあるか。
あるなら最長の要素数と、その組み合わせ数を求めよ。

• 部分列全体である整数M,Nを共有しており、各標識はM=D[i]+A[i]、N=D[i]-B[i]の少なくとも片方を満たしている。

解法

まず最初に

• P[i] = D[i]+A[i]
• Q[i] = D[i]-B[i]

で変数を変換しておく。あとはP[i]=MまたはQ[i]=Nの少なくとも片方を満たす最長の列を求める問題となる。

後は分割統治法で解く。
区間[l,r]に置いて考えるとき、中央のm番目を含むような部分列を考える。
この時P[m]=MかQ[m]=Nの少なくとも片方は満たすので、もう片方を任意に取れる場合、部分列を左右方向どこまで伸ばせるかを考えればよい。

それが終わったら、mを含まない[l,(m-1)]、[(m+1),r]の区間を再帰的にチェックする。

int N;
int A[101010][2];

map<int,int> MM;

void dfs(int L,int R) {
	if(R-L<=2) {
		MM[R-L]++;
		return;
	}
	int M=(L+R)/2;
	dfs(L,M);
	dfs(M+1,R);
	
	set<pair<int,int>> B;
	for(int t=0;t<2;t++) {
		vector<int> LL,RR;
		int patL=-1<<30,patR=-1<<30;
		for(int i=M-1;i>=L;i--) {
			if(A[i][t]==A[M][t]) LL.push_back(-1<<30);
			else {
				if(patL==-1<<30) patL=A[i][t^1];
				if(patL!=A[i][t^1]) break;
				LL.push_back(A[i][t^1]);
			}
		}
		for(int i=M+1;i<R;i++) {
			if(A[i][t]==A[M][t]) RR.push_back(-1<<30);
			else {
				if(patR==-1<<30) patR=A[i][t^1];
				if(patR!=A[i][t^1]) break;
				RR.push_back(A[i][t^1]);
			}
		}
		
		if(patL==-1<<30 || patR==-1<<30 || patL==patR) {
			B.insert({M-LL.size(),M+1+RR.size()});
			continue;
		}
		
		int x;
		FOR(x,RR.size()) if(RR[x]!=-1<<30 && RR[x]!=patL) break;
		B.insert({M-(int)LL.size(),M+1+x});
		FOR(x,LL.size()) if(LL[x]!=-1<<30 && LL[x]!=patR) break;
		B.insert({M-x,M+1+(int)RR.size()});
	}
	
	FORR(r,B) MM[r.second-r.first]++;
	
}

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>r>>x>>y;
		A[i][0]=r+x;
		A[i][1]=r-y;
	}
	
	MM.clear();
	dfs(0,N);
	
	
	_P("Case #%d: %d %d\n",TC,MM.rbegin()->first,MM.rbegin()->second);
	
}

まとめ

分割統治に気付けばあっさりだけど、気づかないとつらい。