New Year Contest 2015 : F - 番号札

BitDPじゃなかったか…。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_6

問題

番号札は以下のルールで塗られているとする。

• 番号1～Mは同じ色。
• 番号(M+1)～2*Mは別の同じ色。
• 番号(2*M+1)～3*Mはまた別の同じ色。
• 以下同様に、番号(k*M+1)～(k+1)*Mは同じ色で塗られており、かつ他の札でその色は用いられていない。

今手元にN個の番号札がある。
i番目の札はA[i]の数字が書いてあり、色はC[i]である。
条件を満たすMは何通りあるか答えよ。

解法

最初にA[i]全体をデクリメントしておくと良い。
そうするとA[i]/Mの値が色と考えることができる。

まずコーナーケースを除外する。
A[x]＜A[y]＜A[z]となるx,y,zに対し、A[x]==A[z]かつA[x]!=A[y]なら、条件を満たすMはない。

さて、Mを1つずつ大きくしていく場合、Mが小さいうちはA[i]/Mの値は頻繁に変わるが、Mが大きくなるとA[i]/Mは変化しなくなってくる。
よってA[i]/Mが変化するようなMだけ、条件を満たすかどうか判定すればよい。

以下のコードでは、1≦M≦10000の範囲は総当たりしている。
また、M＞10000に対しては、A[x]/i＞10000となるようなM=A[x]/iに対し条件を満たすか判定している。

const int DIV=10000;
int N,M;
pair<int,int> P[50];
pair<int,int> P2[50];

int ok(ll v) {
	int i;
	FOR(i,M-1) if(P2[i].second/v==P2[i+1].first/v) return 0;
	FOR(i,M) if(P2[i].first/v!=P2[i].second/v) return 0;
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first>>P[i].second, P[i].first--;
	
	FOR(i,N) {
		FOR(x,i) FOR(y,x) if(P[i].second==P[y].second && P[i].second!=P[x].second) return _P("0\n");
		if(i!=0 && P[i].second==P[i-1].second) P2[M-1].second=P[i].first;
		else P2[M++]=make_pair(P[i].first,P[i].first);
	}
	
	if(M==1) return _P("-1\n");
	
	ll ret=0;
	for(i=1;i<=DIV;i++) if(ok(i)) ret++;
	
	vector<int> cand;
	FOR(i,M) {
		ll a=P2[i].first,b=P2[i].second;
		for(int c=1;a/c>=DIV;c++) cand.push_back(a/c);
		for(int c=1;b/c>=DIV;c++) cand.push_back(b/c);
	}
	cand.push_back(DIV);
	sort(cand.begin(),cand.end());
	cand.erase(unique(cand.begin(),cand.end()),cand.end());
	
	FOR(i,cand.size()-1) if(ok(cand[i+1])) ret+=cand[i+1]-cand[i];
	cout<<ret<<endl;
}

まとめ

うーむ、BitDPとか包助原理だと思ったんだけどな。