乐胖代购免代理版

B - -- - B

解法

ある整数 $x$ を作ることが可能か判定するときには、 $x$ を最小のコストで作る操作列だけを考えれば十分です。作りたい整数を最小のコストで作る操作列が、何らかの限定的な特徴を持つことを見つけられると非常に見通しが良くなります。

その特徴を探すために、逆に無駄な部分を持つ操作列としてどのようなものがあるかを考えます。ここで言う無駄な部分とは、操作列の一部であって、そこをある規則で変形することでより小さいコストで同じ整数を作れるものを指します。

まず、「 $-1$ 倍する」という操作を連続して2回行うことは無駄で、その2回の操作を除いても同じ整数が得られます。

また、その時点での整数が $0$ であるときに「 $-1$ 倍する」という操作を行うことも無駄で、その操作を除いても同じ整数が得られます。

さらに、次の図で表される操作も無駄です。

f:id:betrue12:20210218222152p:plain

これは「 $1$ を引く」→その時点での整数が $0$ でないときに「 $-1$ 倍する」→「 $1$ を引く」という一連の操作で、2回の「 $1$ を引く」という操作を除いても同じ整数が得られます。

作りたい整数を最小のコストで作る操作列は、これらの無駄な部分を持たないものに限られます。そのような操作列は必ず次の性質を満たします。

操作列の先頭と末尾以外に「 $-1$ 倍する」という操作が存在しない。

もしこの性質を満たさない場合、先に挙げたいずれかの無駄な部分が必ず1つ以上含まれることが場合分け等で証明できるからです。

このことから操作列としては「先頭で $-1$ 倍する/しない」「末尾で $-1$ 倍する/しない」の組み合わせ4通りだけを考えれば十分だということが分かります。

それぞれの場合について作ることが可能な整数を調べると、これは区間になります。例えば先頭で $-1$ 倍を行って末尾では行わない場合を考えます。その間に「 $1$ を引く」という操作は $0$ 回から $\lfloor\frac{C-1}{2}\rfloor$ 回までの好きな回数だけ行うことができるので、作ることが可能なのは閉区間 $\lbrack -B-\lfloor\frac{C-1}{2}\rfloor, -B\rbrack$ に含まれる全ての整数です。

同様の考え方で、4通りの場合について作ることが可能な整数の区間を求めると次のようになります。

$\lbrack B-\lfloor\frac{C}{2}\rfloor, B\rbrack$
$\lbrack B, B+\lfloor\frac{C-2}{2}\rfloor\rbrack$
$\lbrack -B-\lfloor\frac{C-1}{2}\rfloor, -B\rbrack$
$\lbrack -B, -B+\lfloor\frac{C-1}{2}\rfloor\rbrack$

これらの和集合に含まれる整数の個数が答えになります。一般に複数の区間の和集合のサイズを求めるためには、順序付き集合で区間を管理するライブラリや、座標圧縮＋imos法などを用いることができます。または4つの区間を $B$ 周辺と $-B$ 周辺でそれぞれマージすると2つの区間になるので、それぞれの長さと重なりを考えることで直接計算することもできます。