20200829_ABC177/

README

ABC177 感想

結構スムーズに5問解けたと思ったけど、順位は720位くらいでパフォ1600ちょい。 みんな強い。。

A問題

ちょっとむずかしいAだと思った。

分数が登場するので、積の条件で済むように式変形して判定する。 オーバーフローとかは流石に考えなくて良い。

B問題

文字列のスライシングをバグらせないように注意。

C問題

累積和を使って高速計算するが、引き算があるところでMODを雑にとってしまい、1ペナ。

CalcMod の関数はテンプレートにint版、int64版も置いてしまって、常にこれを使うようにする！

D問題

MSTの問題とか直前で解いてたせいで、ちょっと手間取ってしまった。

単純に連結成分の最大のものを見つければ良い。

E問題

結論から言うと、調和級数の計算量になる例のアレをやれば良い。

高速素因数分解

問題: A 以下の数が N 個与えられる。すべて素因数分解せよ。

なんとこれが高速に解けるらしい。 ぜひ覚えておきたい。

F問題

やりたいことはぼんやり描けたが、高速化の方法がさっぱりわからん。。