TopCoder SRM 552 Div2 Hard FoxPlusMinus

自分が参加する前の問題を、時間をさかのぼる方向でチャレンジしてみた。
http://community.topcoder.com/stat?c=problem_statement&pm=12147

問題

要素数Kの初期数列Fが与えられたとき、そこから無限数列Aを以下のルールで生成する。

• i
• i>=KならA[i]=A[i-K] - A[i-K+1] + ... + (-1)^(K-1) * A[i-1]

数Nが与えられたとき、A[N]が最大となるようFを並べ替えよ。
題意を満たすFが複数あるなら、そのうち辞書順最小なものを返せ。

解法

N=Kの場合を考えていく。

A[i]の計算式を見ると、Kが偶数か奇数かで挙動が変わることが推測できる。
試しに、Fを1要素だけ1、残りを0としてみた場合、Aがどうなるかを列挙してみる。

Kが奇数の場合

たとえばK=7の時、1要素だけ1にしたFから以下のようにAが生成できる。

F[0]=1 :  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1
F[1]=1 :  0  1  0  0  0  0  0 -1  0  1  0  0  0  0  0 -1  0  1  0  0  0  0  0 -1  0
F[2]=1 :  0  0  1  0  0  0  0  1  0  0  1  0  0  0  0  1  0  0  1  0  0  0  0  1  0
F[3]=1 :  0  0  0  1  0  0  0 -1  0  0  0  1  0  0  0 -1  0  0  0  1  0  0  0 -1  0
F[4]=1 :  0  0  0  0  1  0  0  1  0  0  0  0  1  0  0  1  0  0  0  0  1  0  0  1  0
F[5]=1 :  0  0  0  0  0  1  0 -1  0  0  0  0  0  1  0 -1  0  0  0  0  0  1  0 -1  0
F[6]=1 :  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1  0  0  0  0  0  0  1  1  0

明らかに法則性が見える。よって、解は以下の通り。

• (N+1)%(K+1)==0の時、A[N]はFの偶数indexの総和から奇数indexの総和を引いたものになるため、Fを昇順ソートして下位半分を奇数indexに、上位半分を偶数indexに配置すればよい。
• (N+1)%(K+1)!=0の時、A[N]=F[N%(K+1)]なので、N

Kが偶数の場合

同様にK=6の時のAの遷移を列挙してみる。

F[0]=1 : 1 0 0 0 0 0  1 -1  2 -4   8 -16  32  -63  125 -248  492  -976
F[1]=1 : 0 1 0 0 0 0 -1  2 -3  6 -12  24 -48   95 -188  373 -740  1468
F[2]=1 : 0 0 1 0 0 0  1 -2  4 -7  14 -28  56 -111  220 -436  865 -1716
F[3]=1 : 0 0 0 1 0 0 -1  2 -4  8 -15  30 -60  119 -236  468 -928  1841
F[4]=1 : 0 0 0 0 1 0  1 -2  4 -8  16 -31  62 -123  244 -484  960 -1904
F[5]=1 : 0 0 0 0 0 1 -1  2 -4  8 -16  32 -63  125 -248  492 -976  1936

それぞれのA[N]の値は、F[i]が寄与する重みと見ることができる。
A[K]～A[2K-1]までは同じ要素が見られるが、A[2K]以降は数値がばらつき、法則性も見られる。

• N>=2KかつNが偶数なら、Fを昇順ソートした上位半分を偶数indexに配置し、下位半分を奇数indexに逆順で配置すればよい。
• N>=2KかつNが奇数なら、Fを昇順ソートした上位半分を奇数indexに配置し、下位半分を偶数indexに配置すればよい。
• K<=N<2Kの場合、A[N]への寄与が同程度となるF[i]が複数ある。法則性はあるのだが偶奇も合わせた記述が面倒だったで、上記表をN<2Kの範囲で生成し、重みが大きい順にFの大きい要素を格納した。

class FoxPlusMinus {
	public:
	vector <int> maximize(vector <int> first, int N) {
		int K=first.size();
		int i,j,k,x;
		
		sort(first.begin(),first.end());
		if(N<K) {
			rotate(first.begin()+N,first.begin()+(K-1),first.end());
		}
		else if(K%2==0) {
			vector<int> V;
			V.resize(K);
			
			if(N>=K*2) {
				
				FOR(i,K/2) V[i*2] = first[K/2+i];
				FOR(i,K/2) V[i*2+1] = first[K/2-1-i];
				if(N%2) FOR(i,K/2) swap(V[i*2],V[i*2+1]);
			}
			else {
				vector<pair<int,int> > PP;
				FOR(i,K) {
					vector<int> T;
					FOR(j,K) T.push_back(j==i);
					FOR(j,K+5) {
						x=0;
						FOR(k,K) x += T[T.size()-(1+k)]*((k%2)?1:-1);
						T.push_back(x);
					}
					PP.push_back(make_pair(T[N],i));
				}
				sort(PP.begin(),PP.end());
				FOR(i,K) V[PP[i].second] = first[i];
			}
			return V;
		}
		else {
			N%=K+1;
			if(N==K) {
				vector<int> V;
				V.resize(K);
				FOR(i,K/2+1) V[i*2] = first[K/2+i];
				FOR(i,K/2) V[i*2+1] = first[i];
				return V;
			}
			else {
				rotate(first.begin()+N+1,first.end(),first.begin()+(K-1));
			}
		}
		return first;
	}

};

まとめ

シンプルな問題設定ながら、意外と考えることが多くて面白い問題。