PCT's Soliloquy

数学と競プロについての忘却記

AC黄色になりました

PCTです。AtCoder黄色になることができました!

 色変記事です。色々書きます。

 はじめに

競技プログラミングをしているPCTといいます。数学をしている人に勧められて競技プログラミングを初め、それが面白くてハマってしまいました。

そして先日、3月20日にあったABC196でついに黄色になることができました。

精進記録

f:id:PCTprobability:20210405152856p:plain

f:id:PCTprobability:20210405153111p:plain

f:id:PCTprobability:20210405153203p:plain

最近は、高難易度に強くなりたいので黄diff以上を埋め始めています。

また、レートを上げるには遠回りになるかもしれませんが自分の興味を持った分野を深く勉強してみる。なども少し始めています。

学習したもの

青から黄になるまでで学習したものを上げていきます。

 

グラフライブラリ

dijkstra、BellmanFord、トポジカルソートの機能をつけたグラフライブラリを制作しました。

最低限の機能といった感じですが、ABCを解く上ではこれがあればあまり困らないと思います。

どうしても定数倍の重いコードを書いてしまいがちで、困っています。どうすれば定数倍の軽いコードを書けるのでしょうか...

これは今後の課題だと思っています。

 

形式的べき級数

青から黄の期間で始めた、ということではないのですが本格的に武器に出来るようになったのはこの期間だと思っています。

ライブラリも作りました。modがNTT-friendlyでない時も使えるように任意mod版も作っています。(任意版ではかなり定数が重くなってしまったので、まぁまぁ使いにくいです...)

ライブラリを使わなくても考察で使うことによって問題を解ける。解けるとまではいかなくても考察が楽に進められるなどといったことが多くとても便利に感じています。使っていて楽しいです。

まだまだ知らない使い方があるので、マスターしていきたいです。

 

Trie木

文字列を管理できる木構造です。

これ、とても賢いな~と感じました。Trie木を使ったことはまだ1回しかありません。いつか使える日が来ることを願って...

 

Mo

これもまだ1回しか使ったことがないですが、仕組みを理解しライブラリにもしました。

ふと思い出してツイートしてみたら物理好きさんが詳しく教えてくれてMoを使う問題

まで教えてくれてとても感謝しています。分割統治についても教えてもらいました。

これは雑談になりますが、私がNPCAに入部した年に物理好きさんが卒業してしまったのは少し寂しいです。

 

知っているが未学習のもの

フローアルゴリズム

使えるには使えるのですが、計算量が特殊な時に落ちたり、逆辺を貼ったりするのがまだいまいち理解できていません。仕組みを知らないでブラックボックスとして使ってしまっているのはいい状態とはどう考えても言えないので、理解したいです。

 

Dirichlet積

形式的べき級数の指数法則が積になったverととらえています。これも数え上げに使えそうでとても面白そうなのですが理解が遅くまだいまいち自分のものに出来ていません。

ライブラリは積と単位元ゼータ関数のみ作っていて、ARC116-Cを高速に解けることを確認しました。

 

 これからについて

黄色になれたのは嬉しいのですが、レートを稼げていたABCがunratedになってしまって停滞するのではないか。という恐怖を感じています。

f:id:PCTprobability:20210405155212p:plain

f:id:PCTprobability:20210405155253p:plain

速解きタイプなのが見てわかると思います。ある程度の難易度までを高速に解き、残りの時間を高難易度に費やして解けずに少し温まって終わってしまう。ということを青の時から繰り返してしまっています。

これが一番の今後の課題で、コンテスト中に安定して黄diffまでを通せるようになる。というのをしばらくの目標にします。

そのために4月10日にあるAGCでは大爆発したいです。1036prfを取れば青落ちはしないので、よっぽどのことがない限り黄のままでいられると思います。

目標は橙prfを取ってレートを2100に乗せることです。頑張ります。

 

終わりに

あまり内容の濃くない記事になってしまったと感じています。いかがだったでしょうか。

これからは今までのような速解きだけでは通用しにくいと思っているので、高難易度を解けるようにしていきたいです。得意分野を橙diffまで解けるように。苦手分野でも青diffは確実に解け、黄diffもたまに解けるレベルまで持っていけたらと感じています。

前のようなStreakを繋げるための精進をやめて、高難易度を考える習性をつけようとしているのでこれがいつか実力となってくれたら嬉しいです。

 

そして、レートの目標をたてたいと思います。かなり厳しめの目標を立てます。

・6月にレート2200達成

・8月にレート2400達成

*1

とても厳しい目標だと思います。けど、ここで甘えていては一生赤になどなれないと感じたのでこの目標をここで宣言します。

ただ、学業も少しずつやらないといけないのでそちらの方も頑張ります...

次回のAGCは、NoSubしないように初めにFにCE提出を必ずします。これでレートが下がってしまっても勉強料だと思うことにします。

頑張るぞー!

*1:言ってから気付きましたが、これ8月までに安定して黄diffを通し50%の確率で橙diffも通す。ということですよね。頑張らないと...