【5日目】はじめてARCを解いてみた - 茶coderが1カ月だけ競プロをガチってみる

最初はABCをやろうと思っていたのだが、時間もあるのでARCにチャレンジしてみた。

結果はご覧の通り。

f:id:danook:20210410104719p:plain

400点問題と500点問題の間の壁はやはり高かった。A,Bは(若干苦戦しつつも)解けたが、C,Dは全く歯が立たず、途中でギブアップ。以下解説を見て再考。

C - Multiple Sequences

$A_1, \frac{A_2}{A_1}, ...$ への素因数の割り振りを考えるという発想がなかった。これは持っておきたいと思う。

ついでにこの問題を解くために、素因数分解と二項係数のアルゴリズムを作って保存しておいた。

計算量 $O(\sqrt{n})$ 。もっと高速化できないのかな？という気もするが、 $O(\sqrt{n})$ かかることは稀と思われるので、多分これで間に合うのだろう。

数が大きくなるのでmodをとる。DPを用いて計算量 $O(n)$ で逆元を求める漸化式が？？？だったが、以下のサイトが非常に参考になった。

これらを用いていざ実装…と思ったがまだうまく動いていないので続きは明日。D問題も明日復習することとする。

A, Bも少し課題が残る結果になった。Aはもう少し速く書けた気がしているし(ろくに考えずいきなりコードを書こうとして失敗した)、B問題は

998244353で割った余りを答えてください

という問題形式だったので、それに備えて用意しておいたmodintクラスを転用しようとした…ところまではよかったのだが、いくつか不具合が残っていてその修正に苦戦してしまった。あと単純にfor文の範囲を間違えた。これやりがちだから気をつけねば。

さてさて明日は

ABC198

が開催される。ここでいい成績を残してratingを上げておきたい…しばらくABCないから。目標は

5完。

今のレベルだと結構ギリ…だけど頑張ろう。焦らず落ち着いて。