読者です 読者をやめる 読者になる 読者になる

Codeforces Round#350 Div2

http://codeforces.com/contest/670
 1200番くらいかな?今回もB問題に一時間かけたりしてグダグダでした。Codeforcesは相性が悪いんだよなあ(他のコンテストが得意なわけではない)。
 本当はSRMにもっとたくさん出たいんですが予定が合わなかったりレジり忘れたりTCOに登録したなかったりでなかなか出られません。ARCもなかなか予定が合わなくていまだに7級です。Codeforcesは睡眠削ればまあOKみたいな日時にやってるので4回くらい出てますが、実装力が低くサッパリです。以下復習。
 A問題:Holidays
4分で解けたのでまあOKという感じ。
 B問題 : Game of Robots
掛け算の途中で発生するオーバーフローに気づかず死亡。一時間かかりました……。
僕は二分探索で解いたのですがこれ愚直解も余裕で通りますね……。

int d[100001];
int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    rep(i, n) cin >> d[i];
    int lb = 0, ub = n + 1;
    while(ub - lb > 1){
        ll mid = ((ll)ub + (ll)lb) / 2;
        ll m = mid * (mid + 1) / 2;
        if((ll)k <= m) ub = mid;
        else lb = mid;
    }
    ll hiku = lb * (lb + 1) / 2;
    int at = k - hiku - 1;
    cout << d[at] << endl;
    return 0;
}


C問題 : Cinema
バケツソート風の解法というかバケツを使うやつ。入力の順序を間違えていて死亡。

map<int, int> table;
typedef pair<int, int> pint;
int mov1[200000], mov2[200000];
int main(){
    int n; scanf("%d", &n);
    rep(i, n){
        int a;
        scanf("%d", &a);
        table[a]++;
    }
    int m; scanf("%d", &m);
    pint res(0, 0);
    int ans = 1;
    rep(i, m) scanf("%d", mov1 + i);
    rep(i, m) scanf("%d", mov2 + i);
    rep(i, m){
        int a = mov1[i], b = mov2[i];
        int tmp1 = 0, tmp2 = 0;
        if(table.count(a)) tmp1 += table[a];
        if(table.count(b)) tmp2 += table[b];
        if(res < pint(tmp1, tmp2)){
            res = pint(tmp1, tmp2);
            ans = i + 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

D問題 : Magic Powder
 問題文読解後即binary searchしたくなるもの。
 B問題の反省を活かしたlong long int多用でなんとかまともな速度でAC。

ll a[100001], b[100001];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k; cin >> n >> k;
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    ll lb = 0, ub = INF;
    while(ub - lb > 1){
        ll mid = (ub + lb) / 2;
        ll kk = k;
        rep(i, n){
            if(a[i] * mid > b[i])
              kk -= (a[i] * mid) - b[i];
            if(kk < 0) break;
        }
        if(kk < 0) ub = mid;
        else lb = mid;
    }
    cout << lb << endl;
}

E問題 : Correct Bracket Sequence Editor
 みんなだいすき正しい括弧列(http://mio-hirona.hatenablog.com/entry/2016/04/19/013335)。
 こんなんどうやっても解けるだろ~とか思っていたらpretestで落ちて死。
 以下pretest落ちしたコードです。

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m, p; cin >> n >> m >> p;
    string par, com; cin >> par >> com;
    int it = p - 1;
    for(char a : com){
        if(a == 'R'){
            it++;
        }else if(a == 'L'){
            it--;
        }else{
            if(par[it] == '('){
                int height = 0, sum = 0, at = 0;
                REP(i, it, par.size()){
                    height += (par[i] == '(') ? 1 : -1;
                    sum++;
                    if(height == 0){
                        at = i;
                        break;
                    }
                }
                if(at == par.size() - 1) it--;
                par.erase(it, sum);
            }else{
                int height = 0, sum = 0, at = 0;
                for(int i = it; i >= 0 ; --i){
                    height += (par[i] == '(') ? 1 : -1;
                    sum++;
                    if(height == 0){
                        at = i;
                        break;
                    }
                }
                par.erase(at, sum);
                it = at;
            }
        }
    }
    cout << par << endl;
    return 0;
}

 簡単な問題で時間を使いすぎるのはどうにかしたいですね。
 掛け算の途中でオーバーフローするなんて知らないし掛け算用のメモリはすべて64ビットにしてほしいです(わがまま)。
 問題自体は前回よりかは良かったです。前回は英語が意味不明すぎました。