競プロ日記002: ABC270とMM140とAHC014

ABC参加3回目

この1週間は前半MM140，後半AHC014ということで大変ハードでしたが，こういうのはとにかく続けないとダメなのでトヨタ自動車プログラミングコンテスト2022(ABC270)に強行参加しました．

今回はABCと3問解いて残り時間が1時間ちょい，あと1～2問解けるかなーと思っていましたが，いろいろとダメで結局Dをやっているうちに時間切れになりました．前回より正答数が少なかったけど，まだ3回目ということでレーティングは順調に上がっています．

Dは貪欲→WA，うーん全探索→TLEという典型的な失敗を順当に経た後，メモ化かなーとかやっているうちに時間切れになりました．1時間もあってなんで時間切れかというと，貪欲解法のときに「あれ，lower_boundってどんな使用だっけ？」となって30分くらい調べてました^^;翌朝メモ化再帰版が通りました．解説とかTwitterのタイムラインではDPという説明が多くてそれはよくわかるんですが，自分の基本的なアプローチが「貪欲→全探索→メモ化」というステップになりがちなので，これを「あっ，これ競プロ本で見たやつだ！DP！DP！」という感じにならんとスピードアップが難しいかも．

とはいえ，あまり無理な勉強をすると長続きしないと思うので，基本ABC用の勉強はナシ．とにかく実戦経験を積む．解きかけの問題があった場合のみ次の日に最後までやる程度にしようと思います．