[AtCoder]入緑しました！競プロ始める前~入緑までの道のり

はじめに

初めてQiitaで記事を投稿させていただきます！Cecilと申します！最近、AtCoderにて緑色になることができたため、その道のりをここに記します！

自己紹介

• 情報理工学科に所属するB2
• B1の夏休み頃に競プロを知る
• Pythonを主に使用している

競プロを始める前の話

私は大学に入学したらプログラミングの勉強をしたいと思っていました。その為、大学に入学後はPythonをメインに様々な書籍を読んだり、学習サイトなどで勉強をしていました。しかし、開発はおろかPythonの文法を理解することにすら苦戦していました。

競プロを始めた頃の話

Pythonの勉強をするなかで競技プログラミングの存在を知りました。問題が与えられてそれを満たすコードを作成することはプログラミングの勉強に効果的だと思い、競技プログラミングを始めてみることにしました。

まずは、AtCoder Beginners Selectionの問題をいくつか解いてみようとしました。このときの私は競技プログラミングについて何も知らず、Pythonもごく簡単な文法しか扱うことができなかったため、いくつか問題が生じてしまいました。

• 余計なコードを書いてしまう

当時、学校でもプログラミングの授業があり、そこでは入力の前に"Please input ~"みたいな出力をしていました。その癖で、競プロのコードを書く時もそんな感じの出力をしてしまい、よくWAとなっていました。なんだか懐かしいです。

• map(int, input().split())を知らない

このような入力が与えられるとき、「bとcってどうやって同時に受け取ればいいんだ？」とよく困っていました。入力形式について調べているとき、なかなかmap関数にたどり着けませんでした。

• Pythonの文法を全然理解していなかった

これが一番の課題でした。問題を解くためのコードを書くにあたり、for文やif文などの文法について調べながらでないとまともにコードを書くことができませんでした。コードを書く経験が非常に浅いため、何も見ずにコードを書くことができなかったのです。

まずはPythonの文法を勉強する

まともにプログラムが書けない以上、競技プログラミングの問題を解くことができません。そのためPythonの勉強を改めてすることにしました。ここで、活用していたのがアルゴ式というサイトです。

このサイトでは入力の受け取り方をはじめ、Pythonの基本的な文法について競技プログラミングに近い形で学習することができます。

次に、AtCoder Beginner Contest（以下ABCと略します）の過去問のA,B問題を解くなどをしました。これにより、Pythonの基本的な文法を何も見ないで書けるようになりました。同時に、ABCへ積極的に参加するようになり次の課題に直面します。

AtCoderの過去問はAtCoder Problemsというサイトで一覧表を見ることができます。過去問を見る以外にも様々な機能があって便利です！

計算量とアルゴリズム

ABCのA,B問題が順調に解けるようになり、C問題にも手を出そうとしました。問題文を読んで、「簡単だ！」と思った私は愚直にコードを書いて提出しました。その結果、TLEと表示されました。

当時の私はTLEが何なのか知らず、答えはあってるはずなのになぜ間違い扱いになるのかと混乱してしまいました。後に、プログラムを書く上でループの数や使用する関数により実行時間が変わり、制約の実行時間内に収まるように実装をしなければならないことを知りました。ここで出会ったのが、計算量とアルゴリズムです。自分が実装したコードはどれくらいの実行時間を要するのかを見積もるために計算量が必要で、より効率的に問題を解くためにアルゴリズムが必要であることを知りました。それらを勉強するにあたり、同じく競プロをしている友達に次の本を勧められました。

競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~ (Compass Booksシリーズ) https://amzn.asia/d/7CKAKzI

E869120さんの通称"鉄則本"です。この本には初心者が学ぶべき計算量やアルゴリズムについて体系的にまとめられており、効率的に学習することができました。まだ学びきれていないことも多く残っており、現在も重宝しております。

他にも、アルゴ式のデータ構造とアルゴリズムという項目を使って勉強したり、YouTubeに投稿されているアルゴリズムに関する動画などを使って勉強していました。

入茶までの過程

計算量とアルゴリズムを勉強し始めた私はABCで3,4完できるようになり、レートも徐々に伸びていきました。それに伴い、茶色を目指すようになりました。入茶までに行っていたこととしては主に次の3つがあります。

• 灰,茶diffのC,D問題埋め
  茶色を目指すにあたり、C,D問題が解けるようになる必要があります。その為、C,D問題で自分にも解けそうなレベルの問題を解くなどしていました。下のポストではすでに入茶していますが、入茶前から続けていました。

• バーチャルコンテストに参加する
  AtCoder Problemsではバーチャルコンテストで本番に近い形式の練習用のコンテストを作ることができます。私は主に"まよこん"と呼ばれるバーチャルコンテストに参加していました。出題される問題の難易度と時間がABCのように設定されており、コンテスト形式で練習することができました。

