AtCoderで黄色になった感想 - Programming Coontest

はじめに

はじめましての方ははじめまして，そうでない方はこんにちは．競プロをやっております，はちじです．

さて，私はちじは，先日10月1日に開催された京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271) にて，AtCoder黄色になりました！

THE ACHIVER - RATING 2000 -

AtCoder で黄色になりました！！！！！ pic.twitter.com/Z7M7mOWAJ5
— はちじ@競プロ (@sad_eight) 2022年10月1日

そこで，今回はAtCoderで黄色になった感想を書いていきたいと思います．

はじめに
レート推移，解いた問題数などのデータ
黄色になるまでに得たアルゴリズム，知識など
青になってから黄色になるまでに心掛けたこと
競プロでのアドバイス
おわりに

レート推移，解いた問題数などのデータ

レート推移，解いた問題数などのデータ（2022/10/15現在）は，以下のようになっています*1．

追記：精進グラフの表示が正しくないとの指摘を受け，精進グラフを差し替えしました．

黄色になるまでに得たアルゴリズム，知識など

以下には，黄色になるまでに得たアルゴリズムや知識の中で，特に最近重要そうに感じたものの一部を挙げていきます．基本的には，ここに挙げているのは青になってから得たアルゴリズムや知識などがほとんどだと思いますが，一部青になるまでに得たアルゴリズムの中で，より理解が深まったものを挙げてもいます．いちいち全部言っていたらきりがないので，配列の二分探索やしゃくとり法，Union-Findやナップサック問題で使うDPなどの，簡単な問題でもよく登場するようなアルゴリズムについてはここでは挙げません．

数学関連

Smallest Prime Factorを用いた，高速な素因数分解

水色のときから存在じたいは知っていたのですが，ちゃんとは理解しておらず，ABCにそれを応用する問題が解けなかった際に悲しい気持ちになったことを覚えています．

問題例：

ABC177-E：高速素因数分解の基本問題です．
ABC227-G：解けませんでした．高速素因数分解の理解が甘かったことを思い知らされます．
yukicoder No.1665：ゲーム問題との融合です．なかなかに面白い問題と思います．

Lucasの定理

競プロをやっていてもたまに出てくる気がしますが，完全に覚えてはないです......．「二項係数の値を求める際に，modを取る必要があるときに使う定理」というくらいの認識でいます．

問題例：

ARC117-C：AtCoderではこの問題が記憶に新しいのですが，この問題に関してはどちらかと言うとそこに帰着させるまでのステップがかなり難しいと思います．

オイラーの定理・フェルマーの小定理・トーシェント関数

整数問題なんかでは最近のABCでもけっこう登場しているような気がします．以前ABCで出題されたときに，全然理解していなかったことがわかって呆然としました．流石にヤバいと思ってある程度履修し，今では問題を解くときにある程度道具として使えるようになっていると思います．

問題例：

ABC228-E：フェルマーの小定理の基本を問う良問ですが，何箇所か罠があるので要注意です．
yukicoder No.1140：フェルマーの小定理を「ちゃんと」理解しているかが問われます．
ABC212-G：「原始根」に関する理解が問われます．それについての理解を深めるにはすごく良い問題だろうと思います．ちなみに，その後には数え上げパートが控えているのですが，その数え上げパートも普通に難しいです．
ABC222-G：オイラーの定理，またトーシェント関数に関する理解が問われます．ちゃんと理解していないと解くのは難しいと思います．

カタラン数

意外と知識として出題されるんだなぁというのを，最近感じました．カタラン数には様々な解釈があるため，今後どのように問われるかもわからないので，しっかり解釈とともに身に着けていきたいところ．

問題例：

ABC205-E：カタラン数の「導出」部分が問われる良問です．
ARC145-C：こちらは逆に，考察要素がかなり強いです．考察を行う仮定で数え上げ部分にしれっとカタラン数が登場したりするので，「知識として問われるんだ......」という感想がかなり強かったです．

データ構造関連

Binary Indexed Tree（BIT）

