Codeforces Round #645 (Div. 2) 参加記

コンテストへのリンク

ABCで冷えました。悲しい。 Cで詰まりました。。。

A

問題へのリンク

長方形の面積のだいたい半分。

void solve(){
    ll a, b;
    cin >> a >> b;
    cout << (a * b + 1) / 2 << endl;
}

B

問題へのリンク

ソートして左全部取るとしたときにその人が取れるかどうかを考える。

void solve(){
    int N;
    cin >> N;
    vec<int> a(N);
    rep(i,N)cin >> a[i];
    sort(all(a));
    int ans = 1;
    rep(i,N){
        if(a[i] <= i+1)chmax(ans, i+2);
    }
    cout << ans << endl;
}

C

問題へのリンク

「間が全部できる」系なので、右上のパスと左下のパスの差を求めればいいです。 斜めに見ると、その距離分だけ離れていることがわかります。 いろいろ考えると、斜めの差の合計は縦横それぞれ1ずつ減らした長方形の面積になるので、それ+1がパスの差です。 お絵かきするとわかります。

本番中は階差数列の和の一般項を求めて多倍長で殴りましたが、パズルでした。。。

• パズル

void solve(){
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    gx -= sx - 1;
    gy -= sy - 1;
    cout << (gx-1) * (gy-1) + 1 << endl;
}

• 多倍長

void solve() {
    string _sx, _sy, _gx, _gy;
    cin >> _sx >> _sy >> _gx >> _gy;
    __int128 sx,sy,gx,gy;
    sx = parse(_sx);
    sy = parse(_sy);
    gx = parse(_gx);
    gy = parse(_gy);
    auto ret = [&](__int128 i, __int128 j) {
        __int128 syoko = 1 + (j - 1) * j / 2;
        __int128 res = syoko * i;
        res += (j + 1) * (i - 1) * i / 2;
        __int128 tmp = (i * (i + 1) * (2 * i + 1) / 6) - 3 * i * (i + 1) / 2 + 2 * i;
        tmp /= 2;
        res += tmp;
        return res;
    };
    auto gyo = [&](__int128 i, __int128 j) {
        __int128 syoko = i * (i + 1) / 2;
        __int128 res = syoko * j;
        res += i * (j - 1) * j / 2;
        __int128 tmp = (j * (j + 1) * (2 * j + 1) / 6) - 3 * j * (j + 1) / 2 + 2 * j;
        tmp /= 2;
        res += tmp;
        return res;
    };

    __int128 l = gyo(sx, gy-1) - gyo(sx, sy - 1);//
    l += ret(gx, gy) - ret(sx - 1, gy);//
    __int128 r = gyo(gx, gy) - gyo(gx, sy - 1);
    r += ret(gx-1, sy) - ret(sx-1, sy);
    cout << r - l + 1 << endl;
}

D

問題へのリンク

問題文不謹慎すぎないか・・・。 尺取りをやろうとしたけど時間が足りませんでした。後日通します。

-> 通しました。

今回は区間の中の一番後ろ以外から始めるのは無駄です。なぜなら、区間の一番後ろから始めたときの和がのとき、一個前にずらした区間は和が大きくなることがないからです。 後ろを全探索します。配列を複数周期分突っ込んでから、reverseして尺取り法をします。尺取りのを超えない区間の長さとその間の和を管理し、に足りない部分は一個先の後ろ個分の和を足します。実装は半開区間が功を奏する感じになります。

void solve() {
    ll N, X;
    cin >> N >> X;
    vec<ll> d(N);
    rep(i, N)cin >> d[i];
    rep(i, N)d.emplace_back(d[i]);
    rep(i, N)d.emplace_back(d[i]);
    reverse(all(d));
    int r = 0;
    ll len = 0;
    ll tmp = 0;
    //1 + 2 + ... + x
    auto calc = [&](ll x) -> ll {
        return x * (x + 1) / 2;
    };
    // x + x - 1 + ... + x - k + 1
    auto calc2 = [&](ll x, ll k) -> ll {
        if (x < k)return 0LL;
        return calc(x) - calc(x - k);
    };

    ll ans = 0;
    for (int l = 0; l < 2 * N; l++) {
        while (r < 2 * N && len + d[r] <= X) {
            len += d[r];
            tmp += calc(d[r]);
            r++;
        }
        //[l, r)になっているはず
        // X - lenだけ残っている
        chmax(ans, tmp + calc2(d[r], X - len));
        if (l == r)r++;
        else {
            len -= d[l];
            tmp -= calc(d[l]);
        }
    }
    cout << ans << endl;
}