AtCoder Beginner Contest 169
2020-06-02
競技プログラミング関係のメモを残していこうと思ったので, 書く.
コンテスト中に挑戦した問題についての感想とか.
A - Multiplication 1
掛け算するだけ.
現状, 私は速解きしても仕方ないのでこういう問題でもちゃんとテストして提出. テスト大事.
結果: AC
B - Multiplication 2
0が含まれるケースに気を付けないといけない. 優しいことにテストケースが用意されている.
とりあえず, 昇順でソートしてから掛け算を累積して, もし上限超えたら止めるということにした.
結果: AC
C - Multiplication 3
入力の値によって, 誤差をふくらませることになってしまう.
CLで解いてるので, 有理数型使えば良い. 私はBの文字列としての長さを見て判断した. 今回の問題設定では, 2, 3, 4でどこに小数点があるかということは確定する.
あとで他の人の解答を見て知ったのだがrationalizeを用いると簡単.
結果: AC
D - Div Game
素因数分解出来るかなという問題.
この問題の場合, 素因数分解は試し割法で十分間に合う.
試し割法はnの素因数分解をするために2から(floor (sqrt n))で割り切れるだけっていくという方法.
ある数iで割り切れる場合に(setf n (/ n i))として再度割る. 割り切れなかったら(incf i)して続けるというもの.
今回の問題の場合は(expt i j)でjを一つずつ大きくしながら割っていきカウントすると良い.
今回, 酷い間違いをしてしまったのは, 素数で割っていこうと毎回次の素数を計算していた.
高速なアルゴリズムだとそれでも間に合うが, 愚直にやるとこれでは間に合わない.
しかも, 終わってからしばらく高速な素数判定を知らなかったせいだと思いこんでおり,
sb-int:positive-primepなどを人の解答で見つけたり, なんだか興奮していた.
ひどく恥ずかしい.
まあ, 次に活かすために毎回素数判定が必要ないことを確認しておく.
素因数分解を試し割り法で行うとして, ある数xで割るという操作をする際には, 既にx以下の数では割り切れない状態である.
この時, 有効にカウントされるのは割り切れる場合であるが, もしxが合成数ならxより真に小さい素数yと正整数zが存在してx = y * zとなるので, 合成数xで割り切れるならこの様なyで割り切れるが, これは前提に反するので, xで割るという操作の際に割り切れるのであれば, xは素数である.
勉強になったコンテストだった.
結果: WAとTLE