今まで一点更新，区間和計算のクエリに答える場合はSegment Treeを用いていたため，BITの出番は全くと言っていいほどなかったのですが，さすがに青コーダーにもなってこれが書けないのはマズイだろうと思い，原理と実装について履修してみることにしました．実際にわかったこととしては，「実装は思っていたよりもはるかに簡単だったが，その原理は思った以上に巧いbit演算を用いていた」ということでした．一応ACLにもfenwick_treeとして実装されてはあるようなので，今後はそれを使うことになるかとは思いますが，実装も知っておいて良かったなという気持ちでいます．

遅延評価セグメントツリー

基本的にはACLを使うことにしているのですが，遅延セグ木に変なものを乗せるときの扱いがいまだに慣れません......．この点については，強い方も「慣れていくしかない」とのことだったので，やはりそうなのでしょうか......．

問題例：

ABL-E：こういう変なものを乗せる遅延セグ木の扱いはいまだに慣れません．

bitset64倍高速化

コンテストでもたまに見る気がします．ただ，C++のbitsetの仕様を覚えておらず，まだスムーズに書けはしないのでちゃんと書けるようにしたいもの......

問題例：

典型059：bitset64倍高速化を初めて知ったのは，この問題でした．ただ，この問題は若干実装が難しいような気もしています．
ABC258-G：bitset64倍高速化の基本です．本番でこれが見えなかったのは大反省案件．
ABC260-F：想定解はbitset64倍高速化ではないのですが，これなんかもbitset64倍高速化で解けたりするらしい......？
AGC020-C：個人的に，bitset64倍高速化はこういう部分和問題のDPで見ることが多いような気がしています．

文字列アルゴリズム関連

ローリングハッシュ

基本的に，文字列アルゴリズムはこれが最重要だと思っています．ローリングハッシュじたいの存在は青になる少し前から知っていたのですが，最近「ローリングハッシュだと信じ込んでいたアルゴリズム」が実はローリングハッシュではない（一応正しい結果は返すものの，計算量が $O(N \log mod)$ のものだった*2）ということが判明して唖然としました．今では正しくローリングハッシュが書けるようになっています．

また，ハッシュの衝突を意識しないといけない場面に遭遇しました．具体的には，比較対象が1つだけであればほぼ確実に判定できるのですが，比較対象が多いとき（文字列 $T$ が，文字列 $S_1, S_2, ..., S_N$ のどれか一つと一致しているかを判定する，など）の場合は，かなりの高確率で衝突してしまう，ということが起こってしまいます（誕生日攻撃）．この回避方法の一つとしてはmodの値を大きくする（どうやら $2^{61}-1$ が安全なmodらしい？）というのも手のようですが，個人的に一番楽で手っ取り早いと思ったのは，「複数のmodを用意する」でした．

問題例：

典型047：ローリングハッシュの基本問題です．ただ，文字列を対応させる手間があり，ちょっと実装が大変です．
yukicoder No. 2102：実際に誕生日攻撃に遭い，悲しい気持ちになりました......．

Z-Algorithm

すごく賢いアルゴリズムだなぁという印象でした．ACLにあるので，コンテスト中はそれを使うのが良いように思います．意外と昔の問題でも登場していたりするなぁという感想です．

問題例：

ABC141-E：Z-Algorithmの基本問題．
ARC055-C：工夫が必要な文字列判定の問題．Z-Algorithmがすごく役に立ちます．

Manacherのアルゴリズム

文字列の全ての文字に対して，その点からの回文半径を全体で $O(N)$ で求めるアルゴリズムではありますが，これはローリングハッシュと二分探索を組み合わせることで $O(N \log N)$ で求めることができてしまうため，もしかするとあまり使いどころが少ないように思うかもしれません．しかし，知っておいて確実に損はないように思われます．

動的計画法関連

個数制限つき部分和問題

蟻本にあったので履修しました．たまに実際のコンテストでも使える場面があるように思います．

問題例：

QUPC2018-B：想定解は貪欲のようですが，範囲を絞って部分和問題に帰着させると嘘貪欲にハマらず確実に通せます．

部分列DP

すごく賢いアルゴリズムで，ABCでも何回か出題されたのを覚えています．

問題例：

ABC214-F：部分列DPを少し工夫すれば，通すことができます．
ABC230-F：こちらは部分列DPに帰着させるところが難しく，また値の種類数も多いため，先ほどの問題と同じようにやっていてはTLEしてしまうのですが，累積和もうまく活用することで通すことができるでしょう．

