ABC136 E Max GCD
自力考察
まずサンプルから推測すると考えられる答は$ \sum_{i=1}^{N} A_iの約数である.
ここで, 約数を全探索してその値を$ Xとおく. 以後, 操作後に$ Xになることはあるか?という判定問題を解く.
$ B,Cの要素$ B_i, C_iを次のように定義する.
$ B_i = $ a_i - X \cdot (a_i / X) (つまり, $ A_iから$ A_i以下の$ Xの倍数のうち最大のものを引く)
$ C_i = $ X \cdot (a_i / X) - a_i (つまり, $ A_iより大きい$ Xの倍数のうち最小のものから$ A_iを引く)
例えば$ X = 7, A= [1, 2, 22, 27]とする.
このとき, $ B = [1, 2, 1, 6], C = [6, 5, 6, 1] である.
さて, 問題は "各$ iについて$ B_i, C_iのどちらかを選び, それぞれ$ sumB, sumC に加算する.
このとき, $ (max(sumB, sumC) \le K))という条件を満たすものは存在するか?" に帰着された. あとはこれを解けばよい. しかしこれ, 解けるのだろうか? DPっぽい感じはするが… (→ 学校で考えてたけどやっぱり解けなかった, 解説見る)
解法
上と約数を全探索するところまでは一緒. まず, $ R_i= $ A_i \mod Xとおいて,$ Rをソートする. こうしても正確に求まり, 大幅に計算量を削減できる. 詳しいものは他の方が書かれているので, ここでは簡単に証明する.
$ Proof. 各$ R_iを$ 0か$ Xにしたい(そうでないと明らかに損する). もしもある$ R_i, R_j (i<j)について$ R_iが$ X目標, $ R_jが$ 0目標(逆転している)とすると, それらの目標をswapすることでより良くなる. よって示せた.
あとは最初から$ i要素を$ 0目標にする全探索をするとこの問題が解けた($ 0目標, $ X目標の$ R_iそれぞれの和のmaxがKより小さければOK).
感想
やー ソートするという発想が思いつかなかった. でもこれかなり良問だと思う.
初めて解説を書いた気がする. Texに慣れるという意味でも結構良い練習になった. 証明の部分あまりにも端折りすぎたかもしれないけど.