• アルゴリズムとデータ構造の勉強
  先ほども述べた通り、鉄則本やアルゴ式、YouTubeを活用してアルゴリズムの勉強をしていました。入茶までに身に着けたアルゴリズムとデータ構造としては累積和、二分探索、簡単なDP（ナップザック、部分和問題など）、DFS、BFS、union-find、連想配列、queue、stack、heapqなどが主に挙げられます。

そして、2023年7月15日に行われたABC310にて入茶しました！

入緑までの過程

茶色になってから緑perfも徐々に取れるようになりました。このまま緑も行けるのではないかと思い、緑を目指すようになりました。緑を目指すにあたり、主に次のことを行っていました。入茶までやっていたことと大きく変わっていないです。

• 緑diffのD,E問題埋め
  入茶時点で茶diffの問題をかなり埋め終わっていたため、緑diff前半の問題を解くようになりました。緑diff前半の問題で必要とされる知識について、当時の私が知っていたもので十分だったため、新しく学んだことは少なかったです。

• バーチャルコンテストに参加する

• AtCoder以外のコンテストに参加する
  競技プログラミングのコンテストを開催しているサイトはAtCoderだけではありません。yukicoderやCodeforcesなどのサイトでもコンテストは定期的に開催されています。これらのコンテストにも積極的に参加するようにしていました。

• アルゴリズムとデータ構造の勉強
  入緑までに新しく身に着けたアルゴリズムとデータ構造は少なかったです。主に、bit全探索、ダイクストラ、imos法、尺取り法、貪欲法などが挙げられます。

• AtCoder Regular Contestへの挑戦
  ABC以外にもAtCoder Regular Contest（以下ARCと略します）にも定期的に参加していました。ARCではABCよりも難易度が高く、考察力を求められる問題が出題されます。そのため、当時の私では1問も解けないことが多かったです。今もARCの問題は解けないことが多く、この記事を書く数時間前に参加したARC173も0完でした笑。しかし、難しい問題に対して2時間集中して考えることが楽しいため、なるべく参加するようにしています。

そして、2024年2月19日に行われたARC172にて入緑しました！E869120さんの本で勉強してきたため、E869120さんの作問する回で入緑できたことが感慨深かったです。

これまでの記録

2024年3月11日時点でのAtCoder Problemsの記録を載せておきます。

今後の展望

もちろん次は水色を目指します！それにあたり、次に記してある計画で精進していこうと考えています。やることが沢山あるため、優先順位をつけてやっていきます。これが正しい方針かは自分もわからないのでどなたかアドバイス頂きたいです。

おまけ

ここまで読んでいただきありがとうございました！以下は余談を記しておきます。

競プロを始めてから変わったこと

競プロを始める前よりも圧倒的にコードが書けるようになりました。実績を得ることもできました。具体的には以下のような実績があります。

• paizaでSランクが取れました！
  

• GCIを修了できました！
  

• 基本情報技術者試験科目B、800点以上
  結果が不合格なので実績とは言えないですが、このとき受験した基本情報技術者試験はタイミングが悪く、前日に参考書を眺めて過去問を解くくらいしか勉強できませんでした。しかし、科目Bの問題は競プロをやっている方にとって簡単だと思われる問題が出題されており、ほとんど試験勉強していない状態で高得点が取れました。
  

オンサイトコンテスト/ICPCについて

様々な大学のサークルがオンサイトで競技プログラミングを開催しています。ここでは、普段オンライン上で競技プログラミングをしている方々にリアルで会うことができます。つよつよ競プロerの方々と話すとモチベーションにつながると思います！

次に、ICPCについて述べます。

ICPC とは、ICPC Foundation (2018 年まではACM (Association for Computing Machinery) という計算機学会）が主催する、International Collegiate Programming Contest (国際大学対抗プログラミングコンテスト) という名前のプログラミングコンテストです。同じ大学で３人一組のチームを作り、チームでプログラミングと問題解決の能力を競う大会です。全世界で毎年3万人以上が参加する大会に成長しています。
引用元(https://icpc.iisf.or.jp/acm-icpc/)

2023年の7月頃にAtCoderのレート灰（私）、緑、水の3人チームで参加しました。私はA問題を担当し、無事にACしました。C問題も協力して考察しましたが、解法が思いつきませんでした。結果はA,Bの2完で予選突破とはなりませんでした。しかし、大会に向けてチームで練習したり勉強することは非常に楽しかったです。私と友達も、競技プログラミングで強くなるために日々精進を続けているため、今後のICPCでは予選突破を目指します。

一緒に競プロやってくれる友達、TLの皆さん

みんな頑張っていてすごいなと思っています！精進に関する投稿やコンテスト後の感想など勉強になります。また、わからないことがあった際に助けて頂き非常に感謝しています。これからもよろしくお願い致します！

最後に

私はこれからも競プロをやっていきます！最低限の目標は水色です！そこから先は自分の実力でどこまでいけるかわかりませんが、競プロを続けられる限り挑戦し続けます！

ここまで長くなってしまいましたが、読んでいただきありがとうございました！