競技プログラミングのはじめかた

## はじめに

今年も何かエンジニアとしての学習を進めるぞということで元日から 1 か月間競技プログラミングに挑戦してみました。

競技プログラミングをはじめました的な記事は数多とあるかと思いますが、私の場合の所感を残すことでこの1か月の振り返りをしたいと思います。

## 実は初めてではない競技プログラミング

これは結構あるあるな気がするのですが、競技プログラミングってやり始めたはいいもののすぐに挫折してしまったという方も多いのではないでしょうか。私もそのタチで、学生時代や新卒時代に何度か初めようとしてすぐに諦めてしまったという経験があります。

今回こそはちゃんと競技プログラミングを身に着けたいと思ったので、**なぜ今までは 3 日坊主になってしまったのかを深堀りしてみたところ「動機づけ」と「解説書」の 2 点がポイントになりそうだと分かりました**。

## 競技プログラミングをやる動機

そもそも競技プログラミングをやる動機はなんでしょうか。「ゲームのように楽しむ」とか「スキルアップのため」などと一般的には言われていますが、もう少し具体的に**自分にとって競技プログラミングが何を意味するのか** を考えてみました。

私の場合は次の 2 点が動機になると思いました。

### 将来外資系で働きたいという夢のため

GAFAM などに代表される外資系のテック企業では選考の過程に必ず「コーディング」が含まれます。また国内であっても Mercari, PayPay, DeNA, リクルート あたりのレベル感の企業では「コーディング」があります。

アルゴリズムとデータ構造といったコンピュータサイエンスの基礎からの出題が必ずあり、日常の業務に近い分野からの出題がある場合もあります。将来の面接を確実に突破するために競技プログラミングをやることは自信につながるなと思いました。

ちなみに選考の過程で行われる「コーディング」はただ正解のコードが書ければ OK というわけではなく、どちらかというとどのように問題を捉えて方針を立て、面接官とコミュニケーションを取りながら回答にたどり着くかが見られているそうです。これは実際の経験ですが、例え半分くらいしか解けなかったとしても解く過程が評価されれば Pass できる可能性があります。

### エンジニアとしての実力を定量的に示すものとして

聞く場合も聞かれる場合も困るのが、エンジニアとしての実力です。「あなたはどのくらい優れたエンジニアなの?」と聞かれると意外と答えに困るのではないでしょうか。経験年数や保有資格、肩書き、学歴、職歴は参考になりますが、何か定量的にエンジニアとしての実力を示すものがあればと思っていました。

競技プログラミングであれば明確に順位やランクが付くので、自分がどの程度の実力があるのかをはっきりと示すことができると思いました。


## 競技プログラミングの解説書

動機づけに続いて競技プログラミングを継続するポイントの2つ目は良い解説書と出会うことです。

