DDPC2016 予選 : B - ディスコ社内ツアー

ドワコン→s8pc→DDPCと全部同じ順位。
http://discovery2016-qual.contest.atcoder.jp/tasks/discovery_2016_qual_b

問題

1～N番の部屋が円周上に並んでおり、それぞれ番号が増える方向に一方通行で移動可能である。(N番から1番には当然移動可能)
部屋を経由する際、部屋を見学することができる。(せずに通り過ぎても良い)
i番の部屋を見学する面白さはA[i]である。

1番の部屋から初めて、部屋間を移動しながら見学を行う。
見学した部屋の面白さが単調増加になるように見学順を定め、最終的に1番の部屋に戻りたい場合、最低何周する必要があるか。

解法

まず面白さ毎に部屋番号をビンソートしよう。
ある面白さの部屋を全部訪れたら、次の面白さの最寄の番号に訪れる、という手順を繰り返せばよい。
1番の部屋を最後に訪れても周回数は増えない点に注意。

int N;
vector<int> A[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x, A[x].push_back(i);
	
	int ret=0;
	int cur=101010;
	
	FOR(i,101000) if(A[i].size()) {
		FOR(j,A[i].size()) if(A[i][j]>cur) break;
		if(j==0) cur=A[i].back();
		else ret++, cur=A[i][j-1];
	}
	
	if(cur==0) ret--;
	cout<<ret<<endl;
	
}

まとめ

17年卒が80人通るというから、ABCやCodeFestival予選級の問題を予想していたら、完全にARCレベルの問題が出てきた。