期待値DP

AtCoderやyukicoderなんかでも出題が多いように思います．基本的に「最終状態を0として，そこから逆算して考える」ということを徹底してやるのが良いように思います．

問題例：

ABC263-E：期待値DPの基本問題．愚直に更新をすると計算量が足りず，累積和の工夫が要るので，少し難しいです．
EDPC-J：「期待値DPっぽいなぁ」とはすぐにわかると思うのですが，どのような形でDPテーブルを作るかがこの問題の山場と思っています．
M-SOLUTIONS2019-C：直接的に期待値DPをしてしまうと計算量的にアウトなのですが，考察の助けになる，というタイプの問題です．

円環DP

正式な用語かはわからないのですが，勝手にこのように呼んでいます．要は「円環状にDPの遷移がある場合，まず円環をどこかで切って直線状に見立て，切った箇所で改めて帳尻を合わせるようにするとうまくいく」というものです．最近のABCでよく出題されていますね．

問題例：

ABC229-F：本番では解けませんでした．「円環部分がある」→「その部分でDPをする」と持ってくることができるかどうかがけっこうカギになるような気はします．
ABC251-E：ABC229-Fより簡単だと思います．

全方位木DP

一度履修し，1問だけ通したことがあるのですが，非常に実装が大変だったことをよく覚えています．全方位木DPをコンテスト中に使いこなせるようになるためには，まだまだ時間がかかりそうです......．

二乗の木DP

原理だけうっすらと履修したのですが，計算量解析が面白かったように思います．考えてみればこの計算量になることは確かにわかるのですが，あまりにも非自明すぎる計算量解析のように思います．ただ，まだ実戦の場では使えていません*3．

グラフ関連（基本的なグラフの探索など）

オイラーツアー

「木をDFSの行きがけ順（または帰りがけ順）に訪れ，その番号を順番に記録してやる」という考え方で，木を考える問題なんかではけっこう役に立ったりする印象です．ABCでも割と汎用性がよく使われるなぁという印象です．

問題例：

ABC202-E：木の子孫すべての頂点を見たい場合に，それを「区間」として扱いたい，そのような場合にオイラーツアーは役に立ちます．この問題は，まさしくその好例と言えるでしょうか．
ABC240-E：これも木の「区間」にまつわる問題！
ABC244-G：構築問題であり，そこそこの考察要素が要るので，オイラーツアーと気づくのも少し難しいかもしれませんが，「グラフを訪れた順に頂点番号を記録する」というところからオイラーツアーが連想できれば......という気持ちです．

なもりグラフ/Functional Graph

個人的に，グラフの中でも特に扱いの苦手なものだと思います．なかなか実装に慣れていないからだとは思うのですが......．

問題例：

ABC256-E：実装方法がわからなかったため本番で通せず，本当に衝撃を受けた記憶があります．
ABC266-F：なもりグラフの基本問題と言うべき問題です．実装方法は，インターネット上の記事を参考にしました．

最小共通祖先問題（LCA）

実際にLCAを使って問題を解いたことは，あまり多くはないのですが，スムーズに出来ていると便利なことがあるかなぁという感想です．方法としては，2頂点の深さをそろえてから，ダブリングと二分探索を用いることで求める方法と，上記のオイラーツアーで木をDFSの行きがけ順にたどった後でセグメントツリーを用いる方法の主に2通りが考えられるのですが，個人的には後者のほうが好みです．

問題例：

ABC267-F：LCAは直接的に出てこないのですが，LCAの考え方を知っていれば，ダブリングをすることには気づきやすいかもしれません．

ダブリング

LCAに関連して．個人的に，このアルゴリズムは青になってから確実に書けるようになり，成長を感じたものの一つだと思っています．周期を考える問題は今まで実装が大変だと思いながら周期を数えていたのですが，今ではダブリングで楽をするようにもなりました．

問題例：

ABC258-E：なかなかに実装が大変です．

グラフ関連（最短経路関連）

01BFS

書き方を覚えました．今まではダイクストラのライブラリを貼ることでサボっていた場面も多かったですが，それだと今後計算量が流石にしんどい点も出てくるかもしれないと思い，dequeを利用した01BFSの実装を覚えることにしました．

問題例：

