TopCoder SRM 777 : Div1 Easy PreviousOccurrence

久々に0完やらかしてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=15923&rd=17802

問題

定数Dに対し、以下の数列を考える。

• A[0]=0
• A[k+1] := A[k]以前にA[k]と同じ値が登場してなければD。登場していれば直前の登場をA[m]として(m-k)

整数Qに対し、A[i]=Qとなる最初のiを求めよ。

解法

D=1の場合、A={0,1,1,1,...}となるので、2以降になることはない。
それ以外の場合、少なくとも問題の入力の範囲では添え字が1500000以前以内に登場するようなので、愚直にシミュレートすればよい。

int P[3000001][2];

class PreviousOccurrence {
	public:
	int findValue(int defaultValue, int query) {
		MINUS(P);
		int i;
		P[0][0]=0;
		int pre=0;
		if(query==0) return 0;
		for(i=1;i<3000000;i++) {
			int cur;
			if(P[pre][1]==-1) {
				cur=defaultValue;
			}
			else {
				cur=P[pre][0]-P[pre][1];
			}
			if(cur==query) return i;
			P[cur][1]=P[cur][0];
			P[cur][0]=i;
			pre=cur;
		}
		return -1;
	}
	
}

まとめ

本番は1000000回だけシミュレートしてたので落ちちゃった…。