AtCoder Beginner Contest 182をPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 182を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - twiblr

求める値は$2A+100-B$となるので, それを出力します.

$k$を$2$から$A$の最大値(もちろん$1000$まででも問題ありません)までループさせて, 各$k$に対してGCD度を求めます. そして, 最もGCD度が大きかったときの$k$を出力します.

Pythonで組み合わせのリストを作成するには, itertools.combinations(リスト)を利用します.

$N$の桁のうち$0$個を消した場合, $1$個を消した場合, ……と順に試していき, $3$で割り切れた場合に消した桁数を出力します. $3$で割り切れるかどうかの判定は, 各桁の数字の合計が$3$で割り切れるかどうかで行います.

愚直に行うと$O(N^2)$かかるため, TLE. そのようなコードを参考までに以下に示しておきます.

そこで, 「正の向きに$A_1$進み, 正の向きに$A_2$進み, 正の向きに$A_3$進み, …, 正の向きに$A_i$進む」という一連の動作を動作$i$とします.

ある変数$p$に対して, $A_i$を順に足していくことで「動作$i$の合計の座標の変化」が分かります.
また, $p$が最大だったときの値を(変数$q$に)保存し続けることで, 「動作$i$を座標$0$で始めた場合の, 開始から終了までの座標の最大値」が分かります.
さらに, $p$を順に足し続けてきたある変数$x$に対して, $q$を足すことで「動作$i$が行われている間の座標の最大値」が分かります.
つまり, $x$が最大だったときの値を(変数$r$に)保存し続けることで, 求める最大値を得ることができます.

この方法なら$O(N)$ですみます.

E以降は私の能力不足故に省略いたします.