B - ディスコ社内ツアー

[Q] https://atcoder.jp/contests/discovery2016-qual/tasks/discovery_2016_qual_b

スマートな解放や実装がありそうだけど思いつかず。
素直に問題文通り処理をする。次見る部屋を1つずつ探索すると、
5, 4, 3, 2, 1
が来た時に、4周して5要素を見るから4*5回見て、O(N*N)処理してしまう。

次行く部屋をupper_boundで探索すればO(NlogN)。111ms。
早いと12msとかすごい。

1. 座標圧縮して、
2. 圧縮値ごとに、その部屋の位置リストを作っておく。
3. 次に行く部屋の位置を、upper_boundで探索。

Q. どう実装？
A.

入力例
5
4 4 2 8 6

1. 座標圧縮する。
A[] = {4, 4, 2, 8, 6}
    =>{1, 1, 0, 3, 2}

2. 場所リストを作る。
G[0] = {2}      // G[A] = { 部屋id }
G[1] = {0, 1}
G[2] = {4}
G[3] = {3}

3. 問題文通りに処理していく。
Aをsortした順番に訪れる。
A_[] = {0, 1, 1, 2, 3}

スタート地点idは
now = -1で用意。

・0の部屋を探す
auto it = upper_bound(A.begin(), A.end(), now)
*it = 2が取れるので、
now = 2に移動する。

・1の部屋
auto it = upper_bound(A.begin(), A.end(), now)
G[1] = {0, 1}なので、
it = G[1].end() にいたってしまう。
1周する必要があるので、先頭に戻り、2週目に入る。
now = -1

再び探索を行って
auto it = upper_bound(A.begin(), A.end(), now)
*it = 0
now = 0に移動する。

・1の部屋
auto it = upper_bound(A.begin(), A.end(), now)
*it = 1
now = 1に移動する。

・2の部屋
*it = 4
now = 4に移動する。

・3の部屋
it = G[3].end()なので3周目に入る。
now = -1にセットして、
*it = 3
now = 3に移動する。

解答は3周目。

実装

vector<ll> G[100010]; // G[a]={id}
int main(){
 cincout();
 
 ll N;
 cin >> N;
 vector<ll> A(N);
 vector<ll> A_(N); // sort用
 set<ll> S; // 座標圧縮用

 rep(i, N){
   ll a;
   cin >> a;
   A[i] = a;
   A_[i] = a;
   S.insert(a);
 }
 sort(all(A_));
 map<ll, ll> conv; // 座標圧縮のマッピング
 ll cnt = 0;
 for(auto it = S.begin(); it != S.end(); ++it){
   conv[*it] = cnt;
   ++cnt;
 }

 rep(i, N){ // Aを座標圧縮の値におきかえちゃう
   A[i] = conv[A[i]];
   A_[i] = conv[A_[i]];
   
   G[A[i]].push_back(i); // 値の位置をメモ
 }
 ll ans = 1;
 ll now = -1; // 現在いるid
 rep(i, N){
   ll t = A_[i];
   auto it = upper_bound(all(G[t]), now);
   if (it == G[t].end()){ // もう後続にない場合1周して先頭に戻る
     ++ans, now = -1;
     it = upper_bound(all(G[t]), now);
   }
   now = *it;
 }
 if (now == 0) --ans; // ゴール地点が先頭なら1周引く
 cout << ans << endl;
}

https://atcoder.jp/contests/discovery2016-qual/submissions/26083946