競プロ楽しすぎる
近況報告 - 競プロ楽しすぎ
入茶しました！
ABC462
ABC462は c++ / 競プロを始めて2回めのコンテストでした！ なんと、水色perf（1325）を出すことができました！嬉しい！！ 特に、E問題がO(1)解法のあるモロ数学のような問題だったので、するりと解くことができました。 逆に、D問題はめちゃめちゃ難しく感じたのに、茶色diffでレベルの高さを感じました。 えぇ、T - Dを考えるのってそんなに簡単ですか？典型だったりするのかな...。 とにかく、みんなすごい。
プランを練る
さて、本格的にレートを上げていくために、今後の精進の方法を綿密に練っていく必要があります。 そこでまずは、何ができれば各色に到達できるのかを知ることにしました。 当面の具体的な目標として、「Dまでの速解きをこなしてEをじっくり考えて解ききる」というものを設定しました。 これは、水色perfを安定して出すための基準の一つだと思います。 そして、それが達成できたら「Eまでの速解きをこなしてFをじっくり考えて解ききる」を目指すことにしたいと思います。
これを達成するために何が必要かを探るために、いくらかのABCの過去問をセット形式でAからDまで解く練習をしてみました。 （後にこれは完全に正しくないと判明するわけですが）圧倒的にアウトプットの量が足りないということが発覚しました。 （まだ始めて1週間とちょっとでしたから当然と言えば当然ですが）典型90などで知識を入れるだけ入れてアウトプットが全然できていなかったのです。 ということで、ABCの過去問を引き続き解いて行くことにしました。
精進
ABCの過去問を解き進めていくのと並行して典型90の星5の問題も解いていました。 この期間に新たに習得した技術は、バックトラックを活用した再帰関数の実装、上手な前計算、強連結成分分解、再帰DFS、ラムダ式、汎用セグメント木、汎用遅延セグメント木、エラトステネスの篩、DP復元、最長増加部分列の長さを求める、復元するアルゴリズム、主客転倒、マージテク、クラスカル法、形式的冪級数、ワーシャルフロイド法、bit DP、番兵、枝刈りを活用した全探索などです。
典型90の星5、意外と自力でも解けることに気が付きました。セグメント木などの強い道具を使うやつは明らかに厳しいですが、今までの知識の組み合わせで解けるやつはスムーズに行けました。 087はとてもおもしろかったです。 また、主客転倒など、競技数学で培った考えが活きていると感じました。
自分の課題は本当にスピードで、実際、時間(と前提知識)があればdiff1600以下のFは解けうることが判明しました。 考察力は数学科としてなんとか頑張りたいものです。
入茶（ABC463）
ABC463で入茶できました！ perfは水色(1274)で、ratingは茶色(582)でした。緑色くらいまでならすぐに到達できそうです。 目標は、この勢いを絶やさずに水色に到達することです。
今回は、C問題までは12分と非常に良いペースで解き進めることができました。 D問題も、答えで二部探索するという方針はすぐに見えたもののそこからの実装で70分ほど消費してしまいました。 悔しい...。どうやら、この実装パートは区間スケジューリングという典型的な手法だったらしく、ここに来て知識不足が発覚しました。 今まで過去問を解いている感じ、知識は足りているかなと思いましたがまだまだ不足していそうです。 考察すれば解けるが時間がかかるという状況は理想的ではありません。 ぜひ、脳内でパッケージ化(?)して迅速にコーディングできるようにしたいです。 E問題は、ダイクストラに一工夫するだけで6分ほどで終わりました。 MLEを食らったのは人生初めてだったので、焦りましたが、簡単に解消できてよかったです。
ということで、今後の精進の方針を修正していきたいと思います。 典型アルゴリズムのアウトプットが足りていないことと同時に、まだまだ典型的な知識が不足しているので「方針が思いつかないなら迅速に解答を見てACする」という方針にします。 これによって、効率的に知らないアルゴリズムを学習していき、またしっかりと解説ACをすることでアウトプットに機会も担保していきたいです。 とにかく、最速でDまでの速解きができる状態を作り出したいものです。 あとは、ぼちぼちFに耐えうる知識も習得していきたい。