Codeforces Round #317 [AimFund Thanks-Round] (Div. 1) A. Lengthening Sticks

B より正解者が少ないという。

問題

codeforces.com

解法

0 <= n <= l を満たす各 n について, 「3 辺に足す長さの合計が n であるような長さの割り振り方」が何通りあるのかの和が答えです。ということで, 3 辺に足す長さの合計が n であるような長さの割り振り方 が O(1) で求めてみます。

条件を満たすかを考えずに長さを割り振ると, その割り振り方は 通りあります。ここから条件を満たさないような場合の数を引いていきます。

例えば, a, b, c の 3 辺の中で, a が最長になるような場合を考えると, 条件を満たさないためには, a > b+c が成り立っていればよいですが, これはつまり b+c が a+b+c の半分にも満たない, ということです。要するに b+c に値を加えた結果が (a+b+c+n)/2 に満たない限りは b+c にどれだけ値を足しても良いということです。言い換えると, (a+b+c+n)/2 - (b+c) の値は 3 辺に好きなように割り振って構わないということなので, この値を x とすると, 割り振り方は 通りになります。

これを a が最長, b が最長, c が最長の場合について引いていけば OK です。

ll calc(int a, int b, int c, int n) {
    ll maxi = (a+b+c+n)/2;
    ll rest = maxi-b-c;
    if (rest < 0) return 0;
    if (rest > n) rest = n;
    return (rest+2)*(rest+1)/2;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c, l;
    cin >> a >> b >> c >> l;
    ll ans = 0;
    for (int n = 0; n <= l; n++) {
        ans += (ll)(n+2)*(n+1)/2;
        ans -= calc(a, b, c, n);
        ans -= calc(b, c, a, n);
        ans -= calc(c, b, a, n);
    }
    cout << ans << endl;
    return 0;
}