追記(2024/6/12)
いろいろ考え方変わってるからこっち(入橙記事)の方を見てほしいです
まえがき
こんにちは、Halcyonです。
先日開催されたAGC063にて青色コーダーに昇格しました。
AtCoderの社長であるchokudaiさんのブログによると、青色コーダーのレベルは
- 学生時代を競技プログラミングに注ぎ込んでも、ここにたどり着けない学生は大量にいる
- 8割以上のIT企業において、アルゴリズム力はカンスト(一部企業においては、少し持て余してしまう)
という感じらしいので、中２であるこの段階で青に到達できたのは素直にめちゃくちゃ嬉しいです。
この記事では、私が青色コーダーになるためにやったこととか、精進量とか、好きな問題などを書き留めておきます。
「この記事を見て色が一色上がった！」みたいな人が一人でもいれば幸いです。
伝えたいことを1行で
精選100問を埋めるのが最強です。
ステータス
- 普通の中２
- プログラミング経験はPythonがあったが、アルゴリズムの経験はなし
- 数学に関しては平均以上の知識があると思っている
同レート帯に比べて
- 非常に若い
- 数学が強くアルゴリズムがやや弱い
のが特徴だと思います。
精進の仕方
写真集
▲レート変動・精進グラフ
最近の精進グラフの上がり方が尋常じゃない。
レートが(狭義)単調増加なのは珍しいと思います。
▲Difficulty Pies
同レート帯と比べると精進量は少ないほうだと思います。ただし、後述しますが、精進の質はかなり良いものだと思います。
▲Daily Effort
AtCoderにはまったのが今年の4月頃なので、この頃から精進量が上がっているのが伺えます。
▲Climbing
解いた問題の半数以上が灰色相当の難易度だと思います。ただ難しい問題の割合も低くはないと思います。
▲Heatmap
最近青以上のStreakを絶やさない遊びをしています。かなり効果があったと思います。
▲Languages
基本Python勢ですが、JOIに向けてC++も学び中。
PascalとTextとRubyは遊びです。
▲AtCoder Type Checker
多く解くタイプらしいです。多分合ってます。
取り組み方
水色になるまで
この記事を参考に、精選100問を埋めました。
青になれたのも、9割この記事のおかげだと思っています。この質の記事が無料なのがQiitaのいいところですよね(?)
その後上級編の精選50問にも取り組みました。実はこっちは埋め終わってません…
あとは速解き力を鍛えるためにバーチャルコンテストを主催しました。最近は開けてないのですが…
青色になるまで
典型90問を★5まで、また★6の一部まで埋めました。典型を抑えられたので取り組んで良かったと思っています。
あと、たしかこのタイミングで蟻本を買いました。
この記事を参考に、今は中級編の途中まで進めました。もっと読み進めて多くの知識を身に着けたいです。
この後はAtCoder ProblemsのRecommendationを埋めたりしていましたが、なにか特定のことを習慣づけようと思い、最近になって２つのことを始めました。
どちらも青色になるのに少なからず貢献してくれたと思っています。
また、これらに関しても、精選100問で培った知識をフルに活かせたと思います。
Codeforcesのバーチャルコンテストに毎日参加
Codeforces anytimeを使用して、適正Divのバーチャルコンテストに参加しています。
海外のコンテストサイトなので、問題文が英語ですが、それはみらい翻訳くんに全てを任せています。
AtCoderよりも非自明な構築問題が多くて面白いです。
青色以上のDifficultyの問題を毎日解く
前述の写真集にも載せましたが、青色以上の問題を毎日解くようにしました。
これは一色上の問題を安定して解ければまず間違いなく青色に上がれるだろうと思ったからです。
高度な典型問題も少なくないので、とても勉強になっています。
解説ACについて
私は解説ACはためらいません。
勿論自分で考えはしますが、解けない問題にリソースを割かれるのが嫌なのと、特にABCの問題は典型が多いと思っているので、解説を見てでも身につけるべきかなと思います。
ここはとても個人の考えによると思いますが。
印象深い問題
挙げきれないので、コンテスト中に挑んだものについてのみ挙げることにします。
- E - Throwing the Die…全体通しても初めて解けた水Diffです。まじで大好きな問題です。
- D - AABCC…枝狩り探索の大事さを思い知らされました。
- F - Merge Set…超頂点という概念を初めて知った問題です。工夫次第で計算量を削減できる最もわかりやすい例だと思います。
- F - Shift Table…コンテスト中に初めて解けた青色Diffです。Unratedがまじで悔やまれる。
- E - Art Gallery on Graph…Pythonの弊害その1。tupleのほうが早いという重要な知識を得ることができました。あとC++の偉大さを思い知りました。
- E - Best Performances…Pythonの弊害その2。平衡二分探索木について調べるきっかけになりました。
- C - Ideal Sheet…とある解説を見たのを覚えていたのが功を奏しました。これ水色になるんですか。
- F - Make 10 Again…bitDPに気付いて通せたおかげで黄色Perfが出ました。ありがたや。
- C - Find it!…強連結成分分解で解けちゃいました。明らかに解説の解法のほうが楽ですね。
- E - Tangency of Cuboids…座標が小さいことに気付いて解けるべきだったなぁ、とめちゃくちゃ反省しています。
- Ex - snukesnuke…本番中こそ解けなかったものの、めちゃくちゃ答えに近づくことができたことの成長を感じました。
- B - Triple Pair…これが解けたおかげでレートが結構上がったので感謝しています。ちなみにAは未だに解けてません。
- D - Everywhere is Sparser than Whole (Construction)…エスパーで通しちゃいました。気持ちよかったです。
- B - Switching Travel…頂点1からスタートしないといけないと思ってて10ペナ程度くらいました。問題文は本当によく読みましょう…(自戒)
- C - Add Mod Operations…入青の決め手になった、本番中に解けた最初の橙Diffです。B問題はその後も解けていないので、さっさとC問題の考察を頑張ってよかったです。
Pythonの長所と欠点
Pythonをよく使い、C++を勉強した私にとっては、Pythonの大きな長所は以下の点であると考えます。
- コードが単純で、すぐに書ける
- 繰り返し二乗法を自前で実装しなくていい
- オーバーフローの心配が一切なく、大きな整数を多少ゴリ押して使える
逆に、Pythonを使う場合は以下の点に気をつけましょう。
- 平衡二分探索木がない…tatyamさんに感謝してこれをコピペしましょう。
- ACLが使えない…shakayamiさんに感謝してこれをコピペしましょう。
- 動作が遅い…PyPyを標準的に使うようにして、細かな点で定数倍高速化をしましょう。
おわりに
青色になりましたが、暖色コーダーたちを見てみると、ここは通過点に過ぎません。
勿論次の目標は黄色コーダーです。黄色になるためにもっと精進を重ねていこうと思っています。
終わります。