精進の振り返り【2020年9月号】
まえがき
regiです。唐突に、その月でどんな精進をしたのかを月末にまとめておいて、数ヶ月後辺りに自分で見返して「うわあ！」したいと思ったので、今月からそういう記事を書き始めます。また、秘密の精進ノートに書いてうふふするのも良かったのですが、どうせなら記事に書いておこうというノリで始めました。何かの間違いでだれかの役に立つかもしれないので...。
今月のAtCoderレーティング変化
2020/09/13 Rating 1546->1619
入青しました！下に入青記事のリンクを載せておきます。
2020/09/19 Rating 1619->1659
変なバグらせがいっぱい発生したけど、レート伸びて嬉しかった。
2020/09/20 Rating 1659->1666
UnionFindちゃんと最小費用流ちゃんにボコボコにされた。恋人の整数ちゃんは600点くれてよしよししてくれた。好き。(惚気話)
2020/09/26 Rating 1666->1645
最小費用流ちゃんと仲良くなりたくて、遅延セグ木ちゃんそっちのけで距離を縮めてたら、遅延セグ木ちゃんにボコボコにされた。
今月に作ったライブラリ
エラトステネスの篩を用いて素因数分解を高速に行うライブラリ
某ABCで犯罪を犯してしまったので、罪滅ぼしのために作りました。
フォード・ファルカーソン法
デニック法は気が向いたら作ります。
プライマルデュアル法
ポテンシャルを導入して、最短路をダイクストラで求められるようにしました。また、最初にベルマンフォードを回すことで、負のコスト辺も張れるようにもしました。ただし、負の閉路の対処はまだよく知らないため、それはこれから勉強して書き換えます。
区間更新・区間最小クエリの遅延評価セグメント木
非再帰にしたいです...。(小声)
抽象化もしたいです...。(小声)
区間加算・区間和クエリの遅延評価セグメント木
非再帰にしたいし、抽象化もしたいぜ。
木の重心を求めるライブラリ
こどふぉに出てきてびっくりしたから作りました。
LCS
一応作りました。
ベルマンフォード法
ベルマンフォードを再び回し、各ノードにおいて、最短路長を永遠に小さくできるようなノードであるか否かの判定をする機能もつけました。今後、ベルマンフォード法だけでなく、最短路を求めるアルゴリズムライブラリ全てに復元機能をつけておきたいですね。
今月に解けるようになった問題
フロー全般(最大流や最小カット、最小費用流、最大マッチング、最小点被覆など)
結構さまざまな問題見て解いたため、ある程度は感覚を掴めた気がしますが、まだまだできないので、さらに解いて学んで武器にしたいです。
有向グラフにおける最長路問題
有向グラフにおける最長路問題ってベルマンフォード法使うと解けるんですね、びっくりしました。その実装は以下の問題で練習することができます。皆さんも是非とも。
https://atcoder.jp/contests/abc061/tasks/abc061_d
FFTやSCC、2-SATなど、ACLで取り上げられているアルゴリズムを使う問題
易しめなら解けます...。
遅延評価セグメント木を使う問題
私が持っているライブラリで「「何とかなる問題」」なら「「ある程度」」解けます。
来月に頑張りたいこと
フロー全般
これは継続して勉強していきます。特に、アルゴリズムの正当性の証明と、最小費用流における負の閉路の対処、フローに帰着させることができる問題において使える考察パターンについてきちんと押さえたいですね。
セグメント木と遅延セグメント木の非再帰での書き方と、抽象化
特に抽象化はきちんと勉強したいです。セグ木に殴られる人から、セグ木で殴る人になりたいです。
全方位木DPの抽象化
どこかの記事によるとこれも抽象化できるらしい...？なのでやります。
SCCや2-SAT、FFTにおいて使える考察パターンを身につける
まだあまり問題を解くことができていないので、問題を良く解いて、良い考察パターンを身につけていきたいですね。
ダブリング
最近、ABCでよく話題になっているため、流石にやります。
行列におけるrankを使う問題
現時点では自分にとって得体の知れない問題なので、解けるようになっておきたいです。
グラフ問題についての情報収集
グラフにやられっぱなしなので、本当に舐め回すようにさまざまな情報やテクニック、考え方を集めたいです。
EDPC
まだA～Eしかやってなくてごめんなさい...。
包除原理を用いた数え上げ
流石にやります。
その他
ライブラリ整備とかいろいろ。
あとがき
並べてみると、頑張るべきことがかなり多いですね。さらには大学も再開して、その上、開発の勉強も頑張りたいため、上手いこと回せるかかなり心配です。まあ、無理をせずコツコツ焦らずにやっていきたいと思います。
最後に一言...冒頭の私、今の私とは別人でびっくりしました。
