TopCoder SRM 721 Div1 Easy (Div2 Med): RememberWords

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

$d_{1}, d_{2}, w_{1}, w_{2}$ が与えられるので、以下の条件を満たす数列が構成できるか判定せよ。

数列の長さが $d_{1} + d_{2}$ であり、各項は非負整数で、隣り合う項との差の絶対値は $0$ または $1$
第 $1$ 項から第 $d_1$ 項までの和は $w_1$
第 $d_1+1$ 項から第 $d_1 + d_2$ 項までの和は $w_2$

解説

前半の数列を $s_1$ 、後半の数列を $s_2$ とします。

それぞれの数列について、端に来れる値の範囲を考えます。これは公差 $1$ の等差数列を考えればよく、例えば項数が $5$ で和が $15$ の場合、 1 2 3 4 5 のように、端に来れる値の最小値が $1$ 、最大値が $5$ であることが分かります。

この最小と最大を得るには、二分探索をすればよいです。

最小を得るには、初項が $x$ であって公差 $1$ の等差数列を作り、その和が目的の値を 下回らなければ 良いです。同じかそれより大きい場合はどこかを適当に削って対応できますが、どの要素も隣接要素との差がすでに $1$ であり、かつ最小値を変更することができないことから、増やすことができないからです。

最大を得るには、初項が $x$ であって公差 $-1$ の等差数列を作り、その和が目的の値を 上回らなければ 良いです。同じかそれ未満の場合はどこかを適当に増やして対応できますが、どの要素も隣接要素との差がすでに $-1$ であり、かつ最大値を変更することができないことから、減らすことができないからです。

最大を得るには公差が負の等差数列を扱いますが、項は非負なので注意しましょう。

こうして $s_{1}, s_{2}$ それぞれに対して求められた最小・最大からなる区間の関係を見たとき、区間が被るか端と端の間の距離が $1$ であれば、数列が構成できます。

ソースコード

pair<ll, ll> solve(ll d, ll w) {
    ll mi, ma;
    // 最小値
    ll ub = INF, lb = -1;
    while(ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        ll sum = mid * d + d * (d - 1) / 2;
        if(sum >= w) ub = mid;
        else lb = mid;
    }
    mi = ub;

    // 最大値
    ub = INF, lb = 0;
    while(ub - lb > 1) {
        ll mid = (ub + lb) / 2, val = min((ll)d, mid);
        ll sum = max(mid - d, 0LL) * d + val * (val + 1) / 2;
        if(sum > w) ub = mid;
        else lb = mid;
    }
    ma = lb;
    return make_pair(mi, ma);
}

string check(pair<ll, ll> a, pair<ll, ll> b) {
    if(a.second < b.first - 1 || b.second < a.first - 1) return "Impossible";
    else return "Possible";
}

class RememberWords {
    public:
    string isPossible(int d1, int d2, int w1, int w2) {
        pair<ll, ll> seg1 = solve(d1, w1);
        pair<ll, ll> seg2 = solve(d2, w2);
        return check(seg1, seg2);
    }
};