ABC213-E：01BFSの基本問題．
ABC246-E：愚直にやっては間に合わないところを，上手いこと頂点を拡張することで辺の数を削減することができるかどうかがカギと思います．
yukicoder No.2096：自作の問題です．難易度は高めで，実装量も多めだとは思いますが是非，解こう！

ベルマン・フォード法

ベルマン・フォード法は，アルゴリズムこそ単純ですが，意外と実装がしんどいというのが書いてみてわかりました．また，このアルゴリズムは注意しないといけない点があり，それが「答えに関係のない閉路があった場合に，それをどう処理するか」という点です．これの処理で嘘を書かないよう，あらかじめライブラリを作っておくことにしましたが，それ以来このアルゴリズムを直接的に使うことはできておらず......．

問題例：

ABC137-E：ベルマン・フォード法の基本問題ですが，「答えに関係のない閉路の処理をどうするか」という点で難しいです．
ABC271-E：直接ベルマン・フォード法......というわけではないものの，ベルマン・フォード法の「お気持ち」がわかっているかどうかがすごく大事なように思います．

グラフ関連（フロー関連）

最小費用流

これは基本的にACLに頼っているのですが，ACLの最小費用流のmin_cost_slopeという関数の仕様に罠があるということに気づいておらず，痛い目をみたことがありました．*4

問題例：

ABC247-G：ACLのmin_cost_slopeの仕様を正しく理解しておらず，痛い目に遭いました......．

燃やす埋める問題

二部グラフのときに片方を反転するところまで含めて，最小カットに帰着させることによって解けることは知っているのですが，実際にどのように使うかについてはまだ自信がありません．引き続き，問題を解いていくことを通じて，より理解を深めたいです．

問題例：

ABC193-F：二部グラフをなしているため，片方を反転して燃やす埋めるの形に帰着させる，ということを知っているかどうかが大きいように思われます．

最小カット

最小カットを最大流に帰着させて解く，というのもよく出題されるように思います．

問題例：

ARC074-D：「辺のカット」ではなく，「頂点のカット」なので，どういう辺の張り方をするかが試されます．
ABC239-G：同じく「頂点のカット」なのですが，こちらは復元つきです．どうやって最小カットを復元するのかがこの問題の最大の壁である気がします．残余グラフについての知識が要求され，なかなかに教育度が高いです．

クエリ問題など

Mo's Algorithm

これもすごく賢いアルゴリズムのように思えます．最近もABCで出たのですが，経験がなくて書けず，痛い目をみたのを覚えています．一度書けるようにしたので原理はわかっているのですが，実装がすぐにはできる自信がない......

問題例：

ABC242-G
ABC174-F：これなんかもMo's Algorithmで通せますね！

平方分割

これはまだ使える気がしないのですが，「2つの解法が考えられ，その双方で効率の良さが異なる場合に，そのサイズの大きさが $O(\sqrt(N))$ 以上か，それより小さいかで扱いを変えるようにする」というのが多いのではないかと思っています．

問題例：

ABC259-Ex：個人的に，すごく綺麗に平方分割を使っている印象で，最近の問題の中ではすごく好きな部類に入ります．
yukicoder No.1312：これなんかも，言ってしまえばある種の「平方分割」？

整数計画問題

整数計画問題に関しては，競プロのアルゴリズム部門に登場した際に大事なことは「整数計画問題を定数時間で効率的に解こうとしてもうまくはいかない」*5ということをちゃんと感覚として持っているかどうかだと思いました．ARCで整数計画問題が出題された当初，そのことを知らなかった私はとにかく上手く解こうと $O(1)$ で解く方法を考えたのですが，当然うまくいくわけもありませんでした．このような問題に出会ったときは，「もし解けるんだとしたら全探索とかしかない，ただ，その全探索をうまく工夫して探索範囲を減らすことがこの問題の肝である」というように考えられるかどうかが大事なように思いました．「うまく工夫する」方法は色々あるとは思いますが，全探索の方法を複数考えてから，先述の平方分割などを適用する，というものが多いように感じます．

問題例：

ARC139-B：整数計画問題を定数時間で解こうとしたところ破滅した記憶を鮮明に覚えています．
ARC150-B：ARC139-Bの記憶がよみがえったからか，割とすぐに解法を思いつけました．
yukicoder No.2099：これも3変数の整数計画問題と言えます．注目する変数が重要だと思います．

