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)で捌ける。

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使うってのが閃かなかった。データ構造の使い方を問う良問。

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;
}