Codeforces #445 Div1 A. Ann and Books

問題文の読解が辛い問題だった。
http://codeforces.com/contest/889/problem/A

問題

今任意の部屋がある。
時間ごとに任意の部屋に移動できるとする。

今、時間ごとに数字をメモすることにする。
書く数字は以下の通りである。

• 過去のこの部屋に来たことがあるならその時刻
• そうでないなら任意の時刻

メモの内容がわかっているとき、滞在した部屋数の最小値を求めよ。

解法

最後に到達した可能性のある部屋の時刻の集合を管理しよう。
メモを順に見ていき、メモに書かれた数字と、その時刻に最後に到達した可能性のある部屋があるなら、その部屋に再度移動する。
そのような部屋がなければ、新規にその部屋に訪れたとする。

解法

int N;
int T[202020];
int pre[202020];
int LT[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int NR=1;
	pre[0]=1;
	FOR(i,N) {
		cin>>T[i+1];
		
		if(pre[T[i+1]]==1) {
			pre[T[i+1]]=0;
			pre[i+1]=1;
		}
		else {
			pre[i+1]=1;
		}
	}
	
	cout<<count(pre,pre+N+1,1)<<endl;
	
}

まとめ

ちょっと設定が無理やりすぎて問題文の解釈に手間取った。