AtCoder ABC125感想

AB2だけAC、CはTLE、Dはそもそも見てない。

◆Cについて

・「一つを好きな値に変える＝取り除く」までは分かったので、残りに対して二分探索で最大公約数を求めようとしたがTLEから抜けられなかった。選んだ要素の左右の配列について最大公約数を求め、両者の最大公約数を求めるといいっぽい。これは思いつかなかった。

◆Dについて

そもそも解けないだろうと思ってチラ見して放置してたが、これはちゃんと考えればとけたかも。反省

◆今回の学び

・Dでも解けるかもしれないので20分ぐらいはちゃんと考える。

・今回Cで取り除いた要素の左右のリストを連結してGCDにかけたりしてTLEだった。これは連結時にN-1個分のメモリを確保してそこにコピーしなおす処理が行われている（はず）のと、N-1個の要素について、functools.reduce(GCD, list)としたことがTLEの原因だったはず。

・メモリ上の移動を伴う可能性のある操作は避ける

・左右に切り分けて結果を統合する発想

うーん。やっぱりまだまだだなぁ。