Blackboardを解く2019年4月29日Pythonツイートシェアはてブ送るPocket何度かTLEしながらなんとか答えにたどり着いたので、考え方をメモしておきます。使用する言語はPythonです。A1,A2,...,ANが黒板に書かれています。あなたはこの中から整数を1つ選んで、1以上109以下の好きな整数に書き換えます。元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。入力は全て整数である。tmpprint(ans)“整数を1つ選んで、1以上109以下の好きな整数に書き換える”とは、”整数を1つ選んで取り除く”ことと同じであると解釈できます。1:]で整数を1つ取り除いたリストの全パターンを作り、最大公約数を毎回計算しました。N-1個の整数の最大公約数を取る処理をN回行うのでTLEしました。累積和を応用した累積GCDという考え方を使えば、大幅に計算量を減らすことができるようです。AtcoderのPython3のバージョンが3.4.3のため、mathモジュールではなくfractionsモジュールにgcd()関数があります。12だった場合を考えてみましょう。12]から最大公約数を求めるといったように進んでいきます。12]の最大公約数を2回求める必要があります。12]の最大公約数を保持しておけば、48や64との最大公約数を求めるだけで計算できます。いった、重複する処理を削減するために累積GCDを使います。そもそも累積和を忘れてしまった方は、こちらの記事が非常に参考になります。復習しておきましょう。左側からの累積GCDを以下のように用意します。A0とA1とA2と...とANの最大公約数また、右側からの累積GCDも用意しておきましょう。0]4と出力されます。わかりやすいように、左右からの累積GCDも出力しました。累積GCDによって計算量はかなり減少しました。このコードではまだTLEしてしまいます。累積GCDを求める際に、appendで一つずつリストに追加していることが原因です。appendを使うと、リストの中身をコピーして作り直します。競プロでは実行時間を極力短くしたいので、使うのは避けたほうが良さそうです。TLEするのは先頭へのinsertがO(n)であることが原因だとコメントをいただきました。使う操作はOを調べるよう注意することにします。1)と書いて領域を確保しておきます。1]))print(ans)これを時間内に閃くって相当難易度高いんじゃないですかね。Atcoder参戦して2回目の人間にはかなりハードルが高かったです。早く茶色まで上がりたい。コメントをキャンセルメールアドレスが公開されることはありません。SilverPCとかDbDとか、自分の興味のあることについて書いてます。