AtCoderでついに入緑しました!!!
どうも皆さんこんにちは。
先日行われた 第二回日本最強プログラマー学生選手権 でついに緑コーダーになることが出来ました!!!
本当に長い道のりでしたし、とても嬉しかったです!!
そこで今回はこれまでの過程や自分なりのアドバイスが出来ればなと思って記事を書いていこうと思います!
目次
- 1. 自己紹介
- 2. 緑色の実力について
- 3. 緑色になるまでに取り組んできたこと
- 4. 学んだアルゴリズムについて
- 5. 各種実績について
- 6. モチベーションの維持について
- 7. 最後に振り返って
1. 自己紹介
- 所属:公立はこだて未来大学(FUN) B3
- 競プロ歴:10ヶ月程度
- AtCoder:AtCoderのアカウント 自分のレートの遷移図が見れます!
- Twitter:Twitterのアカウント フォローお待ちしております!
- GitHub:GitHubのアカウント AtCoderのライブラリや典型90問のPythonコードなども上げてるのでチェックしてみて!
- OMC:OMCのアカウント 世間ではなぜか数強と呼ばれています...
2. 緑色の実力について
AtCoderの緑色(レートが800〜1199)の実力についてはAtCoder社 社長であるchokudaiさんが下記のように評価しています↓↓
緑色 (Cランク R800~1199 上位30%)
緑色になれれば、「競技プログラミングに熱心に取り組んでいる人」と考えて問題ないでしょう。要求レベルも決して低くなく、出場回数が足りないとマイナス補正がかかるため、運だけで到達することはまず出来ないラインです。他社アルゴリズム力判定サービスだと、上位1%の最高ランクが付く実力です。(あくまで「アルゴリズム力部分だけであることに注意してください)
印象としては、
- 学生ならかなり優秀。
- エンジニアとしてもある程度の安心感がある。論理的に複雑な処理の実装に対応できない、なんてことはなさそう、くらいには思える。データ量が多い現場など、計算量の多い処理が要求される現場でなければ、このレート帯以上を求める必要はほぼない。
くらいの印象です。もちろんアルゴリズム力しか計ってないので個人差があります。
技術的な部分では、
- if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
- 簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。
という感じです。
こんな感じで書かれていますが、実際の所、本当にこのような感じだと思います。
最近のAtCoder界隈では、「参加者のインフレが高くてレートが上がらない」や「昔ならもっとdiff(各問題の難易度を表す指標のようなもの)が低いだろ」などの意見も頻繁に聞きます。
確かに、昔よりかはレートを上げるのが難しくなっているような感じはしますが、緑に必要なアルゴリズムの典型はそんなに多くないと思います。
3. 緑色になるまでに取り組んできたこと
まずは、入茶した日(2020/09/19)から、今日(2021/04/17)に至るまでに精進してきたことを紹介したいと思います。
ここで話す内容がとても大事だと思うので、ぜひ読んでいただけると幸いです。
取り組んだ内容 | 期間 | 重要度 |
---|---|---|
AtCoderの茶色全埋め | 最初の1ヶ月 | 低 |
初中級者が解くべき過去問精選 100 問(後ほど解説)を全埋めしたがる | 最初の2ヶ月 | 高 |
AtCoderの緑diff100問以上AC | 茶色全埋め後から1ヶ月半 | 高 |
競プロ典型90問(後ほど解説)に挑戦 | 直近1週間 | 高 |
毎日精進(連続Streakの記録伸ばし) | 入茶する前から1年ほど | 超絶低 |
上記の表について軽く解説したいと思います。
AtCoderの茶色全埋め
これは正直あまりやる必要がないと思います。
自分がやろうと思った経緯については、茶色になったし、茶色の問題を全部溶けるレベルにしないとレートが上がらないよなーと思い全埋めをしました。
しかし、これよりも緑や水の問題をもっと解くべきだったと思います。
難易度の高い問題を優先して解いていけば、必然的に茶や灰の問題はスムーズに解けるようになると思います。
初中級者が解くべき過去問精選 100 問 を全埋めしたがる
このまとめられた問題集はとても良いと思いました!!
アルゴリズムを学ぶ際に、学びたいアルゴリズムを利用した問題がたくさん用意されているからです。
しかし、自分のような進め方でやっていくと確実に効率が悪いです。自分がどのようにやったかというと、何がなんでも順番に進めていくということです。
精選100問の中には平気で青や黄レベルの問題が含まれており、自分はその問題に出くわしたら解くまで、理解するまで次には進みませんでした。その結果、区間 DP, bit DP の分野で挫折して諦めてしまいました。(今はボチボチ再開してます。)
つまり、何が言いたいかと言うと、難しい問題に出会ったらとりあえず解説AC(答えを見てなるほどーって軽い気持ちで写経してAC)をして、とにかく100問最後まで解ききると言うのが大切だと思います!!
そうすると、とりあえずは基本的な全てのアルゴリズムを知ったことになるので、普段のコンテストの解説を見て「全くわからない...」ということは起きなくなるだろうし、典型問題だったら簡単にACできると思うので、ぜひ最後までやり切って見て下さい!!
AtCoderの緑diff100問以上AC
これは、精選100問を行いながら同時進行で進めていました。
最近は貼っていませんが、 精進ツリー もTwitterに作ってモチベーションを保っていました。
感想としては、とてもやる意義があったと思います。やはり、緑は自分が目指していた問題なので、それを解くことで緑のレベルを知ることが出来るし、とても効率の良い勉強法ではなかったのでは?と自分では思ってます。
ただ、先ほどと同様に全部を埋める必要はないです。中にはとても難しい緑の問題や、昔の問題でとても簡単なのに緑になっている問題も存在するので、最近の緑の問題を埋めるのがとても効率が良い気がします!
競プロ典型90問 に挑戦
これは5日前くらいから始めたのですが、とても良いと思います!!
こちらも精選100問と同様に典型の問題がたくさんオリジナルで作られているのでぜひやってみると良いと思います!
また、毎日の解説に記載されている類題も解いてみるととても力が付くような気がします。
下記のリンクにPythonのコードを少しずつ載せているので、興味のある方は是非ご覧ください!
毎日精進(連続Streakの記録伸ばし)
これが一番伝えたかったことです!!!!
特に灰や茶の人(自分もそうでした)でよく見かけますが、
レートを伸ばしたい方が、Streakの記録を伸ばしたいがために、毎日ACするのは絶対に良くないと思います!!!!!!!!!!!
まず、誤解があるといけないので伝えておくと、例えばとても時間があり、難しい問題(自分のレートよりも1, 2色以上の問題)を毎日解き続けている方なら問題ないし、むしろ良いと思います。
だって難しい問題を毎日解いてるんですもの。絶対に報われるじゃないですか...
自分が言いたいことは何かというと、自分のように力もつかないような(自分の色よりも下の色の問題)を解くのは絶対に効率が悪いと言うことです。
確かに競技プログラミングをするという習慣はつきます。しかし、そのせいで私生活に影響が出たりもしてきます。
なんか300日連続ACしてました。
— カイリュー (@ryusuke__h) 2021年2月25日
AtCoder神ゲーかよ pic.twitter.com/K2gc36CIAM
自分はなんか2月にこんなツイートをしてイキッていましたが、300日連続ACを達成するために、どんなに忙しい日でも簡単な問題を解く、簡単な問題が無くなったら AtCoder Problems の Other Contests からひたすら探す、と言う感じでとにかく毎日続けていました...
しかし冷静に考えて、自分にとって簡単な問題は解いた所で力が付く訳ないじゃないですか?
もし付いても糧となる経験値は少なそうですし...
簡単な問題をやるなら、どこかまとまった日にでも 50問くらい一気にやってしまえば良いんじゃないですか?と思いましたし、300日前の自分に聞かせてあげたいです。
だから、これ以降は自分(該当する読者の方で賛同して下さっている方がいるならその方も)は出来る日に、時間のある日に問題を解いて、特に難しい問題、まだ自分の知らないアルゴリズムを勉強する、こういった姿勢がレートが上がる最善策ではないのかと思います。
悪魔でも、上記の文章は自分の個人的な考えなので 「当てはまらない・そうでもないわ。」 などと思った方は無視していただいて全く問題ありません。
実際に、この話題についても賛否両論の意見があると思うので!
4. 学んだアルゴリズムについて
学んだアルゴリズムは下記の表の通りです。
理解度
理解度の種別について | 説明 |
---|---|
◎ | 理解してるので、何も見ずに書けるし、テンプレートもある |
△ | テンプレートがあるのみで、無いと書けない。典型問題なら解ける |
× | 聞いたことしかない |
茶 | 茶色になる以前から身に付けていたアルゴリズム |
重要度
※重要度は、緑色になるために必要なアルゴリズムかということです。決して競技プログラミングをやる上で知らなくても良いというわけではありません!!
また、完全に個人的な主観となっていますのでご了承ください。
アルゴリズム | 理解度(◎・△・×・茶) | 重要度(高・中・低) |
---|---|---|
最大公約数, 最小公倍数 | 茶 | 高 |
高速素数判定 | 茶 | 高 |
エラトステネスの篩 | ◎ | 中 |
素因数分解 | 茶 | 高 |
約数列挙 | 茶 | 高 |
半分全列挙 | △ | 低 |
累積和 | 茶 | 高 |
いもす法 | ◎ | 高 |
高速な冪乗計算 | ◎ | 中 |
逆元の利用 | × | 低 |
bit全探索 | 茶 | 高 |
二分探索 | △ | 中 |
幅優先探索(BFS) | ◎ | 高 |
深さ優先探索(DFS) | ◎ | 高 |
DP := 動的計画法(基本的な問題) | ◎ | 中 |
区間 DP | × | 低 |
bit DP | × | 低 |
ダイクストラ法 | ◎ | 中 |
ワーシャルフロイド法 | △ | 低 |
ダブリング | △ | 低 |
クラスカル法 | × | 低 |
RLE := RunLengthEncoding | ◎ | 低 |
LCS := LongestCommonSubsequence(最長共通部分文字列) | ◎ | 低 |
LIS := LongestIncreasingSubsequence(最長増加部分列) | ◎ | 低 |
Union-Find木 | ◎ | 高 |
座圧 | ◎ | 中 |
行列累乗 | × | 低 |
Rolling Hash | × | 低 |
平方分割 | × | 低 |
最大流/最小カット | × | 低 |
Grundy 数 | × | 低 |
BIT := Binary Indexed Tree | × | 低 |
RMQ := Range Minimum Query | × | 低 |
遅延評価セグメント木 | × | 低 |
こう見てみると、とてもアルゴリズムって多いんですね...
灰時代では知らなかったアルゴリズムもたくさんありました。
灰・茶で「緑行けないよー」と言う方は一つの参考にしていただければ幸いです。
水に行くまでには下の全滅してるアルゴリズム 7, 8個を確実にマスターして入水したいです!
5. 各種実績について
AtCoder Problemsにて掲載されているデータを載せておきます。
Achievement
AtCoder Pie Charts
Difficulty Pies
Daily Effort
Climbing
Heatmap
6. モチベーションの維持について
競技プログラミングを行う上でよく話題になるのが、モチベーションの維持です。
自分はメンタルが強いのか、一度もモチベが下がったり、落ち込んでしまったりしたことはありませんが、話題になっているので少しだけお話しします。
周りの初心者が強すぎて、メンタルがやられてしまう場合
と言うのもAtCoderではとても能力・才能の高い初心者の方が山のようにおられ、そういった方が後から始めたにも関わらず、平気で自分のレートを越していきます。
こういう方を見て、自分のメンタルがやられてしまう方(自分は全くならないです。)は、
・その方をミュートにする
・今までAtCoderをやって来てないだけで、自分よりもアルゴリズムに詳しい
・最悪の場合、ブロ解(ブロックをして解除することで、フォローを外すことが出来ます。)を行う。
などと言った思考・処置をすればこういう被害は削減できると思います。
以降は完全な個人的な見解ですが、メンタルがやられてしまう方の場合、自分が1番だと思ってませんか?
なので後から入って来た人が、自分を超えると「なんで自分は置いていかれるんだ?」となってしまうのだと考えています。
上には上がいるといつも考えると楽になるのではないでしょうか?ならなかったらごめんなさい。
自分も数学は平均以上には出来る方だとは自負しており、良く水色の方などに、「いつになったら入緑しますか?」とか「なんで茶色から上がれないんですか?」などと言ったような、心配や煽り(自分には今後もしていただいて、全く問題ないです。むしろ煽って来て下さい。)の声を毎週のように聞いていました。
レートが伸びず、メンタルがやられてしまう場合
それから単純に伸び悩んでいる方でメンタルがやられる方も多いと思います。
確かに問題の愛称はとても大きく影響してくると思います。
ですが、昨日の自分よりは、今日の自分の方が経験値が豊富のはずなので、最後まで諦めずに頑張ってほしいです。
7. 最後に振り返って
だいぶ長くなってしまいましたが、いかがでしたか??
色変記事は2回目で少しは書き慣れましたが、まだまだ至らない点が多いと思います。
次の目標はいよいよ最初に自分が立てた最終目標の水色です!
頑張って入水出来るように頑張りますので応援よろしくお願いします!!!!
最後までありがとうございました!