これ本番出てたら落としてたかも。
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つと勘違いしてた。