AtCoder ARC #128 (大和証券プログラミングコンテスト2021) : E - K Different Values

うーん、こういうの苦手。
https://atcoder.jp/contests/arc128/tasks/arc128_e

問題

整数列Aと整数Kが与えられる。
以下を満たす数列Xが存在するなら、辞書順最小のものを求めよ。

• iはX中でA[i]個登場する
• Xから連続するK要素を抜き出すと、同じ値は2回以上登場しない。

解法

先頭からどん欲に埋めて行く。
今X[i]を決めようとするとき、残る空き領域の数を(N-i)=pK+qと表す。

• 残るA[j]＞pとなるjが存在するなら、解なし。
• A[j]=pとなるjがq個より多く存在するなら、解なし。
• A[j]=pとなるjがq個存在するなら、そのうちいずれかをX[i]に入れないと、後でそれらをXに入れられなくなってしまう。なので、A[j]=pであるjのうち直前の登場位置よりK個以上経過しているjのうち辞書順最小のものを入れる。
• A[j]=pとなるjがq個未満なら、何を入れておいてもあとで残りをXに押し込めることができるので、A[j]が正であるjのうち直前の登場位置よりK個以上経過しているjのうち辞書順最小のものを入れる。

int N,K;
int A[505];
int pre[505];

int ret[252525];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	int S=0;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
		pre[i]=-1<<20;
	}
	
	FOR(i,S) {
		int P=(S-i+(K-1))/K;
		int Q=(S-i-1)%K+1;
		int num=0;
		int mi=1<<20;
		int mia=1<<20;
		FOR(j,N) {
			if(A[j]>P) {
				cout<<-1<<endl;
				exit(0);
			}
			if(A[j]==P) {
				num++;
				if(i-pre[j]>=K) mi=min(mi,j);
			}
			if(A[j]>0) {
				if(i-pre[j]>=K) mia=min(mia,j);
			}
		}
		if(num>Q) {
			cout<<-1<<endl;
			exit(0);
		}
		else if(num==Q) {
			ret[i]=mi;
			pre[mi]=i;
			A[mi]--;
		}
		else {
			ret[i]=mia;
			pre[mia]=i;
			A[mia]--;
		}
		
	}
	
	FOR(i,S) cout<<ret[i]+1<<" ";
	cout<<endl;
	
}

まとめ

シンプルな設定だけに解き方がわからないと工夫のしようがなくてしんどい。