脳log[20220613]

2022年06月13日 (月) [AtCoder] 精進。ABC136-E「Max GCD」(ギリギリ青 diff)。操作によって A の総和に変化がないので、A の総和の約数が答えの候補。飛び飛びに存在する GCD の倍数に A 数列の各要素を寄せていくイメージ。操作回数に制限がないなら総和そのものが答え。１は常に可能な答え。それ以外の答えを約数の大きい順にテストしていく。■提出 #32461534 (AC / 448 Byte / 131 ms)。判定関数が全然わからなかった。足す数と引く数の釣り合いが必ず取れることは決まっているのだけど、釣り合いが取れるまでの操作回数がわからなかった。Array#insert を繰り返す効率の悪い方法で数えている。