今週の競プロ活動振り返り ABCとかアルゴ式とか

今週の競プロ活動を振り返ります。前回の記事を見ると今週の目標として以下を挙げていました。

ABC参加
難易度Easyの問題を10問解く。
アルゴ式のグラフアルゴリズムの章(1,2章)を受講する。 algo-method.com
先週、今週のC問題に挑戦 C - Path Graph? C - Don’t be cycle

これを踏まえて今週の進捗です。

今週の進捗

今週の進捗

ABC参加
難易度Easyの問題を10問解く
アルゴ式のグラフアルゴリズムの章(1,2章)を受講する

「先週、今週のC問題に再挑戦」のみ未達でした。これはアルゴ式の1,2章レベルの知識だと、これらの問題に挑むのに十分でなかったことに起因します。
ということで、一個一個振り返ります。

ABC参加

今回の成績です。575パフォ、レートは微増。相変わらず茶色最底辺、気を抜けばすぐ灰色に落ちる危険水準です。

atcoder.jp.

3完できたものの、BC問題に時間がかかってしまったのでそこまでパフォが出ませんでした。B問題については問題文からグラフを使うことが想定されている問題であることは分かったものの、かといってどうやって実装すればいいのか分かりませんでした。仕方なくstackを使ってシンプルに実装。解説にもUnionFindとかBFSとかグラフに関連するワードが出てきます。まさかBで出てくるとは思いませんでしたが、やはりグラフアルゴリズムの優先度をあげて勉強する方針は間違ってなさそうです。
C問題についてはbit全探索を使う問題なのは分かったのですが、bit全探索の実装方法が分かりませんでした。ネットでサンプルのコード例が上がってたのでそれをいい感じに組み込んでなんとかAC。理解できていないのであまり良くないACですね。これも未修のアルゴリズムですがかなり汎用性が高そうで、学習の優先度は高そうです。
D問題はDP。問題文を見て「あ、これDPだな」と分かるには分かるのですが、これもCと同様にどう実装すれば良いか分かりません。もちろんDPも必修分野なので勉強する必要はありますが、先述の通り、一旦はグラフに集中したいと思います。

難易度Easyの問題を10問解く

これは平日だけで達成できた気がします。会社の昼休みとか、作業できない待ち時間とか、退勤後とかにちょこちょこやってました。自分にとってのEasy問題は灰色の中でも低〜中難易度の問題なので、そこまで頭を使うことなくサクサクと実装できます。(たまに詰まる問題は出てくるけど)　とりあえず灰diff埋め、A,B問題早解きのためにもこれは続けていこうと思います。

アルゴ式グラフアルゴリズム1, 2章

初めてアルゴ式をやってみたのですが、なかなか良かったです。サイトのページは教科書、練習問題の2つに分かれていて、教科書を読んで理論を覚えたら早速実践することができます。1,2章の段階ではグラフとは何か、根付き木とは何かといったグラフアルゴリズムの基本的な用語や、それに関連した比較的簡単な問題が用意されています。教科書をしっかり読んで考えればそこまで詰まらずにACできるレベルの難易度です。ただ、根付き木の巡回で再帰する処理が出てきて、再帰が苦手な自分には処理の流れをイメージすることが難しかったです。まあ徐々に慣れてきたし、この辺りは慣れもあると思うのでひたすら問題を解くしかなさそうです。あと、競プロやってる人ってこういう巡回系のアルゴリズムはテンプレート用意してたりするイメージがあります。ああいうのを理解して用意できるようになったらグラフ系の問題とも戦えそうです。