Codeforces Round #136 (Div. 2)

結果

ひさびさにプロコンに参加した。最近は(Java, Eclipse)ばっかりだったので、(C++, Emacs)でうまく書けるか不安だったが思ったより鬼は黒くなかった。 3/5AC、160位/1925人だった。（配列の最大要素数をミスってて問題DはRuntime Errorで死んでいた。それがなかったら20位くらいだった。もったいない。）

　問題D、Eがおもしろかった。解答は以下のとおり。

D. Little Elephant and Array

[l, r]区間に現れる回数がちょうどxとなるような正の整数xの個数を求める問題(1 <= l <= r <= n)。xの候補となるような正の整数はたかだか√n個程度になることに気付くかどうかがポイント。[1, y]区間にそれぞれのxが何回現れるかをメモリ上に保持すると(1 <= y <= n)、1クエリーがO(√n)で捌ける。

view plainprint?

1. using namespace std;  
2.   
3. const int MAX_LEN = (int)1e5;  
4.   
5. int xs[MAX_LEN];  
6. int nums[500][MAX_LEN+1];  
7.   
8. int main() {  
9.     int n, m;  
10.     cin >> n >> m;  
11.       
12.     map<int, int> cnt;  
13.     for (int i = 0; i < n; i++) {  
14.         cin >> xs[i];  
15.         cnt[xs[i]]++;  
16.     }  
17.       
18.     vector<int> vs;  
19.     for (map<int, int>::iterator itr = cnt.begin(); itr != cnt.end(); itr++) {  
20.         if (itr->second >= itr->first)  
21.             vs.push_back(itr->first);  
22.     }  
23.       
24.     int l = vs.size();  
25.     memset(nums, 0, sizeof(nums));  
26.     for (int i = 0; i < l; i++) {  
27.         for (int j = 0; j < n; j++) {  
28.             nums[i][j+1] = nums[i][j];  
29.             if (vs[i] == xs[j])  
30.                 nums[i][j+1]++;  
31.         }  
32.     }  
33.       
34.     for (int i = 0; i < m; i++) {  
35.         int a, b;  
36.         cin >> a >> b;  
37.           
38.         int ret = 0;  
39.         for (int j = 0; j < l; j++) {  
40.             if (nums[j][b] - nums[j][a-1] == vs[j])  
41.                 ++ret;  
42.         }  
43.         cout << ret << endl;  
44.     }  
45.       
46.     return 0;  
47. }  

using namespace std;

const int MAX_LEN = (int)1e5;

int xs[MAX_LEN];
int nums[500][MAX_LEN+1];

int main() {
    int n, m;
    cin >> n >> m;
    
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        cin >> xs[i];
        cnt[xs[i]]++;
    }
    
    vector<int> vs;
    for (map<int, int>::iterator itr = cnt.begin(); itr != cnt.end(); itr++) {
        if (itr->second >= itr->first)
            vs.push_back(itr->first);
    }
    
    int l = vs.size();
    memset(nums, 0, sizeof(nums));
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < n; j++) {
            nums[i][j+1] = nums[i][j];
            if (vs[i] == xs[j])
                nums[i][j+1]++;
        }
    }
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        int ret = 0;
        for (int j = 0; j < l; j++) {
            if (nums[j][b] - nums[j][a-1] == vs[j])
                ++ret;
        }
        cout << ret << endl;
    }
    
    return 0;
}

E. Little Elephant and Shifts

長さnの順列a, bが与えられる。bのn個の巡回シフト集合に対して、それとaの距離を求める。2つの順列の距離は、 minimum |i - j|, that ai = bjと定義される。multisetをうまく使うと解ける。multisetまでは分かったんだけど、lower_bound使うってのが閃かなかった。データ構造の使い方を問う良問。

view plainprint?

1. using namespace std;  
2.   
3. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
4. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
5.   
6. int main() {  
7.     int N;  
8.     cin >> N;  
9.   
10.     vector<int> a(N);  
11.     vector<int> b(N);  
12.   
13.     REP(i, N) cin >> a[i];  
14.     REP(i, N) cin >> b[i];  
15.   
16.     vector<int> x(N);  
17.     vector<int> y(N);  
18.   
19.     // set postions of a[i] and b[i]  
20.     REP(i, N) x[--a[i]] = i;  
21.     REP(i, N) y[--b[i]] = i;  
22.       
23.     multiset<int> dis;  
24.     REP(i, N) dis.insert(y[i]-x[i]);  
25.       
26.     REP(k, N) {  
27.         int ret = 0x7fffffff;  
28.         __typeof(dis.begin()) itr = dis.lower_bound(k);  
29.         ret = min(ret, *itr-k);  
30.         if (itr != dis.begin())  
31.             ret = min(ret, abs((*--itr)-k));  
32.         cout << ret << endl;  
33.         int head = b[k];  
34.         dis.erase(dis.find(y[head]-x[head]));  
35.         dis.insert(N-1-x[head]+k+1);  
36.     }  
37.   
38.     return 0;  
39. }  

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)

int main() {
    int N;
    cin >> N;

    vector<int> a(N);
    vector<int> b(N);

    REP(i, N) cin >> a[i];
    REP(i, N) cin >> b[i];

    vector<int> x(N);
    vector<int> y(N);

    // set postions of a[i] and b[i]
    REP(i, N) x[--a[i]] = i;
    REP(i, N) y[--b[i]] = i;
    
    multiset<int> dis;
    REP(i, N) dis.insert(y[i]-x[i]);
    
    REP(k, N) {
        int ret = 0x7fffffff;
        __typeof(dis.begin()) itr = dis.lower_bound(k);
        ret = min(ret, *itr-k);
        if (itr != dis.begin())
            ret = min(ret, abs((*--itr)-k));
        cout << ret << endl;
        int head = b[k];
        dis.erase(dis.find(y[head]-x[head]));
        dis.insert(N-1-x[head]+k+1);
    }

    return 0;
}