2022/04/23(ABC249)、重い腰を上げてAtcoderを始めて、05/28のABC253(5回目の参加)で水色、06/26のARC143(10回目)で青になったので一応記事を書きます。
どうして今更
- 昔Project Eulerをやってて、300問くらい解いた
- AtCoderの存在は知ってたが、4問時代は全問正解しても、その中の速さで決まってたのを見て、(のんびりやりたいタイプなので)あんまりやりたくならなかった
- 最近見たら、いつの間にか8問になってて、全問正解までの時間より純粋に解ける数が重視されるようになってたのでやってみることにした(しかも毎週あるABCで2000まで上がれる)
- cargo-atcoderやcargo-competeのようなツールが充実していて、安全で、高速なRustを使ってやってみたかった
- コンパイル有りなのでCEで済む場合がある、てきとうに書いててもCのように危険な落とし穴を踏みづらい。型が強力で抽象化しやすい。
練習方法
一応ProjectEulerからの転生組なのであんまり参考にしないほうがいいかもしれないけど、私のやり方
-
解けることがわかっているクラス(300以下など)はあんまりやらない
- 他の人はたくさん埋めたりStreakを稼いだりしているけど、飽きっぽくてめんどくさがりな私には向いてなさそうだと思った。
-
解けるけどちょっと時間がかかる問題の方針を速く立てることを重視して、問題を見て方針が思いつかなかったら解説を見るトレーニングをやる
- これに使うのは典型の多いとされるABCがよい。ARC以降は考察ウェイトが多くネタバレが致命的かもしれないので、後の練習に取っておいたほうが良さそう？
- とりあえずはコーディング速度を上げるよりこっちのほうが楽そうだと考えた。
- 難易度を見積もるのが早くなると、前から順にABCDEF(2000)ではなくABCD+(EorF)+(GorEx)(2100)、というふうな選択肢ができる上に点数有利な目標ができる
-
たまにライブラリ整備兼ねてAtcoder ProblemsのRecommendationのModelate,Difficultを適当にバチャコン化して解いてみる
- 解説を読んだらその問題は寝かせて、後日再挑戦する
-
ちなみに、私は持ち込みライブラリがないと時間内に正しく実装できないタイプなので、整備は時間外にやってる
-
作ったライブラリ
- (関数を渡しての)二分探索。答えを決めて二分探索とかに重宝する。
- LazySegTree(抽象化つき, 一番のお気に入り)
- SparseTable
- 座標圧縮
- Union Find (高さを持ってない手抜き)
- Convex-Hull (Monotone Chain)
- グラフアルゴリズムは概ねpetgraphで解けるが、なぜかDinicとか、ベルマンフォードの到達不能な負の閉路を除外したものとかがないので、そこは自分で書いた
- 連立方程式
- 素因数分解, GCD, 拡張ユークリッドなど
-
自分に合った解法を見つける、その上で広げる
- 例えば、解説に公式解説とユーザー解説でニ種類以上の解法が載ってたりする。正解は一つではないということ。
- ぐちゃぐちゃだろうと自力で解ければえらい。その上で他の解法を見ると思考の幅が広がるし、いつか似た問題が出たとき使える考え方が身につく。
- コンテストは短いので、(自分にとっての)難易度の見積もりが重要。(特にA-Dが絶対解けてEFGExから選ぶ場合)得意技が使える問題、不得意な問題を見極められると楽。
- ちなみに私はLazySetTree抽象化による区間クエリはどちらかというと得意技のつもりだったけど、ABC256で区間が2問出たにもかかわらずそれ以外しか解けなかったいうことがある。
- これはどこかの色変記事で見た「想定解で解けるようにしろ」(意訳)に対するカウンター
今後
しばらくはライブラリ整備のために毎回は出ないつもり。今年中に黄色くらいを目標に。