ABC047 D - 高橋君と見えざる手 / An Invisible Hand
問題
提出コード
デバッグ出力と一緒に答えの出力を消してしまわないように注意しましょう。
解法
高橋君が最大の利益を得るとき、売る町と買う町は1つずつで、それぞれT/2だけ買い、T/2だけ売ることになります。
売値と買値の差が一番大きい場所が、その売る町と買う町になります。
その際、利益を1円下げるには、このどちらかの値段を1円ずらせばいいことになります。
ですが、(売値-買値)が最大になる場所が複数箇所存在しているとき、その複数箇所それぞれについて、売る町もしくは買う町のどちらかの値段をずらす必要があります。
また、問題のがすべて異なるという条件から、候補の売る町(もしくは買う町)が同じ町になることはありませんので、例外を考慮する必要はありません。
よって、あとはその候補の個数を調べればよいです。
まずは、(売値-買値)の最大を求めます。
~の中での最小値を、から引いたときが最大値の候補になりますので、これをすべてのについて行えばよいです。これはで求められます。
利益の最大値(とします)が決まったら、あとは売る町と買う町のペアの個数を求めます。
mapを使い、までに、となるようなが存在するかどうかをしらべ、存在したらカウントを増やしていけば良いです。
このカウントが、最終的な答えとなります。