九州大学プログラミングコンテスト2018 : H - ukuku

これはシンプルながら勉強になるな。
https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_h

問題

N要素の数列Aが与えられる。
アルファベット小文字で構築されたN文字の文字列Sのうち、S[i]を中心とする回文の長さの最大値がA[i]であるようなものを構築せよ。

解法

まず、各A[i]からわかることは、(i+(A[i]-1)/2+1)文字目と(i-(A[i]-1)/2-1)文字目は異なっていなければならないということである。
この情報を元に、Sの先頭から順に決めていこう。
i文字目まで決まれば、(i+(A[i]-1)/2)文字目まで確定できる。

A[i]を見るときS[i]が確定していなかったら、上記異なっていなければならない条件より、問題ない文字を貪欲に割り当てて行けばよい。

int N;
int A[202020];
vector<int> NG[202020];
char S[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int R=0;
	FOR(i,N) {
		cin>>A[i];
		if(S[i]==0) {
			set<char> T;
			FOR(j,26) T.insert('a'+j);
			FORR(n,NG[i]) T.erase(S[n]);
			S[i]=*T.begin();
		}
		l=(A[i]-1)/2;
		if(i-(l+1)>=0) NG[i+(l+1)].push_back(i-(l+1));
		while(R<=i+l) {
			S[R]=S[2*i-R];
			R++;
		}
	}
	cout<<S<<endl;
}

まとめ

本番だと自力ですんなりは思い浮かばなさそう。