半分全列挙

これも，言うなれば広義の「平方分割」と言えるでしょう．このアルゴリズムじたいは水色のときから知っていたのですが， $O(N2^N)$ から $O(2^N)$ に落とす方法を学びました*6．計算量が大きいときなどに，たま～に役に立ったりします．

問題例：

東京海上日動2020-D：半分全列挙なのですがTLがかなり厳しいため，計算量の落とし方が役に立ちます．
ABC271-F：黄色になった回のコンテストで最後に通した問題が，半分全列挙を使う問題だったため，個人的に思い入れのあるアルゴリズムになりました．
yukicoder No.1929：一見すると半分全列挙に見えにくい制約，見た目をしています．こういうのは落ち着いて計算量を睨むことが大事になりそうです．

平面走査

まだあまりよくはわかっていないのですが，一番基本となる考え方くらいはわかってきたような気もします．考え方的にはいわゆる「尺取り法」に近いものを感じますが，xy平面においてx軸方向に見ていく中で，y軸の値を管理するようなイメージでいます．

問題例：

ABC215-F：こういう問題が「平面走査」に当てはまるのかなという認識でいます．

その他，考察テクニックなど

隣接swapの条件を考える貪欲法

2つの要素のどちらを先に選んだほうが良いのかを考え，それを式で表すことで，貪欲法の条件を考える問題です．

問題例：

-yukicoder No.2008：B問題なのに全然解けずに痛い目を見ました．*7

-ABC268-F：yukicoderでの経験が生きたのか，のちにABCで出題されたときには解くことができました．

逆から条件を考えると見通しが良くなる問題

私が競プロを始めたばかりの頃のABCで出題されて，その当時は全く歯が立たなかったのですが，青になって以来こういうのがけっこう解けるようになってきました．最近のABCでも割と見かける気がします．

問題例：

-ABC137-D：当時全く歯が立ちませんでした．ABC-Dにしてはなかなか難しいとは思います．

-ABC249-F：気持ちとしてはABC137-Dに近い？優先度付きキューを使ってシミュレーションするところも似ている気がします．

-ABC252-F：蟻本で同じような問題がそのまま出たらしいです．

何かを決め打って二分探索をすると見通しが良くなる問題

これは水色まででもたくさん出会っており，ABCにも昔も今も変わらず高い頻度で出題されている超重要問題なのですが，青色になってからこの解法を見抜ける率がかなり高くなったように感じられます．決め打ち二分探索以外に解法がないようなタイプの問題も出されているというのはもちろんですが，最近では「一見すると愚直にやりたい見た目をしており，実際愚直でもできなくはない（ただし考察も実装も大変になる）が，そこで一歩踏みとどまって二分探索に気づけるとかなり楽ができる」というのがまさにトレンドになっていそうな気がします．最近のコンテストではかなり早い段階でこれに気づくことが出来ており，成長を感じられて嬉しいです．

問題例：

典型001：典型90問の一番最初に登場した問題ということで，記憶に鮮明に残っているという人も多いのではないでしょうか．
ABC107-D/ARC101-B：決め打ち二分探索＋累積和＋セグメントツリーという，典型詰め合わせ的な問題であり，個人的にもかなり好きな問題です．
ABC236-E：決め打ち二分探索のザ・典型問題．
ABC270-E：一見愚直に解きたくなる見た目をしていますが，ここで踏みとどまって二分探索をすることに気づければだいぶ実装も楽になります．
ABC271-C：これも，愚直でも解けないことはないのですが，C問題にしてはかなり大変．決め打ち二分探索に気づければ考察も実装もかなり素直になってくれます．

非自明な計算量解析に気を付ける

要するに，「一見するとループが3個あるので計算量が $O(N^3)$ あるように見えるが，実は探索範囲を考えると $O(N^2)$ になっている，というようなものです．ABCなどでもたまに見かけるような気がします．先述の「二乗の木DP」に関してもこれの類といえます．

問題例：

ABC234-F：公式解説に詳しく載っています．
yukicoder No.2076：自作の問題です．やや難しめです．

主客転倒

ちょうど私が青になったくらいの時期にABCで流行っていた時期がありましたが，割と意識すると解ける問題の幅も増えてくるかもしれません．

