yukicoder : No.610 区間賞(Section Award)

アドベントカレンダーコンお疲れ様でした。
https://yukicoder.me/problems/no/610

問題

Nチームが駅伝で争っている。
区間開始時の各チームの順位と、終了時の順位が与えられる。
区間賞の可能性があるチームを列挙せよ。

解法

区間開始時に自チームより後ろにいるのに、終了時に前にいるチームがある場合、区間賞ではありえない。
よってそのようなチームの存在をチェックしよう。

終了時のチームを順に見ていき、自チームより手前にゴールしたチームのうち、区間開始時の順位の最大値を求めよう。
それが自チームより大きいなら、途中で抜かれたことになる。

int N;
int A[101010];
int B[101010];
int R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<int,int> M;
	FOR(i,N) {
		cin>>A[i];
		M[A[i]]=i;
	}
	int ma=-1;
	FOR(i,N) {
		cin>>B[i];
		if(ma<M[B[i]]) R[B[i]]=1;
		ma=max(ma,M[B[i]]);
	}
	
	FOR(i,N) if(R[i+1]) cout<<i+1<<endl;
}

まとめ

これは★2～2.5位でもよさそう。