DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 B問題 ディスコ社内ツアー

コンテスト中に解法を思いつけなかったので、AtCoderの解説とTwitteを参考に解きました。

問題

B: ディスコ社内ツアー - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder
面白さがそれぞれA_iの部屋が環状にならんでいて、面白さが広義単調増加となるように部屋を回る。
1番目の部屋を出発点としたとき何周する必要があるかをもとめる。
みたいな問題

解法

実際にぐるぐるまわる単純なシュミレーションを書くとO(N^2)になり部分点の20点が得られます。



満点解法もぐるぐるまわるシュミレーションなのですが、面白さが等しい部屋をまとめて管理することで高速化でき、O(N)で解くことができます。


まわる部屋はかならず広義単調増加になっているため、面白さが等しい部屋は必ず続けて通ることになります(例 : 2 1 3 2 2 2 -> 1 2 2 2 2 3 )
これに注目し、キーを「面白さ」、値を「"その面白さである部屋のindex"をもつvector」のmapを使用して、面白さが等しい部屋をまとめて管理します。
このmapを利用してシュミレーションを行います。


基本的にはmapのキーが小さい順に舐めていくだけなのですが、今いる部屋の更新の際に工夫が必要になります。
説明を簡単にするため、「map[i]」と書いたときのiを、mapのキーの中でi番目に小さいものとします。
また、map[i]の値(vector)は昇順にソートされており、大きい値が格納されている方を右と呼ぶことにします。


現在いる部屋のindexをnowとし、はじめは-1に初期化しておきます。
すると次に向かう部屋は「map[0]の値(vector)のうち、nowのindexから右にたどっていき、はじめに見つかったもの(右端にくると左端にローテーションする)」となります。
その後、向かった部屋と同じ面白さの部屋を全てまわることになります。
つまり今いる部屋のindexをnowとすると、以下のようにnowの値を更新していくことができます。

next = upper_bound( map[i].begin(),map[i].end() , now ) - map[i].begin();
now = map[i][  (next - 1 + map[i].size()) % map[i].size()  ]

now==1の時の更新を図にするとこんな感じで、この例ではnowの値は1から0に更新されます。



よく読むとわかるのですが、「(next - 1 + map[i].size()) % map[i].size()」は基本的にはnext-1の結果と一致し、next==0のときにのみ「map[i].size()-1」となります。

面白さが等しい部屋の左端と右端だけを持つと今いる部屋の更新がうまく行かず、例えば「2 1 3 2 2 2」というケースに対して3と出力してしまう(正解は2)ので注意が必要です。

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back

int main(){
    int n;
    cin>>n;
    vector<int> vec(n);
    map<int,vector<int>> mp;
    rep(i,n){
        cin>>vec[i];
        mp[vec[i]].pb(i);
    }
    
    int count=1,now=-1;
    for(auto itr = mp.begin();itr!=mp.end();itr++){
        vector<int> sec = itr->second;
        sort(all(sec));
        
        int p = lower_bound(all(sec),now)-sec.begin();
        if(  now>sec[  (p+sec.size()-1)%sec.size()  ]  )count++;
        now = sec[  (p+sec.size()-1)%sec.size()  ];
        
    }
    if(now == 0)count--;
    cout<<count<<endl;
}