Editorial
Xをデタラメに定めても大して意味のある値にならないことはわかると思います。
そこで、数列Aの中の数字を用いてXを定める方法を考えます。
数列Aの最小値を達成したいなら数列Aの中で一番登場回数が多い因数をXと定めることで最適になる気がします。
よってこの方針を考えてみることにします。
世の中には偶数が大量に溢れているのでだいたいの場合はX=2と定めると最小値を取ります。
ここで、偶数だけの数列Bを考えてみます。
N=5B={2,4,8,12,16}
すべて偶数であるので2で割るのが最適であるように思います。
ここで実際にX=2であると定めXで割ったあとの数列をX′と定めると
X′={1,2,4,6,8},Sn=∑i=15Xi′=21
となります。
しかし実はX=4とするのが上の数列では最適であり、X=4のときSnは以下のようになります。
X′={2,1,2,3,4},Sn=∑i=15Xi′=12
このような例で実は一番多く登場する因数が最適なXとは限らないことがわかります。
実際のところどの約数が最適かは試してみるしかありません。
だからといってすべての約数に対してN回の割り算を繰り返すとかなり軽く見積もってもO(Nmax(Ai))となりTLEしてしまいます。
そこで次に以下のようなことを考えてみます。
Xを定めた後の総和をSnX, もとの数列の総和をSnとすると
SnX=Sn−変更されたAiの総和+変更後のAiの総和
が成り立つことを考えます。
先程の数列Bを例に取ると、
X=4のときSn=42SnX=12変更されたAiの総和=40変更後のAiの総和=10
これを先程の式に当てはめてみると
12=42−40+10=2+10
一致します。
さて、これによって考えられるすべてのXでAiを割るという操作をなくすことができます。
なぜなら、ある約数D(1≤D≤max(Ai))でどれだけのAiが影響を受けるのか。受けた結果の総和はいくつか。がわかれば試し割りをしなくても数列の総和は上の式を用いて計算することができるからです。
メモをした変位量を用いて数列の総和が最小になったときが最適なXであり、そのときのSnXが答えです。
ここで、N及びAiの成約は十分に小さいのですべてのAiに対してO(Ai)だけ時間をかけて約数列挙を行っても問題はありません。
また、メモした配列(リスト型)を見て最小値を判定するのはすべて定数時間で行うことができるのでこの問題をO(Nmax(Ai))で解くことができました。(実際は定数倍が重いのでPythonでの実装には気をつけてください。ループが主なのでPyPy3などで実行すると高速化すると思います)
ちなみにテストケースのKillerたちの中身ですが、2が最適なXでない場合です。
実はKiller以外のテストケースはすべてX=2で最小値を取ります。
回答例(C++)