🧑💻 AtCoder始めて2ヶ月で入茶するまでにやったこと
はじめに ~AtCoderって何?~
AtCoder は 競技プログラミングコンテスト を開催している 国内サイトです
世界で 60万人以上 のユーザーがおり、定期的に開催されるコンテストで プログラミング力、アルゴリズムの実装能力 を競います
結果は レーティング(数値)、世界ランキング に反映され、自分の実力を相対的かつ定量的に図ることができます
問題の構成(Beginner Contest)
A ~ G までの 7問で構成され、難易度の差に明確な壁があります
この場では、掲題の「入茶」するのに必要な C問題 の説明までにとどめるとします
A : 基本的な条件分岐
与えられる値が "red" だったら "Yes"、"blue"なら"No"と出力せよ みたいなレベル
問題例 : https://atcoder.jp/contests/abc358/tasks/abc358_a
B : 配列操作と算数の知識
与えられた複数行にわたる入力値 を 配列に格納し、偶数の値を全て合計せよ みたいなレベル
要求されるアルゴリズム実装力の観点で言えば、ここまでは 全探索 でパスできる
偶数、奇数を判定させる、配列要素をソートさせる、など典型的な課題が与えられることが多いので、初心者は最初 B問題 を解きまくれば実装力の基礎はつく印象
問題例 : https://atcoder.jp/contests/abc348/tasks/abc348_b
C : 数学的アルゴリズムを用いた計算量の削減
ここからグンとレベルが上がる
まず、問題文を理解し、解答の方針を決める際、 確率や三角関数など、高校数学(基礎?)レベルの知識が必要な場合がある
その上、実行時間の制限も考慮する必要があり、計算回数を減らさないと不正解となってしまう
問題例 : https://atcoder.jp/contests/abc358/tasks/abc358_c
レーティングについて
レーティングは大きく7段階 に分かれています
灰色(0 ~) : 初心者。茶色になるまでに挫折する人が多く、最も人口が多い
茶色(400~) : C問題が解けるか解けないかといった実力帯。ここから、全競技人口の上位50% に入ることができる
以降の実力帯の説明については以下記事を参考のこと(世界ランキングトップ層のプレーヤーが詳細にまとめてくださっています)
レーティングの算出
レーティングは過去参加した全てのコンテストのパフォーマンスから算出されます。
パフォーマンス には 解答速度、得点数(正解する毎に加算)、ペナルティ(解答ミスの少なさ)が関係しているようです。
本題~２ヶ月で入茶した件~
もうお気づきのことかと思いますが、「入茶」とは「レート400 以上に到達すること」を指します。
前提
筆者はAtCoderを始める前に、書籍にて少しばかりアルゴリズムとデータ探索の知識をインプット済みです。
知識のレベル感としては 二分探索やDP(動的計画法) などの存在を知っており、ざっくりどんなことをしているか答えられる といった状態です
なんで入茶を目指したの？
職場で担当する仕事のレベルを上げていくため、文系卒の筆者には「基礎力の証明」が必要であったためです
具体的には
プログラミング言語の基礎文法を理解していること
アルゴリズムを用いた基礎的なデータ探索が独力でできること
以上2点の客観的な証明をしたかったため です。
(余談)
2024年4月に新卒就職した筆者ですが、文系卒の筆者の周りは理系卒ばかり(しかも有名国立大学院卒とかで なんで私が入社できたのか不思議なくらい笑)理系の情報専攻卒ならプログラミング基礎は身についていることが保証されており(だよね？)、ある程度即戦力として期待できるが文系で趣味程度にアプリ作っていた筆者は。。。^^;
入茶までの２ヶ月でやったこと
初日 : 要件の明確化
コスパよく目標を達成したかった筆者はゴールの明確化を先に実施しました
調査の結果、達成にはざっくり以下 3つのこと が必要でした
A,B 問題を3~5分以内に解く
C問題を正解できる確率を上げる
毎回コンテスト参加する <- 一番大事!!
１ヶ月目 : 基礎力を上げる(B問題まで確実に解けるようになる)
以下を繰り返していました
① 毎日１問以上、B問題の過去問を解く
② 初めての知識、解法があればチートシートにまとめる
③ 解答に詰まったらチートシート確認し、解く
④ (余力があれば C問題解く -> ほぼ玉砕(；ω；))
＋ 毎週土曜日のABCコンテストに参加し、少しでもレート上げる
特に、チートシート作成し、反復して確認したことの効果が大きかったです
反復学習のおかげで、目標達成する頃には確認しなくても、シート記載の知識はスッと出てくるようになっており、「A,B 問題を3~5分以内に解く」達成に効果大でした。
2ヶ月目以降 : C問題レベルの知識(アルゴリズム)をひたすらインプット
B問題が5分以内に安定して解けるようになり、自主学習の時間に余裕が出てきたところでC問題への挑戦を本格化しました。
解いた問題は、C問題以上の難易度の 典型的な問題がまとまっている「競プロ典型問題90」です。
その名の通り、「典型的な解法を使う問題」がまとまっているので アルゴリズム実装の応用力がつきます。
① 解説を読んで解答方針を理解する。コードを記憶する
② 模範解答のコードを写経、解説コメントを記入
(この時 ①の短期記憶に頼り、なるべく解答は見ないようにする)
③ 一回写経したら3日間絶対に問題文も解答も見ない
④ 3日経ったら②を実施し復習
以降、②~④を繰り返す
「典型問題」を繰り返し解いて「実装の勘」を養うことで、問題文読んだ段階で解答方針が浮かぶようになっていきます
(「あ、これ 2^N通りの全探索 だから DP で解けるなー」
＞「 DPってどうやるんだっけ？チートシート確認しよ」みたいな感じ」
(余談)
③~④学習方法は「スペースド・リピティション(間隔反復学習)」と言うらしく、科学的根拠に基づいた学習法です。(実際、筆者の知識の定着も早かった気がする。そう、気がする。。)
2ヶ月後(目標達成！！)
AtCoder Beginner Contest 364 にて茶色レートになることができました！
この時点ではまだまだ解けないC問題たくさんありましたが、
プログラミング言語の基礎文法を理解していること
アルゴリズムを用いた基礎的なデータ探索が独力でできること
の客観的証明には足りているかと。
最後に~今後やっていきたいこと~
なんやかんやあり、無事に「効率的に入茶を達成」することができましたがまだまだ突き進みます。
次の目標は 「１年以内に緑レートになること」です
また、私が先人の解説記事に助けられたように、今度は私自身が解説記事を発信する立場になりたいものです。(そのための実力を身につけるが先ですが)
この記事が AtCoder初心者の方のお役に立てれば、筆者としてはそれ以上の幸福はありません。
ぜひ、良き競プロライフを( ^_^)/