ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Regular Contest 085 E - MUL

AtCoder プログラミング競技プログラミング

お題箱より。

解法

私自身、この問題は解説を読んで衝撃を受けた記憶があります。知らないと自力で思いつくのは相当難しいので、テクニックとして覚えてしまいましょう。

先人の知恵

競プロでは俗称「燃やす埋める問題」と言われている問題カテゴリです。この言葉で調べると競プロ関連の情報が出てくると思いますが、特に以下の2つの解説がオススメです。

最小カットを使って「燃やす埋める問題」を解く（後半は難しいです）
最小カットについて - よすぽの日記

私の解説もだいたいこの2つの解説と同じような説明になりますが、今回の問題でどのように解いていくかを具体的に書いていこうと思います。

「燃やす埋める問題」の定式化

「燃やす埋める問題」は、以下のように表現できる問題、およびそれを解くテクニックの呼び方です。これは基本形で、上記リンク先（特に診断人さんのスライド）には色々な応用が紹介されています。

$N$ 個の要素があり、それぞれについてAとBの2択の選択肢がある。

今回の問題では、各宝石を「残す」と「割る」の2択です。

各要素の選択肢それぞれについて、報酬や罰金が設定されている。

今回の問題では、残すと $a_{i}$ 円の報酬（負なら罰金）。割るとプラマイ0円。

以下のような条件がたくさん存在する。
- ある2要素 $x, y$ について、" $x$ はBだけど $y$ はA" という選び方にすると罰金が発生する。もしくは、この選び方にすることができない。

この条件への対応付けは少し言い換えが必要です。今回の問題の「正整数 $x$ を選ぶ。 $x$ の倍数が書かれた宝石を全て叩き割る。」という条件は、「2以上の整数 $k$ について、 $x$ を割って $kx$ を残すことはできない」と言い換えることができて、この条件の形になります。

罰金の最小化（報酬の最大化）をしたい。

こんな問題です。

グラフを作る（仮）

このように表現できる問題を、以下のようなグラフの最小カット問題に帰着させて解きます。 $N=4$ とします。

f:id:betrue12:20190705005603p:plain

f:id:betrue12:20190705005611p:plain

グラフの作り方を言葉で書くと以下のようになります。

各条件を真ん中に並べて、始点 $S$ からの辺と終点 $T$ への辺をそれぞれ張る。
始点側の辺には選択肢A（残す）の罰金を、終点側の辺には選択肢B（割る）の罰金を重みとして設定する。報酬は全て罰金に言い換える。
「" $x$ はBだけど $y$ はA" という選び方にすると罰金」という条件それぞれについて、AからBにその罰金を重みとする辺を張る。「できない」場合は罰金 $\infty$ とする。

このグラフにおける最小カット、つまり「始点から終点まで到達できないようにするために切る辺集合」（これをカットと呼びます）の重み合計の最小値が、この問題における罰金の最小値になります。

ここで真ん中の頂点それぞれについて、始点側と終点側の2辺のうち必ず一方は切らないといけません。この辺を「切る」ことが、対応する選択肢を「選ぶ」ことに対応します。繋がっている方を採用するわけではないことに注意してください。

※ここで「両方切ったほうがトータルで得になる可能性はないの？」という疑問が浮かぶかもしれません。最後に補足します。

そして「" $x$ はBだけど $y$ はA" という選び方にすると罰金」という条件については、そっちの辺を切ったときにカットが成立しない方向に辺を張る、と覚えましょう。

f:id:betrue12:20190705013402p:plain

「解ける」ように条件を整える

この最小カット問題を解くために、いくつか条件を変形して整える必要があります。先ほど既に書いたものもありますが、確認していきましょう。

まずは全部罰金にして最小化問題に

先ほども書いたように、これは罰金を辺の重みとするグラフの最小カット問題になります。そのため「 $a_{i}$ 円の報酬」を「 $-a_{i}$ 円の罰金」と言い換えることで全条件を罰金にして、罰金を最小化する問題にします。

「できない」は $\infty$ 円の罰金に置き換える

先ほど書いた通りです。実装上は十分大きい数とします。

全部の罰金を非負にする

最小カット問題をよく知られたアルゴリズムで高速に解くためには、全ての辺重みが非負である必要があります。例えば正の報酬を罰金に置き換えると負の罰金が生まれてしまうので、これを上手く非負の罰金に変換します。

今回の場合は、 $a_{i}$ が正のときに「残すと $-a_{i}$ 円の罰金、割ると0円の罰金」となって負の罰金が登場します。これを

無条件で $a_{i}$ 円もらえる。 その上で、残すと0円の罰金だが、割ると $a_{i}$ 円の罰金（もらったものを没収されるイメージ）

と置き換えます。こうすると罰金を非負にすることができます。これは今回の問題に限らずよく使うテクニックです。

グラフを作る（改）

具体的に、入力が

4
1 -3 1 2

の時のグラフを描いてみましょう。先ほどの方法で罰金を非負にしないようにすると、以下のグラフを得ます。

f:id:betrue12:20190705005624p:plain

あとは最小カット問題を解きます。この解は「最大フロー最小カット定理」より最大フロー問題の解と一致するので、最大フロー問題を効率的に解くDinic法などのアルゴリズムで解くことができます。

例えば先ほどの入力例では、以下が答えになります。

f:id:betrue12:20190705005633p:plain

おまけ：「両方切る」可能性は考えなくて良い？

先ほど書いた、「始点側と終点側の辺を両方切ったほうがトータルで得になる可能性はないの？」という話です。もし仮にこれが最適解になってしまうと、「 $N$ 個の要素の2択を選んでいく」元の問題との対応が取れません。

これは両方切ることが得になりそうなグラフを実際に考えてみると分かります。ある頂点 $i$ について、始点からの辺と終点への辺がどちらも正の重みを持ち、最小カットにおいてどちらも切られているとします。

まず最適解において始点からの辺が切られている場合、以下のような経路が存在しているはずです。もしこのような経路がない場合は、単にこの辺を切らないようにして値を改善できるからです。

f:id:betrue12:20190705012238p:plain

同様に終点への辺が切られている場合は、以下のような経路が存在しているはずです。

f:id:betrue12:20190705012250p:plain

これをつなげると…以下のように始点から終点への経路ができてしまいます。

f:id:betrue12:20190705012307p:plain

これは最小カットだという仮定で出発したのに、カットになっていません。つまりこのことから、「始点からの辺と終点への辺がどちらも正の重みを持ち、最小カットにおいてどちらも切られている」ということは有り得ないことが分かります。

ただしこれはあくまで、今回紹介した方法で構成したグラフに限定した証明です。私自身、別の問題で最小カットに帰着したときに「余分に切ったほうが得になる場合がある」ようなグラフを作ってしまってACできなかった経験があるので、とても重要な着眼点だと思います…。

ACコード

Submission #6238817 - AtCoder Regular Contest 085

ちゃんと手元で図を描いて、どっち側の辺を切ることがどっちの選択肢に対応しているかも書いて、グラフを構成していくのが慣れるコツだと思います。

類題

比較的考察がやさしい類題です。AtCoderだとフローに帰着するまでが難しい問題が多いので、Codeforcesから。

Problem - 1082G - Codeforces