競プロがんばりたい

BootCamp Brown(つづき)

前回やったバチャ，BootCamp Brownで残した問題があったのでやりました．

chankilu23.hatenadiary.com

3 - Ice Tea Store

必要な金額を最小化したいので， $x$ リットルを買う最適な方法を探します．( $x=0.5, 1, 2$ )

$x$ リットルサイズの値段 $C_1$ と， $\dfrac{x}{2}$ リットルサイズ $2$ つ分の値段 $C_2$ を比べます．

もし， $C_2$ が $C_1$ より小さいなら， $C_1$ を $C_2$ で置き換えても差し支えありません．

なぜならこれは同じ $x$ リットルという量をより安く買うことを意味し，また在庫は無限にあるからです．

また，購入するボトルの個数を聞かれてるわけではないので， $C_1$ を $C_2$ で置き換えたことで購入したボトルが $2$ つ分増える，とかは考えなくてOKです．

$x=0.5, 1, 2$ の順で置き換えていかなければいけないことに注意します．

具体的に1つやってみると，

もし $2 \times Q \lt H$ ならば， $H = 2 \times Q$ とします．

$(H, S), (S, D)$ でも同様の操作をします．

購入する金額は最適化できたので，あとは実際にボトルの容量が大きい物から買えるだけ買っていきます．(省略)

5 - Modulo Summation

これは気づけばとても簡単な問題です．(気づかんけど)

結論から言うと，各 $i=1, 2, \cdots, n$ について， $a_i -1$ を全て足したものが答えです．

上手く $m$ を選んだとき， $m$ mod $a_i$ が最大になるのは， $m=a_i -1$ のときです．

言い換えると， $a_i$ と互いに素である $a_i$ 以下の整数のうち最大のものです．

これを任意の $i$ で考えると $m$ は， $a_1, a_2, \cdots, a_n$ の全てと互いに素であり， $a_1, a_2, \cdots, a_n$ を超えない整数のうち最大のものを考えればよいです．

つまり， $m=$ lcm $(a_1, a_2, \cdots, a_n) -1$ です．(lcmは最小公倍数)

この $m$ に対して $f(m)$ を計算すると， $\displaystyle \sum_{i=1}^n (a_i-1)$ です．

ちなみに， $m$ は求めなくてもいいです．(というかデカすぎてオーバーフロウするかも？)