Codeforces #631 Div1 A. Dreamoon Likes Coloring

ほぼレート増減なしだった回。
http://codeforces.com/contest/1329/problem/A

問題

M個のスタンプがあり、i番目の長さはL[i]である。
今N個のマスがあり、各スタンプを順に使いi番目のスタンプで任意の連続するL[i]マスをi色目で上書きするとする。
最終的に各色のマスが1つ以上現れるようにする塗り方を答えよ。

解法

sum(L)がN未満の場合は解なし。
それ以外の場合、後ろから順に各色右に詰めて塗ることを考える。
M色目はNマス目から左側、(M-1)色目は(N-1)マス目から左側…と塗っていく。

最終的にL[1]+(M-1)＞Nだとこのような塗り方ができないので解なし。
逆にL[1]+(M-1)＜Nだと塗り切れないところがあるので、その場合2色目以降を2マス以上残るように場所をずらしていくとよい。

int N,M;
int L[101010];
int pos[101010];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll S=0;
	cin>>N>>M;
	int ma=0;
	int ON=N;
	pos[M]=N+10;
	FOR(i,M) {
		cin>>L[i];
		S+=L[i];
	}
	if(S<N) return _P("-1\n");
	
	for(i=M-1;i>=0;i--) {
		pos[i]=min(pos[i+1]-1,N+1-L[i]);
	}
	if(pos[0]<1) return _P("-1\n");
	int dif=pos[0]-1;
	int mov=0;
	
	for(i=M-2;i>=0;i--) {
		int ma=min(dif,pos[i]-(pos[i+1]-L[i]));
		mov+=ma;
		dif-=ma;
		pos[i]-=mov;
	}
	FOR(i,M) cout<<pos[i]<<" ";
	cout<<endl;
	
}

まとめ

変なコーナーケースがありそうで怖い問題。