競技プログラミングの問題文って初めはとても分かりにくいですよね。解説を読んでもさっぱり分からないということがしばしばあると思います。最初の一歩を踏み出すための良い書籍がないかと探したところ、 **[アルゴリズム的思考力が身につく! プログラミングコンテスト AtCoder 入門](https://amzn.asia/d/cL3ioRL)** という本を見つけました。

問題のパターン数と解説が秀逸で非常に分かりやすく、問題を解くためのコツが凝縮されています。タイトルに入門とある通り本当に簡単なレベルからスタートし、最終的には動的計画法、貪欲法 あたりまで学習するこができます。私はこの本のおかげで「これなら競技プログラミングをやっていけそう」という手応えを掴むことができました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/56635/dbfc85ca-76e8-720e-d961-8b40c19ca1f4.jpeg" width="320" />

## 競技プログラミングを始める

### どの競技プログラミングサイトを使うか

動機づけと解説書が決まったので、競技プログラミングをさっそく始めることにしました。競技プログラミングのサイトは複数あって、どれを使えばいいのか迷ってしまいそうですが日本のエンジニアは **[AtCoder](https://atcoder.jp/?lang=ja) ** を利用するのが良いと思いました。理由は単純で、問題文が日本語であること、コンテストの開催時刻が日本時間基準であることです。

:::note info
海外の競技プログラミングのサイトには [Topcoder](https://www.topcoder.com/) や [Leetcode](https://leetcode.com/) などがあります。各サイトごとに出題の傾向がやや異なるため、一度登録していくつか問題を解いてみるのもいいかもしれません
:::


### プログラミング言語の選択

さて競技プログラミングのためのプログラミング言語には何を選べばいいのでしょうか。C++ と Python3 が人気言語ですが、**個人的には Python3 が良いと思いました**。理由は以下の 3 点です。

1. 記述量が少ない
1. コンパイルせずに手軽に実行できる
1. 競技プログラミングで頻出の処理を簡単に実現できる (`itertools` など)

C++ もアリだと思いますが、まずは Python3 で競技プログラミングに慣れてから C++ への移行を検討するのがよい気がしています。また、普段使っているプログラミング言語を選択したくなるところですがこれはあまりおすすめしません。私の場合普段使っている言語は Kotlin になりますが、選択しない理由は以下です。

1. 記述量が多くなりがち
    * 変数を作るだけでもこれだけの違いがあります(Python: `a=3` Kotlin: `val a=3`)。ちょっとしたプログラムを短く簡単に記述できるかどうかを競技プログラミング向きの言語かどうかの基準として考えるとよいと思います。
1. 解説コードが Kotlin で書かれていることが滅多となく、自分の頭で読み替えながら理解する必要がある
    * AtCoder 公式や個人ブログ等での解説の多くは C++ や Python3 が用いられています。違う言語で書かれたサンプルコードを読むのは少し大変です。

## AtCoder を始める前に知っておきたかったこと

ついに AtCoder デビューをした私ですが、もっと早く知りたかった...と思ったことがいくつかあったのでまとめたいと思います。

### AtCoder Beginner Contest という名前の割に問題が難しい

定期開催のコンテストで AtCoder Beginner Contest(ABC)というものがあります。名前に Beginner と付いているし楽勝でしょ！と思ったら違いました。A 問題 B 問題あたりは競技プログラミングを知らなくてもまあ解けるレベル、C 問題 D 問題は上記で紹介した解説書で勉強していたらまあ解けるレベル、E 問題 F 問題は現時点では解ける気がしないレベルです。

名前に Beginner と付いていますが後半は結構難しい問題なので、最初は A~D 問題を解けるようになれば御の字ということになります。

### Rating の色は茶でも十分すごい

AtCoder には Rating の色というものがあり、下から 灰 → 茶 → 緑 → 水... のようになっています。茶なんて地味な色だし大したことないんじゃないかと思いそうなところですが、実は茶でも結構すごいことなのです。初心者はまずは茶を目指しましょうと言われることが多いですが、結構すごいところを目指しているのだなと自覚できればやる気も出てきますよね。

Rateing の色ごとのレベル感についてはこちらのサイトが参考になります。

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

### 便利な補助サイトがある

AtCoder 本体のサイトは正直使い方が分かりにくく、例えば過去問がどこにあるのかもパット見では分かりにくいです。そこで活用したいのが **[AtCoder Problems](https://kenkoooo.com/atcoder/#/table/)** というサイトです。

このサイトのすごいところは過去問を一覧できるだけでなく、問題ごとに Difficulty という独自の難易度スコアがつけられている点です。この Difficulty を目安にして自分が目指したいレベル感の問題を簡単に見つけることができます。

また自分の AtCoder の User ID を入れることで自分が解けた問題と解けなかった問題を可視化することもできるので復習をする際に便利です。

![atcoder_problems.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/56635/afea203d-9f2d-f79d-d9bd-4a7f683258c7.png)



### コンテストは主に土曜もしくは日曜日の夜に開催される

土日の夜ってプライベートの予定が入りがちだと思うのですが、AtCoder のコンテストも土日に開催されます。つまり土日の夜にお酒飲めなくなります。なので私はプライベートの予定を優先しつつ、たまにコンテストに出られたらいいなくらいのスタンスにしています。これくらいのスタンスの方が、うっかりコンテストに出場し忘れたみたいなことがあったとしても落ち込まなくて済むのかなと思います。

### Python は処理系によってパフォーマンスが大きく変わる

あるときコンテストの問題を解いていて、明らかに正当なのに TLE(Time Limit Exceeded) になるという事件がありました。計算量を何度見積もり直してもやはり間違いはない。理由を考えた挙げ句、試しに処理系を Python3 から PyPy3 に変更したところ何ごともなかったかのように AC になりました。

コンテスト終了後に調べたところ、条件にもよりますが PyPy の方が数十倍高速なようです。ただし、Python3 の方が高速な場合もあります。詳しくはこちらの記事を参考にしてみてください。

https://qiita.com/y-oksaku/items/f0c5c4681bc30dddf7f4


## 競技プログラミングを 1 か月やってどうだったか

競技プログラミングを 1 か月やってみての振り返りをしたいと思います。

### AtCoder のコンテストに 2 回参加し、灰色コーダーになった

ABC と ARC に 1 回ずつ参加しました。ABC は奇跡的に D 問題まで解くことができ、ARC も A 問題を解くことができました。このままコンテストの参加を続けていけば、茶色コーダーになる日はそう遠くなさそうです。目標を茶色の一つ先の緑に変えてもいいかなと思っているところです。

### Python3 のコードをすらすら書けるようになった

Python3 は予想よりもずっと早く習得することができました。エディタ・IDE には **[PyCharm Community Edition](https://www.jetbrains.com/ja-jp/pycharm/)** の利用をおすすめします。使いやすいデバッガもあるので、コードの挙動を追うのも簡単です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/56635/d3d262ac-f40d-3a2a-b39e-b3d87c2a1b82.png)

https://www.jetbrains.com/ja-jp/pycharm/

### 日頃から計算量を意識できるようになった

日頃の業務で Android アプリのコードを書いていて、計算量を意識する必要がある場面は皆無です。しかしながら、競技プログラミングを学び始めたことで時間計算量・空間計算量を意識する癖がついたように思います。うっかり非効率なコードを書いてしまうことは今後なさそうです。

### 競技プログラミングに対する抵抗が無くなった

何となくこれまで競技プログラミングに対して抵抗感を感じていた私ですが、自分でも競技プログラミングができることが分かりました。苦手意識がなくなったのはとても良かったと思っています。

### 面接のコーディングテストに自信を持って臨めるようになった

最近面接の中でいくつかコーディングテストを実際に受けたのですが、ほとんどの問題をスムーズに答えることが
できました。1 か月程度勉強しただけでもコーディングテストを突破できるだけの十分な技術を身につけられたので、面接でコーディングテストがある場合は少し前から時間を取って対策をしておくと良いと思います。

## まとめ

競技プログラミングをはじめた目的や、学習の進め方、効果などについてご紹介しました。競技プログラミングはきちんと目標を立てた上でやれば実に面白く、仕事やキャリアにもきっと良い影響を与えるでしょう。この記事をきっかけにご自身のペースでチャレンジしてみてはいかがでしょうか。