📝

ABC047 D - 高橋君と見えざる手

2021/01/21に公開

解法

高橋君の戦略として、一つの町でまとめて買い一つの町でまとめて売るのが最善になる
仮に2つの町で売る場合を考える
売る町を $i, j$ とすると、
$A_i < A_j$ のとき $i$ で売る分をすべて $j$ で売ったほうが得である
$A_i > A_j$ のとき $j$ で売る分をすべて $i$ で売ったほうが得である
$A_i = A_j$ のとき $i$ で売っても $j$ で売っても利益は変わらない
よって一つの町でまとめて売れば良い
次に仮に2つの町で買う場合を考える
売る町を $i, j$ とすると
$A_i < A_j$ のとき $j$ で買う分をすべて $i$ で買ったほうが得である
$A_i > A_j$ のとき $i$ で買う分をすべて $j$ で買ったほうが得である
$A_i = A_j$ のとき $i$ で買っても $j$ で買っても利益は変わらない
よって一つの町でまとめて買えば良い

このとき売る町を $i$ とすると、買うべき町は $j = 1, 2, ..., i-1$ の中で $A_j$ が最小のときである
これはAを順番に見ていったときにこれまで出てきたAの最小値を変数にもっておくことで $O(N)$ で計算できる
$prof = A_i - min(A_1, A_2, ..., A_{i-1})$
このときの利益の最大値を $maxprof$ とすると
$maxprof = A_i - min(A_1, A_2, ..., A_{i-1})$ となるような $i$ のどれかで高橋君は売ればいいとわかる
こうなるような $i$ について青木君は $A_i$ を1減らすか、買う町の $A_j$ を1増やす必要がある
ある $A_i$ に対し対応する $A_j$ およびある $A_j$ に対し対応する $A_i$ は $A$ が相異なるという条件から一通りしか存在しないので、
青木君が減らすべき個数は $maxprof = A_i - min(A_1, A_2, ..., A_{i-1})$ となるような $i$ の個数に等しくなる

ABC047 D - 高橋君と見えざる手

解法

提出コード

Discussion