Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 224 G 問題 Roll or Increment

AtCoder ABC ABC224 G問題 600 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

変数 V があり, 最初, V=S と設定されている. 以下の2つの操作を好きな回数できる.

  • V \neq N のとき, A 円払って V \gets V+1 とする.
  • B 円払って, V \gets \operatorname{rand}(1,N) とする. ただし, \operatorname{rand}(1,N) は 1,2, \dots, N の中から当確率でランダムに選ぶ関数.

V=T にするための費用の期待値を最小になるように行動した際のその期待値の最小値を求めよ.

制約

  • 1 \leq N \leq 10^9
  • 1 \leq S,T \leq N
  • 1 \leq A,B \leq 10^9

解法

戦略の決定

i=1,2, \dots, N+1 に対して, E_i で V=i の状況から始めたときの V=T にするための費用の期待値の最小値とする. このとき,

E_i=\begin{cases} 0 & (i=T) \\ \displaystyle \min \left(E_{i+1}+A, \frac{1}{N} \sum_{j=1}^N E_j+B \right) & (i \leq N, i \neq T) \\ \infty & (i=N+1) \end{cases}

である.

ここで, i \gt T ならば, \displaystyle E_i=\frac{1}{N} \sum_{j=1}^N E_j+B であることがわかる.

さて, この方程式によって, (E_1,E_2,\dots,E_{N+1})=(F_1,F_2,\dots, F_{N+1}) と求まったとする. このとき, 当然

\displaystyle F_i=\begin{cases} 0 & (i=T) \\ \displaystyle \min \left(F_{i+1}+A, \frac{1}{N} \sum_{j=1}^N F_j+B \right) & (i \leq N, i \neq T) \\ \infty & (i=N+1) \end{cases}

である. H=\sum_{j=1}^N F_j と置き, i \leq T, i \gt T の場合をそれぞれ考慮すると,

\begin{align} F_i&=\begin{cases} 0 & (i=T) \\ \min (F_{i+1}+A, H+B) & (i \lt T) \\ H+B & (i \gt T) \\ \infty & (i=N+1) \end{cases} \\ &=\begin{cases} 0 & (i=T) \\ \min (A \times (T-i), H+B) & (i \lt T) \\ H+B & (i \gt T) \\ \infty & (i=N+1) \end{cases} \end{align}

になる.

i \lt T のときの \min (A \times (T-i), H+B) に着目する. このとき, A \times (T-i) は単調減少で, H+B は定数なので, ある整数 L で, 以下を満たすものが存在する.

  • \forall i \in \{1,2,\dots,T\}; [i \geq L \iff A \times (T-i) \leq H+B]

以上のことから, 期待値を最小にとるときの戦略は, ある 1 以上 T 以下の整数 L を用いて,

  • L \leq V \leq T のときは V=T になるまで足し続ける.
  • それ以外のときは L \leq V \leq T になるまで \operatorname{rand}(1,N) を選択する.

となることがわかる.

期待値の導出

期待値を求める.

  • L \leq S \leq T のとき, この場合は (T-S) 回の加算が最適になる. これは確定で (T-S)A 円の費用である.
  • それ以外のとき
    • L \leq V \leq T になるまで \operatorname{rand}(1,N) を選択する. 1回の選択で, L \leq V \leq T となる確率 p は, p=\frac{T-L+1}{N} である. 確率 p で成功する試行を成功するまで行う回数は幾何分布に従う. 確率 p の幾何分布に従う確率変数の期待値は, \frac{1}{p} である.
    • その後, (T-V) 回加算する. このフェーズ開始前に V は \{L,L+1,\dots,T\} を台集合とする一様分布に従う. よって, 加算する回数の期待値は, \frac{1}{2}(T-L) である.
    • 以上から, この場合の期待値は \frac{1}{p}B+\frac{1}{2}(T-L)A=\frac{1}{2}(T-L)A+\frac{N}{T-L+1}B である.

このことから, 求めるべき値は,

  • S \leq T のとき \displaystyle \min \left((T-S)A, \min_{S \leq L \leq T} \left(\frac{1}{2}(T-L)A+\frac{N}{T-L+1}B \right) \right)
  • S \gt T のとき \displaystyle \min_{1 \leq L \leq T} \left(\frac{1}{2}(T-L)A+\frac{N}{T-L+1}B \right)

ここで, \displaystyle \min_{1 \leq L \leq T} \left(\frac{1}{2}(T-L)A+\frac{N}{T-L+1}B \right) において, 変数変換をすることにより,

\displaystyle \begin{align} \min_{1 \leq L \leq T} \left(\frac{1}{2}(T-L)A+\frac{N}{T-L+1}B \right) &=\min_{0 \leq X \leq T-1} \left(\frac{A}{2}X+\frac{BN}{X+1} \right) \\\\ &=\min_{1 \leq X' \leq T} \left(\frac{A}{2}X'+\frac{BN}{X'} \right)-\frac{A}{2} \end{align}

a,b \gt 0 とする. 正の実数上で定義される関数 g(x):=ax+\frac{b}{x} について, 以下のような重大な性質がある.

関数 g は下に凸な関数であり, x=\sqrt{ab} で最小値 2 \sqrt{ab} を取る.

証明は相加相乗平均の関係と微分である.

このことから, \sqrt{\frac{2BN}{A}} と 1,T の大小関係によって場合分けをすることによって, 求めることができる. \displaystyle \min_{S \leq L \leq T} \left(\frac{1}{2}(T-L)A+\frac{N}{T-L+1}B \right) の場合も同様である.