Codeforces #557 Div1 A. Hide and Seek

Cが遅かったりD落としたりダメダメだった回。
https://codeforces.com/contest/1161/problem/A

問題

N個のセルが一列に並んでいる。
このうちどこかにトークンを置く。

別の人が、どこのセルにトークンが置いてあるか当てにくる。
その際、セルの位置を指定して、そこにトークンがあるか問い合わせる、ということを行う。
問い合わせる順番と位置はあらかじめわかっている。

この過程で、どこか任意のタイミングで１回だけトークンを隣接セルに動かすことができるとする。
トークンの位置を当てられないような初期位置と最終位置の対は何通りか。

解法

トークンの位置を当てられてしまうケースを引くことを考えよう。

• セルxにあったトークンを隣接セルyに動かすのがダメなケースは、最初にxに問い合わせがあったあと、yへの問い合わせがある場合。
• セルxにあったトークンをそのままにするのがダメなケースは、xに1回以上問い合わせがある場合。

各セルの最初と最後の問い合わせ順を覚えておけば容易に判定できる。

int N,K;
int X[101010];
int F[101010];
ll ret=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N+1) F[i]=1<<20;
	FOR(i,K) {
		cin>>X[i];
		F[X[i]]=min(i,F[X[i]]);
	}
	
	set<int> did;
	ll ret=0;
	if(N==1) ret=1;
	else {
		FOR(i,N) {
			if(i==0 || i==N-1) ret+=2;
			else ret+=3;
		}
	}
	for(i=K-1;i>=0;i--) {
		did.insert(X[i]);
		if(F[X[i]]==i) {
			ret-=did.count(X[i]);
			ret-=did.count(X[i]-1);
			ret-=did.count(X[i]+1);
			
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

ここらへん問題文の解釈に戸惑った記憶が。