📝

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

2021/01/21に公開約900字

解法

高橋君の戦略として、一つの町でまとめて買い一つの町でまとめて売るのが最善になる
仮に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_iAが相異なるという条件から一通りしか存在しないので、
青木君が減らすべき個数はmaxprof = A_i - min(A_1, A_2, ..., A_{i-1})となるようなiの個数に等しくなる

提出コード

https://atcoder.jp/contests/abc047/submissions/19550515

Discussion

ログインするとコメントできます