こんばんは。
本日、アニメ映画「ポッピンQ」の小説版が届きました。
ストーリーはもちろん映画と全く同じなのですが、心理描写が深く、映画では省略されたやり取りもあります。蒼による天照大神の知識の披露や、ポコンが伊純に"あいつ"について話をしている、など（映画のネタバレ回避）。
また、伊純が時の谷に行った後も少しの間だけ土佐弁が残っています。
まだ半分ほどしか読んでいませんが、映画を3回見たあとでも楽しめる内容になっています。
ついでに日岡蒼ちゃんの「ポッピンQ プレートバッジ」も購入しました（下のは大道あさひちゃんのもの）。プレートバッジはあさひちゃんのものが1点しか残っていないようです。
さて、先日、AtCoder Beginner Contest 054が開催されました。
今回はRegular Contestとの同時開催ではなかったので、ABCに参加しました。
目標は全完とし、なんとか達成することができました。
D問題の私の解法が、解説資料の解法（綺麗な解法）と異なる変な解法だったので、紹介したいと思います。
問題はこちら→ D - Mixing Experiment
考察
混合比の条件を満たす選び方について考えます。
選んだ薬品の中に含まれる物質Aと物質Bの総重量をそれぞれA,Bとすると、
A:B=Ma:Mb
が成り立つので、
Ma*B-Mb*A=0
となります。したがって、各薬品iについて
d[i]=Ma*b[i]-Mb*a[i]
という値を用意すると、選んだ薬品のd[i]の和は
Σd[i]=Σ(Ma*b[i]-Mb*a[i])=Ma*(Σb[i])-Mb*(Σa[i])=Ma*B-Mb*A=0
となります。（総和Σは、選んだ薬品のみの総和とする）
したがって、問題は「d[i]の総和を0とする選び方における、c[i]の和の最小値」を求める問題に変わります。パラメータ数が減りました。
しかし、d[i]は負の値も取りうるというのが厄介ですね。
ここで、選び方には以下の2パターンがあります。
①d[i]=0となる薬品を1つだけ購入する（元から混合比がMa:Mbとなっている薬品だけ購入）
②d[i]>0となるものとd[i]<0となるものを購入し、合わせて0になるようにする
ここで、①のパターンは簡単です。d[i]=0を満たすものの中でc[i]の最小値を求めればいいので（複数の薬品を混合する必要が無い）。
また、②のパターンでは、d[i]=0となる薬品は使いません（使うとコストは増えるのにメリットが無い）。
以下では、②のパターンについて考えます。
選んだ薬品を、d[i]>0のものとd[i]<0のものに分けると、それぞれのd[i]の和の絶対値は一致します（d[i]>0となるもののd[i]の和をmとすると、d[i]<0となるもののd[i]の和は-mになる。足して0になるので）。
ということで、全薬品を、d[i]の値が0か正か負かで分けて考えます。
d[i]が正のものだけを集めて、d[i]の和がmになるようにしたセットと、負になるものだけを集めて和が-mになるようにしたセットを合わせると、条件を満たすことができます。
したがって、以下のように考えます。
plus[m]には、d[i]が正になるものだけを用いてd[i]の和をmにできる選び方のうち、c[i]の和（費用）が最小になるような選び方の、c[i]の和を格納し、
minus[m]には、d[i]が負になるものだけを用いてd[i]の和を-mにできる選び方のうち、c[i]の和（費用）が最小になるような選び方の、c[i]の和を格納します。
ただし、そのような選び方が無い場合はINF（10^9程度）を入れます。
そうして得られたplusとminusについて、plus[m]+minus[m]（総費用）の最小値を求めます。これがパターン②の最小コストです。
plusとminusは、ナップザック問題と同じ動的計画法で求めます。その解説は面倒なので「ナップザック問題 動的計画法」等でググってください。
始め、plus[0]=0、minus[0]=0とし、他は全てINFで埋めます。
各薬品のd[i]に対して、正なら、全てのmに対して、mが大きい順に
plus[m+d[i]]=min(plus[m+d[i]], plus[m]+c[i])
で更新していきます。minusについても、d[i]<0となるiに対して
minus[m-d[i]]=min(minus[m-d[i]], minus[m]+c[i])
とします。d[i]<0なので、-d[i]>0となることに注意してください。
plus[]とminus[]の要素数は、「d[i]の絶対値の最大値＊薬品数の最大値＋１」とする必要があります。
d[i]はMa*b[i]-Mb*a[i]なので、その絶対値の最大値は、max(a[i],b[i])*max(Ma,Mb)になります。
これに薬品数Nの最大値を掛けて、10*10*40+1=4001となります。
そうして得られたplusとminusに対して、plus[m]+minus[m]の最小値を求め、その値と「d[i]=0となる薬品のc[i]の最小値」の小さい方が答えになります。
以上が、私が考えた面倒な解法です。
本日はここまで。では。
