ABC046C問題 "AtCoDeer and Election Report"

bit探索完全に理解した(嘘です)

皆様夏休みいかがお過ごしでしょうか（まだ夏休みじゃないって？ 聞こえんなぁ！！）、文学徒です。レポートがつらい。あと昨日2完が悔しすぎてね、もうね。

色々あって逃避的に競プロの精進を加速させているわけですが、せっかくなので思考記録を付けて行きたいと考え、こいつを書いています。つまりこれは解説ではなく私の試行錯誤と七転八倒の記録です。興味のない方は素直にAtCoderの解説を見ましょう。

今回はABC046C問題 "C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report"を解いていきます（以下ネタバレ有、まだ解いていない方で見たくない方はブラウザバック推奨）。

問題文

シカのAtCoDeerくんは選挙速報を見ています。選挙には二人の候補高橋くんと青木くんが出ています。速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。AtCoDeerくんは $N$ 回画面を見て、 $i(1\leqq i\leqq N)$ 回目に見たときに表示されている比は $T_i:A_i$ でした。ここで、AtCoDeerくんが選挙速報の画面を$1$回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。 $N$ 回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。ただし、得票数が途中で減ることはありません。

はい。ちょっと数学っぽいですね。例も見てみるとこんな感じ。

入力例 1 Copy

Copy

3
2 3
1 1
3 2

出力例 1 Copy

Copy

10

二人の得票数が $2,3$ -> $3,3$ -> $6,4$ と動くと投票数は $10$ になって、これが最小値です。

なるほどな。

どうしたら良いのか全然分からない。

私は数学力（というか知識）が塵芥レベルなので、そもそも私はこれを手計算でもどう処理すれば良いのかわかりません。参加したコンテストでこれが出たら多分泣きます。

仕方ないのでとりあえずアルゴリズム的な視点で眺めてみると、ぱっと見では貪欲に処理することが思い浮かびます。......思い浮かぶのですが、この問題の数学的な性質を把握していないので何とも......。

DPっぽい気もするしちょっと試行錯誤します。

しました。

得られた知見なんですが、そもそもの話として総投票数はT[i]とA[i]を足した数で割ることが出来なければならないんですね。いや自明なんですけど。

例1で考えれば、初めの2:3の時、足して5人は確定（互いに素なので）。

その後1:1になるが、これは投票数が1+1=2で割れなければならないことを示します。よって5以上でかつ2で割り切れる最小の数字を考える必要があり、5に1を足して6が最小。

最後3:2になる時は6以上でかつ5で割り切れる最小の数字を考えれば良いので、10となる。

これをひたすら初めから貪欲でして行けばサンプルは通せそうな気がしてきたので、実装します。

実装途中で気付いたんですけど、計算量大丈夫かなこれ。大丈夫じゃなさそう。というか例3でWAしました。まあ知ってた。

バイト行ってきます。

ただいま。

まあ明らかに間違えてましたよね。例えば4人:3人→3:11の時って私の考えたやり方だと7→14になる（4人:3人→3人:11人）わけだけど、これは自明に6人:22人で7→28になります。

まあほぼ確実にDPですよね。明らかに遷移してますし。

だがしかし式が立てられないので解説を見ることに。

各途中状態で、できるだけ投票数が少ない方がよいです (投票数を増やすのはいつでも出来るので)。今高橋君に A 票、青木君に B 票入っていて、次に満たすべき比率が x : y だとすると、A ≤ nx ∧ B ≤ ny なるような最小の自然数 n を取れば、次にあり得る最小の得票数は nx, ny であることがわかります。このような nは max(⌈A/x⌉, ⌈B/y⌉) で計算できます。

はじめに A = 1, B = 1 として、これを N 回繰り返すことで O(N)で答えが得られます。 

はい。言われてみれば自明でしたね。この性質を使ってDPしたらできました。しんどい