AtCoder Beginner Contest 224 G,H問題メモ

AtCoder Beginner Contest 224

G - Roll or Increment

• $1～N$ の目が出る $N$ 面サイコロがある
• はじめ、出目は $S$ であり、出目が $T$ である状態にしたい
• 以下の2つの操作をどちらでも好きな回数行える
  • コスト $A$ で出目を1増やす（出目が $N$ 未満の場合のみ可能）
  • コスト $B$ でサイコロを振り、出目を $1～N$ のいずれかに等確率に変化させる
• かかるコストを最小化させる戦略をとったとき、期待値を求めよ
• $1 \le N \le 10^9$

遷移ループのあり得る期待値問題。

$rem[i]$ を、現在の出目が $i$ であるとき、最適戦略をとった場合の残りコスト期待値とする。

こういう問題は、何かしらの値を変数 $X$ とおいて、 変数含みで $rem[i]$ の値などを求めてやり、 その後、何らかの値を2通りの $X$ を含む式で表してやれば、$X$ を解いてめでたしめでたし、という解法がある。

$rem$ は、とりあえず $rem[T]=0$ であることはわかるが、 他は今の段階では操作 $A$ を選ぶべきか $B$ を選ぶべきかわからない。が、必ず $N,A,B,T$ によって一意に決まる値ではある。

操作 $B$ を選択した場合、$i=1～N$ について、確率 $\dfrac{1}{N}$ で遷移先が $rem[i]$ になる。

これは、遷移元の出目が何であろうと関係ない。

$rem$ の平均を $E$ とおくと、$B+E$（具体的にはまだ求まらないが、固定値）となる。

現在の出目 $i \gt T$ なら、操作 $A$ を行う意味は無い。

操作 $A$ を行った後に操作 $B$ を行うのは無駄なので、 $A$ を行った後は $T$ までひたすら $A$ を使い続けることになる。

つまり、操作 $A$ で $T$ にするのにかかるコストは $A(T-i)$ となる。

コスト最小化戦略をとるなら、各 $i \lt T$ につき $A(T-i)$ と $B+E$ の小さい方を選ぶことになる。

N=5  A=10  B=4

     S     T
  1  2  3  4  5

rem[1]  min(30, 4+E)   ┐
rem[2]  min(20, 4+E)   │
rem[3]  min(10, 4+E)   │平均E
rem[4]  0              │
rem[5]  4+E            ┘

$B+E$ の方は固定値なので、何かしらの境界 $x$ があって、 以下のような形になっているはず（各範囲は長さが0の場合もある）。

• $[1, x)$ は操作 $B$ が最適
• $[x, T)$ は操作 $A$ が最適
• $[T+1, N]$ は操作 $B$ が最適

ここで、その切り替わる境界がどこかを仮定すると $E$ は計算できる。

仮に 現在の出目が 1  の場合は操作B、
                 2,3 の場合は操作Aが最適とした場合

rem[1]  4+E  ┐
rem[2]  20   ├ 38+2E  →  (38+2E)/5 = E
rem[3]  10   │                 ↓
rem[4]  0    │              E=12.666...
rem[5]  4+E  ┘

境界を誤った値に仮定してしまうと、 $A(T-i), B+E$ の選択でコストの高い方を選んでしまうということなので、 $E$ は実際より大きくなる。

真の境界より離れれば離れるほど、高いコストの方を選ぶ数が増えるので、$E$ はますます大きくなる。

つまり、$E$ は境界 $x$ をピークとして下に凸のグラフとなっていることになる。

三分探索を使えば、$E$ の最小値、およびそれを実現できる境界 $x$ を求められる。

$x,S,T$ の大小関係によって場合分けし、$rem[S]$ が答え。

Python3

H - Security Camera 2

• 左側に $L$ 個、右側に $R$ 個の頂点を有する完全二部グラフがある。
• 二部グラフの各頂点にカメラを設置する。カメラは1頂点に複数個、設置できる
• 1個設置する毎に、頂点に応じたコストがかかる
  • $i$ 番目の左側頂点には $A_i$
  • $j$ 番目の右側頂点には $B_j$
• $i$ 番目の左側頂点と $j$ 番目の右側頂点には、合計で $C_{i,j}$ 個以上のカメラが設置されていなければならない
• 必要な最小費用を求めよ
• $1 \le L,R \le 100$
• $1 \le A_i,B_i \le 10$
• $1 \le C_{i,j} \le 100$

線形計画問題で表現し、双対を取る。

双対という概念、いろいろと説明されてはいるのだけど、いまいち、イメージ的につかみづらい。
あくまで数式上で考えると上手くいくのは理解できても、変形した後の問題に「現実的な意味付け」を見いだしにくい。

• 双対性 | PPT

とりあえず、標準的な形というのがある。

$$\begin{equation*} \begin{aligned} & \text{minimize} & \boldsymbol{c} \boldsymbol{x} \\ & \text{subject to} & A \boldsymbol{x} \ge \boldsymbol{b} \\ & & \boldsymbol{x} \ge 0 \\ & ↓↑ \\ & \text{maximize} & \boldsymbol{b} \boldsymbol{y} \\ & \text{subject to} & A^T \boldsymbol{y} \le \boldsymbol{c} \\ & & \boldsymbol{y} \ge 0 \\ \end{aligned} \end{equation*}$$

太字（というか、出てくる英小文字は全て）はベクトルを表す。
$\boldsymbol{c} \boldsymbol{x}$ は、$\displaystyle \sum_{i=1}^{n}c_ix_i$ を示していると考えればよい。

今回の問題では、このように $A,b,c,x$ を定めれば、minimize の線形計画問題に落とし込むことができる。

c = (A1, A2, ..., AL, B1, B2, ..., BR)    頂点毎のコスト    ┐掛け合わせた総和が総コスト
x = (x1, x2, ................, x[L+R])    頂点への設置個数  ┘x を上手く決めて総コストを最小化

A = [[1,  0, ...,  0,  1,  0, ...,  0],   各行、2つだけ"1"が立ってるような行列
     [1,  0, ...,  0,  0,  1, ...,  0],   (L*R 行  L+R 列)
      :
     [0,  0, ...,  1,  0,  0, ...,  1]]

b = (C11, C12, ..., CLR)                  L*R 個の設置個数の制約

これの双対を取ると、

b = (C11, C12, ..., CLR)         L*R 個の設置個数の制約              ┐掛け合わせた総和を最大化
y = (y11, y12, ..., yLR)       （なんかよくわからんけど）L*R 個の値  ┘

A^T = [[1, 1, ..., 1, 0, 0, ..., 0],      Aの転置。(L+R 列  L*R 行)
       [0, 0, ..., 0, 1, 1, ..., 0],
        :
       [0, 0, ...,             , 1]]

c =  (A1, A2, ..., AL, B1, B2, ..., BR)   頂点毎のコスト

すると、これは $L+R$ 頂点の二部グラフに、始点と終点を追加したグラフでの最小費用流として表現できる。

• $y_{i,j}$ は、最小費用流で $i→j$ に流す流量
• $C_{i,j}$ は、$i→j$ に1単位流すコスト（※最大化問題なので、正負逆転して）
  • これの内積が最小費用
• $A^T \boldsymbol{y} \le c$ は、以下の制約を表現
  • 左側頂点 $i$ から流せる量の総和は $A_i$ 以下
  • 右側頂点 $j$ に流せる量の総和は $B_i$ 以下

設置コストが流量制約になって、設置個数制約がコストになって、 おれがあいつであいつがおれで、みたいになっているが、 ともかくこれで最小費用流を解けば、答えとなる。

Python3