kmjp's blog

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

Codeforces #376 Div2 D. 80-th Level Archeology

これ本番出てたら落としてたかも。
http://codeforces.com/contest/731/problem/D

問題

N個の文字列S[i]が与えられる。
各文字列中の文字は1~Cのいずれかである。

全文字列の文字を1つrotateする(C未満の文字は1増加させ、Cは1にする)ことができるとする。
入力された文字列が全て昇順になるためには、最小何回rotateすればよいか。

解法

隣接する文字列S[i]とS[i+1]を比較する。
先頭からj文字目で初めて文字の不一致が生じたとする。(S[i][j]!=S[i][j+1])

すると、このS[i][j]とS[i][j+1]の間でr文字rotateさせたとき、S[i][j]>S[i][j+1]となってしまうrの範囲が1つまたは2つ求まる。
これらは答えとして採用できないrotate回数を意味する。
各iに対してそのようなrを求め、採用可能な最小値を求めよう。

範囲を重ね合わせるのは、imos法の要領で行えばO(N+C)で可能。

int N,C;
vector<int> K[505050];
int NG[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,N) {
		cin>>x;
		K[i].resize(x);
		FOR(j,x) cin>>K[i][j], K[i][j]--;
	}
	
	int L=0,R=C-1;
	FOR(i,N-1) {
		FOR(j,K[i].size()) {
			if(K[i+1].size()==j) return _P("-1\n");
			if(K[i][j]==K[i+1][j]) continue;
			
			if(K[i][j]>K[i+1][j]) {
				NG[0]++;
				NG[C-K[i][j]]--;
				NG[C-K[i+1][j]]++;
			}
			else {
				NG[C-K[i+1][j]]++;
				NG[C-K[i][j]]--;
			}
			
			break;
		}
	}
	FOR(i,C) {
		if(i) NG[i]+=NG[i-1];
		if(NG[i]==0) return _P("%d\n",i);
	}
	_P("-1\n");
	
}

まとめ

最初採用不可なrの範囲が1つと勘違いしてた。