geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ARC128 参加記録

ARC 株の売買問題

コンテスト中AC:A,B

A - Gold and Silver

$A$ を折線グラフで考えたとき、下に凸な頂点で金に交換、上に凸な頂点で銀に交換し、それ以外では何もしないのが最適です。

始点と終点は例外なので、 $1 \leq i \leq N-1$ のとき、以下のようにします。

1.金を持っているとき

$A_i \lt A_{i+1}$ なら、まだ上がりつづける可能性があるのでなにもしません。

そうでない時、銀と交換して翌日以降の下がったときに金に交換した方が今より金の枚数を多くできるので、銀に交換します。

2.銀を持っているとき

金の時と逆パターンです。

$A_i \gt A_{i+1}$ なら、まだ下がりつづける可能性があるのでなにもしません。

そうでない時、翌日以降に金と交換するより金の枚数を多くできるので、金に交換します。

最後に、 $i=N$ の時点で銀を持っているなら金に交換します。

これに基づいて操作列を求めることができます。

提出コード：

https://atcoder.jp/contests/arc128/submissions/26587504

B - Balls of Three Colors

3色の内、2色を同数とする必要があります。

$R,G,B$ を $a,b,c$ に割り当て、 $b$ を $a$ と同数にすることにします。

そのような割り当て方法は6通りなので全探索できます。

$d=a-b$ とします。

$d \lt 0$ なら、同数にすることは不可能です。

3回までの操作で達成できる増加減の列を書き出してみます。((0, 0, 0)を除く)

・1回

(+2, -1, -1)

・2回

(+4, -2 -2), (+1, +1, -2)

・3回

(+6, -3, -3), (+3, 0, -3)

まずわかることは、1回の操作で $a$ と $b$ の差は3ずつ縮まるということです。

よって、 $d$ が3の倍数でない時、同数とすることは不可能です。

3の倍数である場合、必要な操作回数は、 $k=\frac{d}{3}$ 回です。

操作が何回できるかは、 $c$ に依存します。

よって、 $c \geq k$ なら同数にすることができ、その操作回数は、同数にするための $k$ 回と、0にするのに $b+2k$ 回が必要になり、操作回数の合計 $3k+b$ 回です。

$c \lt k$ のとき、そのままでは同数にすることができません。ここで、2回操作を見ると、 $b,c$ を+1しつつ $a$ を-2できるので、必要な操作回数 $k$ を1回減らしつつ、操作可能回数 $c$ を+1できます。

まず、 $c \gt 2$ であれば、2回操作を一度もできないので、同数とすることは不可能です。

そうでない場合、 $l = \lceil \frac{k-c}{2} \rceil$ 回、2回操作すれば、後は(+2, -1, -1)で同数とすることができます。

よって、 $l回$ 分2回操作すると、 $a' = a-2l,\ b' = b+l$ となり、 $m=\frac{a '- b'}{3}$ 回で $a,b$ を同数にでき、更に $b+2m$ 回で0にできます。

したがって、式を整理すると $2l+3m+b$ 回必要になります。

提出コード：

https://atcoder.jp/contests/arc128/submissions/26597979