緑コーダー(AtCoder)になった和洋
アローラ、最近友人が急減したMDMAと申します。
とある面接試験のネタとして始めたっきり放置していた競技プログラミングで、一定の成果を残せたのでここに記録します。毎度のことながら、人によっては自慢に見えてしまうかもしれません。また、無限に言われてたことばっかり書かれてるので内容薄いかもしれません。
なんでMDMAなの?
ーハンドルネームを決めるー現代社会においては、もはやライフイベントとも数えられる営みであるため、みなさんも経験したことがあるかと思います。
僕の場合は、音ゲー未経験で大学の音ゲーサークルに入るときに、苗字もじり以外のハンドルネームを求めてこのイベントに突入しました。とは言っても、ハンドルネームの付け方なんて学校では習わなかったし、人に相談するものでもなかったしで、当時は大変に苦労しました。
・・・
まあ、「色」とか「食べ物」はハンドルネームとして無難だろうと考え、そのとき着てた服の色、好きだった飲み物から着想を得、『緑魔剤』というハンドルネームを考案し、それを使用することにしました。そこから紆余曲折あり、現在のハンドルネームは、みどまとか、それを子音表現したMDMAとかに落ち着いています。
このように、私と「緑色」との間には宿命にも似た並々ならぬ関係があったのでした。
🍌お前は何者だ👓
- 大学生(国立・非情報系)
- 東大理系数学38点(/120点)
- 暗記科目は任せて!
- 情報の単位は落単
- プログラミング、やるやる詐欺し続けて大学4年間終わっちゃった!
- AtCoderへの取り組みは、1年半ダラダラ→4ヶ月ガチ(?)勉
なんだかんだ数学の素養については界隈平均くらいかそれよりちょい上くらいだと信じたいのですが、不毛なのでこれ以上の言及は。。。僕より明らかに強い人が「勝てん」とか言うの禁止です。プログラミングは、いわゆる『AtCoder純粋培養』です。
何やったん
音ゲーでも、「◯◯クレでXXレート」という話題はときに大きな炎上のタネとなってしまうので、この話題については慎重に接する必要があります。ので、事実だけを述べます。私はちょうど300ACで緑レートになることが出来ました。実際のところは、典型90のACが反映されていないのでこれ+50ACくらいでしょうか。
プログラミング未経験から始めた割には少ないAC数で緑レートになれたと認識しています。
(冒頭の図にあるように茶色の途中で躓いてはいますが・・・)
誰しも、できるだけ省エネで良い結果を得たいと考えるのは自然なことです。そこで、僭越ながら、私が「何を」「どのように」「どのくらいの情熱で」勉強してきたかを共有し、手っ取り早く緑レートに到達したい人の不安や迷いを少しでも解消するお手伝いをさせていただきたいと思います。
私を大きく成長させてくれた印象深い教材は
1.PAST本
2.競プロ典型90問
でした。
次の項では、これらの教材に触れながら、直近3ヶ月間どのように勉強を進めたかを記します。
どうやったん
3月
大学が暇になったので、ふと、1年半前にチョロっとやったっきり放置していた競技プログラミングを再開する気分となりました。
当時、レートは100くらいで、 ABCのC問題が解けたり解けなかったりというレベル。
灰色問題を1日20問とかのペースでACしていました。今考えるとちょっと無駄だったかもしれません。
3月13日のABC195でたまたまD(貪欲にやればいいからたまたま通ってしまった)問題までコンテスト中にACしてしまい、そこでやる気が急燃。大学の生協購買部でたまたま見つけたPAST本
アルゴリズム実技検定 公式テキスト[エントリー~中級編] (Compass Booksシリーズ) | 岩下 真也, 中村 謙弘, AtCoder株式会社, 高橋 直大 |本 | 通販 | Amazon
を購入し、本格的に取り組んでみるかという気になれました。
時間の暴力で翌日には一周読み切り、基本アルゴリズムを概観することが出来ました。
このスピード感はかなり良かったのではないかと思います。
茶〜緑perfが安定するようになり、3月最後のコンテストでレートが茶色になりました。
4月
ごめんなさい!!!!!!
なんか新生活にかまけて(あとモンハンしてて)週末のコンテストしか出てません!!!!!!!
週末になるたびに、PAST本を傍らにコンテストに出場していました。一回読んだとはいえ、内容を使いこなせるようになったわけではないため茶〜緑perf止まりですが、標準入力や簡単なデータ構造で迷うことがなくなったので灰perfからは完全に脱却できたと分析します。正直、PAST本があるだけで何もしなくてもレートが伸びる時期でした。
ここで甘えて精進をやめてしまったことで、6月以降少し苦しんでしまうことになってしまったのかもしれません。
5月前半
学振とデスマーチを繰り広げていたので、5月前半は4月と同じく週末にコンテストに参加するだけでした。
rating700までいっていますが、PAST本を必要なときに引っ張り出してくるだけでここまで来ました。本当はしっかり味わい尽くすべき参考書なのですが、当時の僕にはそこまでのモチベーションがありませんでした。(本当にごめんなさい)
5月後半
特に何かキッカケがあったわけでもなく偶然に、競プロ仲間が急に増えました(高校同期が+3名、大学の知り合いが+2名)。
中には、この時期に始めたのにも関わらず今では典型90のランカーに名を連ねるような有望株(Sさん)も現れ、自宅ではそのような方々と通話しながら典型90を解き進める時間が増えました。というか、モンハンの時間が競プロになりました。ここから生活がガラリと変わりました。
また、この辺りからCの速解きができなければレートが伸びなくなり、毎回本を引っ張ってきてコードを書くというやり方に限界が見えてきました。また、週末のコンテストでしか問題を解いていないという習慣のツケが回ってきたとも言えましょう。
6月
と、なればABCのC問題〜D問題を安定させなければ先はないと考え、#400点汁 を始めました。(注:「汁」とは、ネットスラングの「◯◯なオタク、集合汁!」が「集合汁!」→「汁」と短縮していったもので、「通話しようぜ!」という意味の身内の造語です。)
先述のSさんを呼びつけ、ぼくは300~400点問題や典型90の星5までの問題を、彼は400~500点問題や典型90の星7までの問題を唸りながら解き進めるというDiscord通話が、平日の夜に相当な頻度で開催されるようになりました。ときにはEDPC(DPまとめコンテスト)に取り組んだり、バーチャルコンテストに参加したりと、今までで一番熱心に競技プログラミングに取り組むことができたと思います。
また、この時期に、e869120さんの、『レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】』
qiita.com
に記されている12個の基本アルゴリズムと3のデータ構造について、テンプレートを作成しました。
これは当該アルゴリズム・データ構造をテーマとした問題を1~2個選び、PAST本などを参考にしながら自力で解答しそのコードを残しただけの、一般性にいまひとつ欠けるテンプレ集です。しかしながら、自分の頭の中の道具箱を文字として、コピー&ペーストで一発アクセスできる形に残しておくことで、問題を見て解き方がわかってからの解答速度が目に見えて向上しました。また、まだコンテストで役に立ったことはありませんが、念の為ACLの一部も使用できるようにしておきました。また、この過程でPAST本を精読したので、5月までと比べて基本アルゴリズムへの理解度も格段に上がっていました。
6月は熱意の割に結果が伴わない月でした。
コンテストの戦略ミスや速解き失敗、D問題を一度も通せなかったことなどが原因です。
急にレート上昇が止まってちょっと驚いてしまいましたが、別に気持ちが沈むわけではなく、これだけやってるんだしそのうち伸びるやろとポジティブな気持ちを切らさずに、精進の習慣をこなす毎日でした。僕、割と勉強全般で、できなくてもネガティブになったことないしこういうの向いてるのかもしれません()
コツコツ続けた結果、6月が終わる頃に典型90の得点が100点に達しました。木のノード間の距離を求めるコードや、imos法、しゃくとり法などはここでライブラリ化しておきました(伏線)。
典型90 💯 pic.twitter.com/6kaqtqi5gX
— 玖大入生绝望会 (@mdrm1rou) 2021年6月28日
7月
根拠のない自信が芽生えてきたので、#1日1題水色ACチャレンジ を始めました。
また、MojaCoderやAtCoder Problemsを用いて高校同期界隈でコンテストを高頻度に開催し、速解き力を鍛えました。自分では難しい問題に特攻しがちでなかなか速解きの練習を積むことができないので、とても好都合でした。
そんなこんなで、先人に言われた通りに毎日アルゴリズムを学び、ちょろっと速解きの練習をしたら、直後のコンテストでやっと連続で上に振れることができ、ついに緑レートに突入することが出来ました。
ABC208のD問題はワーシャルフロイド法の問題でしたが、何を思ったか初めはダイクストラ法でゴリ押そうとしていました。ワーシャルフロイド法で実装した方が手取り早いと気づいてからは、PAST本に全く同じ状況の問題を見つけ、そこから一瞬でした。
ABC209のD問題は図に書いてみたらノード間の距離が偶数か奇数かわかればいいとすぐにわかったので、典型90で似たような問題をやったことがあると思い出し、自作ライブラリから該当する問題の自分の提出を引っ張ってきて速解きに成功することが出来ました。
ちょうどその日に、典型90で150点を突破し、全体の85パーセンタイルに達することが出来ました。e869120さんのツイートを参考にすると、同一レート帯ではおそらく上位10%くらいだと思われます。150点になったその日に入緑するの本当にわかりやすくていいので(個人の感想)、ご参考までに。
#競プロ典型90問 の統計データが出ました。全体の半数以上が 40 点未満ですが、緑コーダーの約 1 割、水コーダーの約 2 割、青コーダーの約 4 割が 200 点以上です。
— E869120@公開アカウント (@e869120) 2021年7月5日
同レート帯の上位 10% が一つの基準になるので、最終的には「得点率 min(100, 自分のレート/20) %」を目標にすると良いと思います。 pic.twitter.com/mfXUJ09l4A
真面目めに取り組んだらちゃんと実力が伸びたので、コンテスト期間は終わってしまいましたがこれからも少しずつ埋めていきたいと考えています。
手取り早くギュンと入緑するためのまとめコメント
PAST本(Python勢)などの参考書や、信頼できるネット記事を見つけて、できれば平日も練習しましょう
モチベ維持のために仲間を見つけましょう
できれば、ポジティブに続けられる距離感を保てたらいいかもしれません
今後
今はまだアルゴリズムを知ってるだけで、応用にまだまだ弱いので、これについては演習量でカバーしていきたいです。適宜、上手い人のコードを拝見するなどして、綺麗な実装ができるようになります。
首尾よく2連続で水色perfを出せているので、秋くらいまでに水色レートになれるように頑張りたいです(医学は?)
同級生その他で興味ある人は、自分に教えられることは教えるので一緒にキモチよくなりましょう。