名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。

Codeforces Round #541 (Div. 2)に出た(C問題まで)

3完。時間配分としてはB問題に時間をかけすぎた(条件分岐のミスがあまりに多かった。

A問題

https://codeforces.com/contest/1131/problem/A

よく考察すると横の長さは大きい方の四角形に引っ張られて、その分の横幅はどうせ消費される事がわかる。あと四隅のことを考えれば答えが出る。

上下の四角形のかぶっているところを消すという消すもあるらしい。なるほど。

int main(){
    int w1, h1, w2, h2;
    cin >> w1 >> h1 >> w2 >> h2;
    int mw = max(w1, w2);

    cout << (4 + h1 * 2 + h2 * 2 + mw * 2) << endl;

    return 0;
}

B問題

https://codeforces.com/contest/1131/problem/B

なんかすっごい区間のチェックでバグらせた。

まず悲しい計上ミスをしないために

  • 初期値は 0, 0 のPairを入れておく
  • 区間がかぶっているものはフィルタしておく

その後、点数の遷移をAチーム、Bチームでそれぞれ見て、AチームとBチームの区間が被っていなければカウントせず、かぶっていれば足し合わせる。ただし前回区間で計上した最大値が今回の最小値となっている場合は区間がかぶってバグるので(ここの排除にすごい時間がかかかった。。。)、排除する。

あと 0, 0 で試合がずっと動かないパターンは特別処理で1にする。

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

    vector<pair<int, int>> _pv(n + 1);
    _pv[0] = make_pair(0, 0);
    for(int i = 1; i < n + 1; i++) {
        int a, b;
        cin >> a >> b;
        _pv[i] = make_pair(a, b);
    }

    // 寄せとく
    int m = 0;
    vector<pair<int, int>> pv(n + 1);
    for(int i = 0; i < n; i++) {
        if(_pv[i] != _pv[i + 1]) {
            pv[m] = _pv[i];
            m++;
        }
    }
    pv[m] = _pv[n];

    ll ans = 0;
    int last_cross = -1;
    for(int i = m; i > 0; i--) {
        // int maxn = max(pv[i].first, pv[i].second);
        int minn = min(pv[i].first, pv[i].second);
        int maxm = max(pv[i - 1].first, pv[i - 1].second);
        // int minm = min(pv[i - 1].first, pv[i - 1].second);
        if(maxm > minn) {
            // no action
        } else {
            ans += minn - maxm;
            if(minn != last_cross) {
                ans++;
            }
            last_cross = maxm;
        }
    }
    if(m == 0) {
        ans = 1;
    }

    cout << ans << endl;

    return 0;
}

あんまりうまくかけなかったな。。

C問題

https://codeforces.com/contest/1131/problem/C

Bよりも圧倒的に簡単。ソートして偶数奇数ごとに積み直すだけだった。(例えば偶数のものは前から積んで、奇数のものは後ろから積む、最後は真ん中に一番大きいものを置く感じ。山みたい。)本番はなぞのキューみたいなのを作ってマージしてた。(これは書き直したもの)

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

    vector<int> v(n);
    REP(i, n) {
        cin >> v[i];
    }

    sort(v.begin(), v.end());
    vector<int> ans(n);
    for(int i = 0; i < n / 2; i++) {
        ans[n - i - 1] = v[i * 2 + 1];
        ans[i] = v[i * 2];
    }
    if(n % 2 == 1) {
        ans[n/2] = v.back();
    }

    for(int i = 0; i < n; i++) {
        cout << ans[i];
        if(i != n - 1) {
            cout << " ";
        } else {
            cout << endl;
        }
    }

    return 0;
}

D問題以降

読んでない。

まとめ

単純な問題であるのにもかからわず、B問題でバグらせて60分以上使ったのはもったいなかった。Cはサクッと解けたけど、正直Bに比べてかなり簡単だったのでコーナーケースがめっちゃ怖かった。。。

とはいえ久々に出たCodeForcesで3完できたのはまずまずの結果じゃないでしょうか(もう少し稼げたとは思うので納得はできてない)。

英文に慣れる目的でも(CodeForcesのReadForcesは辛いが)もう少しCodeForcesのとき直しもやらなきゃなーと思った。