AtCoder ARC112 B - -- - B 解

##問題概要
整数Bと正整数Cが与えられる。以下の操作を総コストがCを上回らない範囲で任意回数行うとき、作ることができる整数は合計でいくつあるか。

1. Bに-1をかける。コストを1だけ支払う。
2. Bから1を引く。コストを2だけ支払う。

• 制約
  • $-10^{18} \le B \le 10^{18}$
  • $1 \le C \le 10^{18}$

##考察
整数を作る過程は以下4種類に分類できる
(a) $|B|$から操作2で原点まで下る
(b) (a)の途中または終わりに操作1によって負領域に折り返す
(c) $-|B|$から操作2によって-∞方向に下る
(d) (c)の途中または終わりに操作1によって正領域に折り返す

(a)(b) では絶対値が $|B|$ 以下の整数の部分集合を作ることができ、(c)(d) は絶対値が $|B|$ より大きい整数の部分集合を作ることができる。

(c)(d)ケース

(c)にコストを全振りして$-|B|-N$まで負数を作ったとする。$-|B|-1,...-|B|-N$を正領域に折り返す際、払えるコストが1余っていれば、これら$N$個の負数を全て正領域に折り返すことができる。余っていなければ折り返せるのは$-|B|-1,...-|B|-(N-1)$だけになる（$-|B|-N$を作るコストを$-|B|-(N-1)$の折り返しに当てる）。つまり、予算が奇数あれば作った負数を全て折り返せるが、偶数だと奇数ケースより1減る。

(a)(b)ケース

ほぼ同様の議論ができる。(a)によって0に到達し得るか否かで場合分けが発生することに注意。到達し得るなら作れる数は$|B|+1$個。$+1$は0の分。到達し得ないなら(c)(d)のように予算の奇偶で生成個数が分かれる。

##実装
絶対値が $|B|$ 以下の整数の数を数える関数count_inと、絶対値が $|B|$ より大きい整数の数を数える関数count_outを作ればよい。

以下の実装では、Bの正負によって各count関数の数え始めの位置をどこにセットするかが変わるため引数が多少動いている。

たとえば、count_inはB>0に対して定義したが、count_outは B<0 に対して定義したため、B>0 ケースではBの値を負数側に折り返した後の予算c-1をcount_outに渡している。

int main() {
    // read input
    auto b = in<ll>();
    auto c = in<ull>();
    // assume b > 0. count intergers |x| <= |b|
    auto count_in = [](const ull &b, const ull &c) -> ull {
        if (b > c / 2) { // touch 0 ? -> NO
            // #{x: 0 <= x <= b}
            ull pos = c / 2 + 1;
            return (c % 2 != 0) ? 2 * pos : 2 * pos - 1;
        } else {
            // b,-b,(b-1),-(b-1),..., 1,-1,0
            return b * 2 + 1;
        }
    };

    // assume b < 0. count intergers |x| > |b|
    auto count_out = [](const ull &c) -> ull {
        if (c <= 1) return 0;
        // #{x: x < b}
        ull neg = c / 2;
        return (c % 2 != 0) ? neg * 2 : neg * 2 - 1;
    };

    // show
    if (b > 0) {
        print(count_in(b, c) + count_out(c - 1));
    } else if (b < 0) {
        print(count_in(-b, c - 1) + count_out(c));
    } else {
        print(1 + count_out(c));
    }
}