露骨に場合分けをしなくてはいけないような問題で苦手だったので記事にして残しておきます．
問題概要
最初，ウォータークーラーには $ l $ リットルの水が入っている． $ 1 $ 日に $ x $ リットルの水が消費される．また， $ 1 $ 日の初めに $ y $ リットル補充することができる．ウォータークーラー内の水の量がどの時点でも $ [l, r] $ の範囲内に収まるように $ t $ 日間過ごすことは可能かどうか答えよ．
制約
- $ 1 \leq l \leq k \leq r \leq 10^{18} $
- $ 1 \leq t \leq 10^{18} $
- $ 1 \leq x \leq 10^{6} $
- $ 1 \leq y \leq 10^{18} $
考察
まず日ごとの操作について考えてみる．
$ 1 $ 日に $ x $ リットルは確実に消費される．一方で $ 1 $ 日の初めに $ y $ リットル供給するかどうかは任意に決めることができる．つまり， $ 1 $ 日の終わりの時点でウォータークーラーに入っている水の量は $ (-x) $ or $ (y-x) $ リットル増加すると言える．
ただし注意しなければならない点として現在の水の量を $ k' $ として $ k'+y \leq r $ を満たす場合のみ $ (y-x) $ 増加を選択することができる（ $ r $ リットルを超えてはならないため）．この条件を供給条件と呼ぶことにする．
ここで $ (-x) $ は必ず負だが $ (y-x) $ の正負は $ x $ と $ y $ の大小によるので場合分けをする．
$ y-x \leq 0 $ の場合
選択肢の両方が負であるため $ (y-x) $ 増加を選択できる日は選択する方が良いのは明らか．つまり， 供給条件を満たすようになるまで $ (-x) $ 増加を選択したあと水の量が $ L $ 未満にならないギリギリまで $ (y-x) $ を選択するのが最適だとわかる．
供給条件を満たすようになるために選択すべき $ (-x) $ の回数を $ n $ とすると次の式が成り立つ． $$ k-nx+y \leq r $$ $$ \therefore n \geq \left\lceil{\frac{k+y-r}{x}}\right\rceil $$ $ n $ を最小化したいので右辺と等しいとする．
ここで $ k-nx < l $ の場合，つまり供給条件を満たすために必要な回数の $ (-x) $ を実行すると水の量が $ L $ リットルを下回ってしまう場合， 供給条件を満たすこと不可能． $ (-x) $ を実行できる回数を $ m $ とすると $ k-mx \geq l $ より $ m \leq \left\lfloor{\frac{k-l}{x}}\right\rfloor $ となり，この場合は右辺が $ t $ 以上なら"Yes"．
それ以外の場合， $ k $ を $ nx $，$ t $ を $ n $ だけ減らし， $ (y-x) $ 増加を実行し続けることを考える． $ (y-x) = 0 $ の時は明らかに $ t $ がいくつでも"Yes"．そうでないならやはり $ (y-x) $ 増加の実行できる回数を $ m $ として $ k-m(y-x) \geq l $ より $ m \leq \left\lfloor{\frac{k-l}{y-x}}\right\rfloor $ となり，右辺が $ t $ 以上なら"Yes"．
$ y-x > 0 $ の場合
$ y $ リットル足すと水の量が $ r $ リットルを超えてしまうため $ (y-x) $ を選択できない状態をX-Critical，逆に $ x $ リットル引くと水の量が $ l $ リットルを割ってしまうため $ (-x) $ を選択できない状態をY-Criticalと呼ぶことにすると $ y+x $ の値によって以下の $ 2 $ つ図のような状況が存在することがわかる．
$ y+x \leq r-l $ の場合，X-Critical と Y-Critical の領域は重ならないということは必ずどちらかの選択肢を選ぶことができるため答えが"Yes"になることがわかる．
$ y+x > r-l $ の場合，常に X-Critical と Y-Critical のどちらかの状態であるため，進み方は一意になる．重なっている領域に入ってしまうと詰みになる．
どちらの場合も進む戦略が結果に影響を及ぼさないことがわかるので，実装は統一して行う．
何も考えない手法として， $ t $ 回 $ (y-x) $ と $ (-x) $ の選べる方を選択することを繰り返すシミュレーションが挙げられる．当然この計算量は $ O(t) $ で遅い．ここで，制約の中で $ x $ が唯一 $ 10^{6} $ 以下の制約であることに着目する．
めいっぱい $ (-x) $ を選択する → めいっぱい $ (y-x) $ を選択するを繰り返すこと考える． $ (-x) $ をめいっぱい選択するとX-Criticalになる．X-Criticalの領域幅は $ x $ であるため，ここの訪問履歴は十分小さい空間計算量で保持できる．詰むことなく X-Critical 領域内で訪問済みの水量にたどり着いたとき同じことの繰り返しになるので，シミュレーションを打ち切って"Yes"としてよい．
具体的な実装は省くが，片方の選択をめいっぱい実行するのは既に何度も記事内でやっているような立式・式整理を行えば $ O(1) $ で行うことができ，ループ回数は最大でも $ O(x) $ であるから，全体の計算量も $ O(x) $ となり十分高速である．
個人的なポイント
- 操作をグッと睨んで操作の本質が正負によって変わる場合は別々に考える
- 一次不等式から条件を満たす最大整数を得る部分問題は冷静に式整理してからコードに落とす
- 式の整理が難しい場合は条件式をそのまま書ける二分探索を使うことも辞さない
- YesNo問題は自明なYesやNoを発見することで，自明でないケースの条件を絞り込む
- 今回は $ y+x \leq r-l $ の時は自明に"Yes"だった
- 不自然に $ 1 $ つだけ小さい制約 $ (10^{6}以下) $ があったら鳩ノ巣を疑っていい
- 今回は $ x $ が不自然に小さかった
