[AtCoder] AGC 026 B – rng_10s

2020年12月12日

問題

方針

場合分けを行います。

\( B \gt A\) のとき

このとき、最初の昼にジュースを買うことができません。

\( B \gt D \) かつ \( B \leq A\)のとき

このとき、供給量が消費量よりも小さいので、毎日補填したとしてもいずれジュースを買うことができなくなります。

\( C \geq B – 1\) かつ \( B \leq A \) かつ \( B \leq D \) のとき

このとき、在庫量は必ず \( B \) 以上になるので、ジュースを買い続けることができます。これは、在庫を補填できない最小の在庫量は \( C + 1 \) となりますが、次の昼の消費で在庫は、\( C + 1 – B \) となり、この値が \( 0 \) より大きいことを確かめます。

\begin{eqnarray}
C & \geq & B – 1\\
C + 1 – B & \geq & 0
\end{eqnarray}

となるので、その日の夜に補填されたとき、\( B \leq D \) なので、ジュースを買い続けることができます。

\( B \leq A \) かつ \( B \leq D \) かつ \( C \leq B – 2\) のとき

ジュースを買った回数を \( x \)、補填した回数を \( y \) とすると、在庫量 \( f(x, y) \) は、

\[f(x, y) = A – Bx + Dy\]

と表すことができます。\( – Bx + Dy \) で表すことができる整数は \( g = gcd(B, D) \) とすると、\( g \) の倍数であることが言えます。よって、在庫量は、

\[ f(k) = A + gk\]

と表現できます。

ここで、\( C \leq B – 2 \) より、

\[ C + 1 \leq B – 1 \]

であることに注意します。

ここで、\( C + 1 \leq f(k) \leq B – 1 \) を満たす整数 \( k \) が存在するかどうかを考えます。もし、\( k \) が存在するとき、\( f(k) – B \leq -1 \) となってしまうので、ジュースを買うことはできません。さらに不等式を計算すると、

\[ C + 1 – A \leq gk \leq B – 1 – A \]

となります。 \( B \leq A \) より、\( B – A -1 \leq -1 \) なので、\( k \) は負の値となるので、考え易いように全体に \( -1 \) を掛けると、

\[ A + 1 – B \leq -gk \leq A – C – 1 \]

となります。このような \( k \) が存在することは、区間 \([l, r] \) に \( g \) の倍数が何個存在するかを考えれば良いので、次の式が役に立ちます。\( l \leq n \leq r\) において、\( n \mod p = q \) となるものの個数は、

\[ k_q = \left \lfloor \dfrac{r – q + p}{p} \right \rfloor – \left \lfloor \dfrac{l – q  +p – 1}{p} \right \rfloor \]

と表すことができます。証明はしていませんが、正しいとして考察を続けます。

上記の式において、\( q = 0\)、\( p = g \)、\( l = A + 1 – B \)、\( r = A – C – 1 \) として、\( k_0 \) が \( 0 \) かどうかを調べれば良いです。

コード

提出したコード