これはシンプルながら勉強になるな。
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; }
まとめ
本番だと自力ですんなりは思い浮かばなさそう。