自己紹介

はじめまして！
今年度、アルバイトから正社員になった齊藤です！
この記事は、「プログラミング言語を学んでみたいけど特段作りたいものがない」という方に向けて、「競技プログラミング」という選択肢を提案したく、少しでも興味を持ってもらえればと執筆しました。

簡単なプロフィール

  • 文系の4年制大学を卒業しました
  • 2022年からアルバイトとしてお世話になっており、2024年4月に正社員になりました
  • 新卒での採用は第２号です
  • 大学時代、ネイティブアプリ開発に興味を持ち、flutterやSwiftで簡単なアプリを作成して遊んでいました
  • 最近はUnity、C#(+たまにblender)を使ってゲームギミックの作成にハマっています！
  • 社内ではQAチーム、インフラチームに所属し、見習いとして転びながらも日々勉強しています

はじめに ~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

レーティングについて

レーティング帯別人工分布

----------2024-11-14-14.01.13

レーティングは大きく7段階 に分かれています。

  • 灰色(0 ~) : 初心者。茶色になるまでに挫折する人が多く、最も人口が多い

  • 茶色(400~) : C問題が解けるか解けないかといった実力帯。ここから、全競技人口の上位50% に入ることができる

以降の実力帯の説明については以下記事を参考になさってください。(世界ランキングトップ層のプレーヤーでもある、AtCoder社長さんが詳細にまとめてくださっています)

https://chokudai.hatenablog.com/entry/2019/02/11/155904

レーティングの算出

レーティングは過去参加した全てのコンテストのパフォーマンスから算出されます。パフォーマンス には 解答速度、得点数(正解する毎に加算)、ペナルティ(解答ミスの少なさ)が関係しているようです。

https://info.atcoder.jp/overview/contest/rating
https://qiita.com/anqooqie/items/92005e337a0d2569bdbd

本題~２ヶ月で入茶した件~

もうお気づきのことかと思いますが、「入茶」とは「レート400 以上に到達すること」を指します。

前提

筆者はAtCoderを始める前に、書籍にて少しばかりアルゴリズムとデータ探索の知識をインプット済みです。

知識のレベル感としては 二分探索やDP(動的計画法) などの存在を知っており、ざっくりどんなことをしているか答えられる といった状態です。

なんで入茶を目指したの？

新卒で入社した職場で担当する仕事のレベルを上げていくため、文系卒の筆者には「基礎力の証明」が必要でした。

具体的には
プログラミング言語の基礎文法を理解していること
アルゴリズムを用いた基礎的なデータ探索が独力でできること
以上2点の客観的な証明をしたかった です。

入茶までの２ヶ月でやったこと

初日 : 要件の明確化

コスパよく目標を達成したかった筆者はゴールの明確化を先に実施しました。
調査の結果、達成にはざっくり以下 3つのこと が必要でした。

  1. A,B 問題を3~5分以内に解く
  2. C問題を正解できる確率を上げる
  3. 毎回コンテスト参加する <- 一番大事!!

~１ヶ月 : 基礎力を上げる(B問題まで確実に解けるようになる)

以下を繰り返していました
① 毎日１問以上、B問題の過去問を解く
② 初めての知識、解法があればチートシートにまとめる
③ 解答に詰まったらチートシート確認し、解く
④ (余力があれば C問題解く -> ほぼ玉砕(；ω；))
＋ 毎週土曜日のABCコンテストに参加し、少しでもレート上げる

特に、チートシート作成し、反復して確認したことの効果が大きかったです。

Notionで実際に作成したチートシート(一部抜粋)

1722767466839-nrDCP1etaF

反復学習のおかげで、目標達成する頃には確認しなくても、シート記載の知識はスッと出てくるようになっており、「A,B 問題を3~5分以内に解く」達成に効果大でした。

~2ヶ月 : C問題レベルの知識(アルゴリズム)をひたすらインプット

B問題が5分以内に安定して解けるようになり、自主学習の時間に余裕が出てきたところでC問題への挑戦を本格化しました。

解いた問題は、C問題以上の難易度の 典型的な問題がまとまっている「競プロ典型問題90」です。
その名の通り、「典型的な解法を使う問題」がまとまっているので アルゴリズム実装の引き出しを増やすことができます。

https://atcoder.jp/contests/typical90

① 解説を読んで解答方針を理解する。コードを記憶する
② 模範解答のコードを写経、解説コメントを記入
(この時 ①の短期記憶に頼り、なるべく解答は見ないようにする)
③ 一回写経したら3日間絶対に問題文も解答も見ない
④ 3日経ったら②を実施し復習
以降、②~④を繰り返す。

Notionを使って②~④でまとめた解説ページ

1722770382845-CrSjAyECn

「典型問題」を繰り返し解いて「実装の勘」を養うことで、問題文読んだ段階で解答方針が浮かぶようになっていきます。
(「あ、これ 2^N通りの全探索 だから DP で解けるなー」＞「 DPってどうやるんだっけ？チートシート確認しよ」みたいな感じ」)

(余談)③~④学習方法は「スペースド・リピティション(間隔反復学習)」と言うらしく、科学的根拠に基づいた学習法です。(実際、筆者の知識の定着も早かった気がする。そう、気がする。。)

https://emprony.com/skillpocket/importance_repeated_learning

2ヶ月後(目標達成！！)

1722770215943-xRedjrTrz31

AtCoder Beginner Contest 364 にて茶色レートになることができました！
この時点ではまだまだ解けないC問題たくさんありましたが、

プログラミング言語の基礎文法を理解していること
アルゴリズムを用いた基礎的なデータ探索が独力でできること

の客観的証明には足りているかと。

次の目標

次の目標は 「１年以内に緑レートになること」です。
また、私が先人の解説記事に助けられたように、今度は私自身が解説記事を発信する立場になりたいものです。(そのための実力を身につけるが先ですが)

最後に~初心者こそ競プロをやれ~

なんやかんやあり、無事に「効率的に入茶を達成」することができました!

プログラミングを学びたいけれど作りたいものがない。。

わかります。。
できること、実現手段 が明白になっていないとやりたいことってなかなか浮かばないですよね。。

でも、プログラミングは勉強したいんだ！

そんな人に、学習の入り口として 競技プログラミング を知ってもらえたら嬉しいです！

この記事が筆者のような初学者の一助となれば幸いです。

ぜひ、良き競プロライフを( ^_^)/