問題例：

問題が「有名問題+α」の形をしており，その「有名問題」の部分で使えるアルゴリズムが限定されているようなタイプの問題

これは特にARCやAGCで有効な場面が多いように思えるのですが，「有名問題+α」のような設定の問題であって，その「有名問題」の解き方が限定されているような場合，解法はその有名問題のものを利用することが多いです．「どのような問題はどのようなアルゴリズムを用いて解けるのか」というのを，知識としてしっかりと知っていれば知っているほど有利になるかということであり，まさに「総合力が問われる」ようなタイプの問題に感じられます．先ほどの整数計画問題に関しても，「定数時間では解けず，全探索くらいしか良いアプローチがない」ということを知っているかどうかでだいぶ話が変わってくる点において，これに通ずるところがあるかもしれません．

問題例：

AGC054-B：本番で全然解けなくて悲しい目に遭いました．「部分和問題+α」の形をしているため，この制約下においては部分和問題はDPでしか解けない，ということから解法を絞る，という旨のツイートが流れてきて，「なるほど......」と思った記憶があります．
ARC149-B：求めるものが「LIS+α」の形をしているため，LISをまともに求められるような解法ぐらいしか考えられるものがない，というところから解法が絞れます．

高速デバッグ

これは競プロで使うアルゴリズムや知識の話ではないのですが，主に実装面において非常に助けられたものの話です．デバッグする際に，配列やmapなどの中身を全て出力したいような場合に，そのコードを書くのに時間を取られてしまいます．それを，簡単なフォーマットで全て中身を出力してくれるようにしたい，というのが高速デバッグのモチベーションです．一時期究極的に競プロが伸びない時期があり*8，これは実装で詰まっているのが悪いかもしれない，であればこれを導入してみる価値もあるかもしれない，と思い，導入したところ，効果はてきめんでした．競プロで詰まっている人で，もしこれをまだ導入していないような人がいれば，導入してみることを考えてもよいかもしれません．

参考：競技プログラミングで print デバッグ

総評

このようにして振り返ってみると，青から黄色に上がるにあたり，当然アルゴリズムや知識も身に付いたものは多いのですが，それに加えて「考察力」が確実についていったという印象がありました．競プロの問題を解くには，アルゴリズムや知識を知っていることも当然大事ですが，それだけではなく，それらをどのように組み合わせて実際の問題に対して使うかが非常に重要です．このように考えれば，このような力を，問題演習を通して身に着けていくことが実力の向上につながるのも納得のいくように思えます．

青になってから黄色になるまでに心掛けたこと

「考察」を重視した

青になるまでは，アルゴリズムなどの知識が十分に足りておらず，それがけっこうボトルネックになっていたこともあり，知識を蓄える過程でレートが上がっていった側面が大きかったように思いますが，青になって以降は道具がけっこう整って行ったということもあり，それらをどのように使って行くかという，いわゆる「考察」にも力を入れるようになりました．その結果，いわゆる「典型考察」がどういうものなのかもだんだんとわかってきたような気がします．

「実装」も重視した

知識も知っており，ちゃんと考察できたとしても，「実装」ができなければ意味がありません．競プロは結局「プログラミング」なわけですから，正しくプログラムを実装できなければ全く意味がないわけです．青になってからもしょっちゅう実装で詰まらせることが多く，そのたびにレートを下げて悲しい思いをしてきました．実装力を上げることも，競プロで成長する上では非常に大切です．実装力を上げることは「どうすれば良い」という確実な方法がなく，やはり問題を解いていく過程で慣れていくしかないと個人的には思っています．ただ，次のようなことに注意するだけでもだいぶ変わってくるのではないかと思っています．

新しい問題に出会ったとき，考察が出来たから終わり，などではなく，ちゃんとACを取れるように心がける
実装で詰まった場合は，競プロが強い人の実装を見て，どのように実装すれば簡潔に出来るのかを知る
先述した「高速デバッグ」を取り入れ，デバッグの速度を上げる．デバッグの速度は実装の速度に直結すると思っています．

基本事項の確認に努めた

青まではABCでレートを上げることができます．それゆえ，主に典型が問われるABCにおいて，基本事項が抜けていた，または実装できなかったことによって取れるはずの問題を取れなかった，または時間がかかってしまった，となれば，非常に勿体ないわけです．そのため，基本事項がすぐに出てくるかどうかを確認することは，非常に大切なわけです．確認する方法は色々ありますが，「競プロ典型90問」や「競技プログラミングの鉄則　演習問題集」など，典型を確認する問題セットがありますので，それを埋める過程で確認するというのがおすすめです．分野が偏りますが，特定の分野のみに特化して確認したい場合は，「DPまとめコンテスト」や「AtCoder Library Practice Contest」も良いかもしれません．

競プロでのアドバイス

ここでは，競プロをやっている上でのアドバイスを書いていきます．現在競プロの調子のよい方や，競プロに取り組みたいと思っている方はもちろんのこと，そうでない方の参考にもなれば幸いです．

レートを上げたいなら，コンテストに出よう！

唐突ですが，次のような主張をしてみたいと思います．

コンテストに出なければ，レートは絶対に上がりません．

これは一見当たり前のことを言っているように思えますが，個人的に大事なことだと思っています．「競プロでレートを上げたいときに真っ先に何かしたいなら，何をすれば良いか？」と言われたら，私は「コンテストに出る」と答えます．都合でコンテストに出られないとかであれば話は別ですし，実際私もそのような理由でコンテストに出られないこともありますが，「どうせ冷えるから今はコンテストには出ないでおこう......」などという理由でコンテストに参加しないようにしようと思っていると，本当にレートを上げることのできるチャンスを逃すことにもなりかねず，非常に勿体ないと思います．*9

もちろん，レートが下がることもあるだろうと思います．実際，とんでもない冷えを繰り返してしんどかった時期もあったりしました．しかし，そうそう実力が下がったということではないと思っています．一回のコンテストで出題される分野にはどうしても偏りが生じてしまうもので，それと自分の問題の相性を鑑みたときに，一回のコンテストだけで見れば失敗に転んでしまうこともどうしても生じてきます．そのような際に，「次に頑張ればいい」と思えるかどうかが大事になってくるとは思います．

ただし，無理だけはしないようにしましょう．気をもんでしまって日常生活に支障がでてしまうと大変です．*10本当に難しいことではありますが，自分なりに競プロとのうまい向き合い方を模索することが大事なのだろうなぁという気持ちです．

作問，しよう！

最近私は競プロの作問をやるようになりました．今までは競プロの問題を解くだけだったのですが，青になったところで，これだけ実力がついてきたということで，自分で問題を作ってみよう，と思ったところ，意外と楽しいことに気づき，それ以来不定期で作問を行っています．競プロでの作問プラットフォームには様々ありますが，yukicoderが一番使いやすいと思います．yukicoderでは毎週金曜日に有志が作問した問題によってつくられたコンテストが開催され，毎回100～150人程度がコンテストに参加しています．yukicoderのシステムが作問には非常に使いやすく，ローカルにRime*11さえ入れていれば作問するには十分でしょう．

作問をすることで，問題の解法に向き合う時間が長くなり，その理解がより深まる，ということがあるように感じます．そのため，意外と競プロの作問をすることで新たに学ぶことも多いんじゃないかなというのが私の意見です．

競プロを楽しもう！

競プロはとにかく楽しむことが大事です．楽しんでくれる人が多いと，私はとても嬉しいです！

おわりに

私は3年前の夏に，その当時にやっていた友人に触発されて競プロを始めました．当初，私はプログラミングのプの字も知らず，for文とかif文とかを学んだ覚えがあります．その当時，友人はABCで4完できるくらいの実力があったのですが，私は最初に出たAtCoderのコンテストでなんとA問題1完だけでした．

for文もまともに書けなかった時代ですから，そのような結果になってしまったのも無理はないでしょう．それでも，「問題を解いて競うのって楽しいな」という気持ちは奥底にあり，何だかんだで楽しめる趣味だな，と思い，時間をかけて打ち込もうと思うことにしました．そうして，基本文法を覚えて，ゆっくりではあるものの，緑までは進むことができました．

そして，周りの人は着実に成長を重ね，青や黄色になる人が現れていきました．そんな中，私は緑や水色などで長い間停滞しており，私の中では焦りが生まれていました．思えば，周りで黄色以上になっている人の多くは，すぐに灰色や茶色，緑を突破しています*12．chokudaiさん*13のツイートでも，このような言及がなされていました．

２ヶ月で茶色だとすると、平均するなら、緑半年、黄色１年、青２～３年ですかねー？黄色は結構厳しいかと。
ただこの辺はどれくらい頑張るかとかそもそも続くかとかにもよるので、別に茶色に数ヶ月かかって黄色行ける人ーとかもいるとは思います。
— chokudai(高橋直大)🍆@AtCoder社長 (@chokudai) 2020年7月11日

実際，私がAtCoderを始めてから各色になるまでにかかった時間は，茶色まで約2か月半，緑まで約5か月，水色まで約1年1か月，青まで約2年1か月であり，上のツイートとほぼ一致します．そんな私には，「黄色は厳しいかも」という現実が間接的に言い渡されてしまっており，ショックでした．

それでも，私が暖色コーダーになれる日はいつか来るはずだ，と思って精進を重ねました．レートを上げてもすぐ下がるときや，レートがどんどん下がり続ける時期もあり，しんどい思いをした日もありました．それでも諦めずに，「目指せ黄色」と信じ続け，ついにこのように黄色コーダーになることができました！自分のユーザーネームが黄色くなった瞬間は，とても嬉しかったです．

最初の成長が周りと比べて遅かったとしても努力次第で暖色コーダーになれることをこのような形で証明できました．この記事を読んでくださっている方で，周りと比べて低いレートで伸び悩んでいる方もいるかもしれませんが，そのような方も，レートを上げたいという気持ちがあればぜひとも諦めずに続けてほしいと心から強く思っています．

競プロは個人的に大事な趣味の一つということもあり，まだまだ続けるつもりではありますが，これ以上実力を上げることができるかどうかはまだまだわかりません．今後は問題を解く側のみではなく，作る側としても楽しもうと考えています．また，今まで全然行けていなかった競プロ系のイベントなんかにも是非積極的に参加したいものですね*14．

最後に，この記事を読んでくださった皆さんが競プロを楽しんでいただければ，私はとても嬉しいです．

それでは．また次の記事でお会いしましょう．

*1:精進グラフは， AtcoderDevotionGraph をユーザースクリプトとしてインストールして表示させましょう

*2:差分計算に掛け算を用いるべきところで割り算を用いてしまっており，逆元の計算に $O(\log mod)$ かかってしまっているのが原因です．

*3:ちなみに，AGC058-Bを見て，問題設定から一瞬二乗の木DPを疑いかけたのですが，見事に嘘でした．

*4:この仕様については，最小費用流のアルゴリズムであるプライマル・デュアル法を考えれば自然な仕様になっているのですが，それが影響して，問題を解く上では不都合が生じることがあります．

*5:整数計画問題はNP困難のクラスに属することがわかっています．

*6:AtCoder Beginner Contest 184 F - Programming Contest 解説 (おまけ: 半分全列挙高速化について) - Growth Record of Lettuce Farm

*7:ちなみに，この問題は難易度も当初は★1.5に指定されていたのですが，のちの投票で★2.5に修正されていたりします．

*8:その当時，レートのHighestが1844だったのですが，一気に1625まで落ちてしまい，もう少し落ちていれば水色になってしまう，というところまで来てしまい，大変に落ちこんでしままっていました．

*9:かくいう私も最近はCodeforcesのコンテストには出ていないので人のことは言えない気もしますが......あのコンテストは夜遅いのが悪い......

*10:私自身も，大冷えしたときに，競プロと将来のことが頭から離れずに朝の6時まで寝られなかったことがあり，その後が非常にしんどかったです．それだけ競プロにかけてきたものが大きいのだとは思いますが，後から思い返すとすごく衝撃的な出来事だったんだなぁというように思いました．

*11:競プロの作問を支援するツールです．

*12:これに関しては，プログラミングの経験がある程度あってから競プロを始めた人や，そもそも競プロ経験があってからAtCoderを始めた人も含まれるため，あまり信用ならない要素もあるのですが......

*13:AtCoder株式会社の社長である，髙橋直大さんのことです．

*14:ちょうどTTPCのオンサイトに参加する予定です．また，競プロ忘年会が開催されたら是非行きたいと思います．