こどふぉ紫/AtCoder水になりました！
0.はじめに
こんにちは、十六夜 龍です。
5月2日にこどふぉで紫に、AtCoderで水色に色変したので記念に色変記事を書きます。（正直言えば1日に2回色変出来たのが嬉しいので書いています）
こどふぉを知らない/やっていないという人への宣伝も兼ねようと思うので是非読んでください。
1.目次
以下の流れで書いていきます。
2.こどふぉで紫になりました！
既に書くのは5回目となりましたが、先日のDashboard - Codeforces Round #638 (Div. 2) - Codeforcesで紫（candidate master）になりました！嬉しいです、こどふぉ最高です！
紫、素敵な色です。
Codeforces Performanceというスクリプトを用いることでこどふぉでもパフォーマンス推定値を確認できます。
僕のコンテストごとの結果は以下のようになっています。
実は紫パフォはとったことがありません。
直近2回が運よく相性の良い問題だったので紫になれましたが、まだ紫適正の実力を持っているとは言い切れません。
安定して紫パフォをとれるように精進します。
ここから少しこどふぉの宣伝に入ります。既にこどふぉをやっている方は読み飛ばしていただいても構いません。
以下、Q&A方式で説明します。
・「こどふぉ」とは？
Codeforcesというロシア発祥のコンテストサイトです。AtCoderよりも頻繁にコンテストが開催されています。
・どうしておすすめするの？
AtCoderよりも頻繁に、かつ平日にもコンテストがあるからです。やっぱりコンテストがあるとやる気が上がります。
・こどふぉの特徴は？
レートの変動が大きい、Hackやシステムテストというルールがある、Divという概念がある、などいくつかあります。次の記事が分かりやすくまとまっています。
・こどふぉの欠点は？
たまに問題文が難読の回があること、そして開催時間ががっつり深夜帯と厳しめなことです。これは慣れるか頑張るかしないといけないです。
・どうやって始めればいい？
AtCoderみたいに登録するだけです。いきなりコンテストに参加するのではなく、何問か過去問を解いてみて提出形式など慣れておいたほうが良いです。
とにもかくにもまずはCodeforcesにいってみましょう。
3.AtCoderで水色になりました！
AtCoder Beginner Contest 165 - AtCoderでAtCoder水色コーダーとなりました！
rated/unratedの協議の末、無事ratedになりました。AtCoder最高です！
ABC165は問題文不備で直前に開始時刻が延長されたり、E問題のテストケースに制約外の入力があったり、C問題に緑上位diffの問題が出たり、逆にD問題は茶下位diffだったりと色々ありました。
コンテスト終了後、コンテスト時間よりも長く調査・協議してくださったAtCoder社の方々お疲れさまでした、ありがとうございます。
簡単に問題を振り返ってみます。
ABC165の問題のネタバレが含まるので気を付けてください。
a以上b以下の範囲を調べたいときはa-1以下とb以下の範囲をそれぞれ調べて差をみてやると上手くことが多いです。累積和などもこの考え方です。
もちろん全探索でも調べられます。解法に貴賤はありませんが上記の考え方も知っておくと後々役に立ちます。
シミュレーションしていけば答えが出ます。制約が10^18と大きいですがサンプルに10^18があるので親切仕様です。
話題になったC問題です。やることはごくシンプルなDFSですが確かにいつものC問題よりは難しいです。
計算量の目安がつかずに諦めた人も多いそうですね。制約が小さいので頭の中で簡単にイメージしてやると案外候補が少ないことに気づきます。どうせ通るだろ、の気持ちで提出しました。
はい、まさかのO(１)解法かつ茶下位diffの問題です。……僕はCよりDのほうが難しく感じました。実際Dのほうが時間もかかったので。
どんなにヤバそうな問題でも小さい値で全探索/シミュレーションをしてみることが大切です。この問題も適当に値を決めて全部計算したら「B周期である」「周期内では広義単調増加（非減少）」であることが分かります。
unratedになりかけた原因のある問題です。
問題文通りにイメージすると数字がどんどん変わっていて頭がパンクします。（僕だけでしょうか？）
問題文を言い換え（同値変形）することはどんな時も大切です。その言いかえさえできればこの問題の半分は解けた気がします。
LIS（最長増加部分列）を求める問題です。CでもFでもDFSが出ましたね。
僕はAC出来ていませんがポイントは「ある頂点から先を見終わったときに、その頂点の直前の状態にDPテーブルを復元する」ことかな、と思います。
以上、問題の振り返りでした。
今回のABCで思ったのは「もっと全探索を重要視しよう」ということです。
コンピュータが真に人より優れているのは「計算」と「処理速度」です。その「処理速度」に頼る全探索は本来一番自然な考え方です。
そして単なる全探索だと間に合わないから効率化・高速化したのが累積和やDPだと思います。まずは基礎かつ本質たる全探索をおさえましょう。
4.最近の精進について
人によって向いている精進方法やペースは差異があるので一概にいうことは出来ませんが、「精進するほどレートが伸びやすくなる」くらいは言って良いと思います。
その上で参考までに僕の最近の精進をまとめました。
みんなお馴染みAtCoder Problemsです。（お馴染みじゃない、という方はぜひ試してみて下さい。とても便利です。）
もう少しで800ACかつ青色精進ですね。
続いてやはりお馴染みAtCoder Scoresの精進グラフです。
これを見ると2月の最後まで全然精進していないことがばれますね。確か200ACもしていなかったです。
（なぜ突然頑張りだしたのか、それは新型コロナウイルスによって不完全燃焼に終わった定期試験へのやる気をぶつけたからです）
精進を沢山してもすぐにはレートが上がらないことが多いです。
でもしばらくしたらブレイクスルーがやってきます。気長に競プロを続けましょう。
次に最近はやりの精進を紹介します。
AtCoder Problemsから参加できるヴァーチャルコンテストの「よるかつ」です。
参加者も多数おり、楽しく精進できます。
よるかつ終了後に考察を呟いている人もいるので解けなかった問題も復習しやすいです。
よるかつと似たヴァーチャルコンテストとして「あさかつ」もありますが、その時間帯は僕はまだ布団の中でスヤスヤ眠っているので参加したことはありません。
緑になるまでの精進内容はQiitaで書いた色変記事に載っているのでそちらも参考にしてみて下さい。
緑から水色になるまでの間の精進で思ったことを少し書きます。
1つはやはり典型アルゴリズムを知ることの大切さです。
緑までは考察が上手くいけば解ける問題も多かったですが、水色diffになるとあるアルゴリズムを扱えることが前提となることが多くなってきた印象です。
逆にアルゴリズムの知識があればそれを上手く適用して解ける問題が多いので知っているかどうかが分水嶺となりやすいです。
これは実際に水色diff以上の問題をいくつも解いて解説を読んで理解することが一番手っ取り早いでしょう。
もう1つは解く速さについてです。
水色になるには水色パフォーマンスを出す必要がありますが、水色パフォーマンスを出すには水色diffが必ず解ける必要はありません。
灰－茶、茶—緑に比べて緑—水の難易度傾斜は少しきつい気がします。
だから水diffを解くことと並行して緑以下diffを速めに解けるようになることも大切です。
あとはEducational DP Contest - AtCoderのような特化した問題を解いてアルゴリズムを身に着けることも有効そうです。
焦らず1つずつアルゴリズムをものにしていくことが大切です。
まあ、この章の冒頭で述べた通り人によって何が適しているかは千差万別なので各々が自分に必要な精進や知識を考えてみたらそれが一番です。
5.さいごに
「はじめに」があるから「さいごに」もあるだろ、という気持ちでこの章をつくりましたが正直書くことは無いです。
この文章を書いている今日（5月3日）は、このあとにABCとこどふぉがあります。その両方で色落ちして「1日に2回色落ちしました！」という記事を書くようなことにならないことを祈っています。
もし今日色落ちしたら追記でこの下に書き足します。追記が無ければ無事耐えたと思ってください。
それでは、ここまで読んでいただきありがとうございました。
