7K12 blog

猫でも分かるアルゴリズム解説

ABC136 E - Max GCD

f:id:tkr987:20200325023642p:plain

https://atcoder.jp/contests/abc136/submissions/11077726

diff1600を超えると数学的素養がないと考察を進めるのが厳しい。

理解はしたけど一生出来るようにならないという気分になった。

  • 各操作をしても合計は不変
  • 答えMは \sum A_{i}の約数
  • 約数の個数は対数程度に収まる
  • 剰余を0かMにする操作を調べる
  • a-b=(M-X)-(M-Y)=Y-X

まず、文章を読んで気になる点として、各操作をしても合計が変わらないという事が挙げられる。各操作をすることで数列 A_{i} A'_{i}に変わったとき、割り切れる答えをMとすると全ての A'_{i}=c_{i}Mなので \sum A'_{i}=CM=\sum A_{i}となる。すなわち、答えMは \sum A_{i}の約数となる。約数の個数は log{NA}程度になる。高度合成数を参照。

https://ja.wikipedia.org/wiki/%E9%AB%98%E5%BA%A6%E5%90%88%E6%88%90%E6%95%B0

f:id:tkr987:20200330153758p:plain

次に、「各操作をしてMで割り切れる」という処理をするために各Aiの剰余を取っておく。この剰余を0かMにしたとき「全てのAiがMで割り切れる」ということであり、どのように矢印を選んでも各Aiの剰余を0またはMにする限り「全てのAiがMで割り切れる」ということになる。各操作は+1と-1がセットなので下矢印と上矢印の合計が一致してなければならず、そういう条件を満たす矢印の長さとKを比較すれば良い。Aiの剰余の合計と○倍のMが等しいので「剰余をソートして左側を0にして右側○個をMにするような組み合わせを全て試す」という処理をする。

 

下矢印と上矢印が交互に現れる場合、 a-b=(M-X)-(M-Y)=Y-Xなので入れ替えても矢印の合計は変わらない。そういう組み合わせは枝刈りすることが出来るため、計算量が O(N\log{NA})に収まる。

 

自分の質問箱リスエストに答えてくれた以下の解説が非常に参考になる。

https://betrue12.hateblo.jp/entry/2020/03/28/142051