ABC054-D「Mixing Experiment」

シェアする

  • このエントリーをはてなブックマークに追加

こんばんは。

本日、アニメ映画「ポッピン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]の絶対値の最大値*薬品数の最大値+1」とする必要があります。

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]の最小値」の小さい方が答えになります。

以上が、私が考えた面倒な解法です。

本日はここまで。では。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする