競技プログラミング ことはじめ

プログラミング始めてみたけど、なんかコピペばっかで思ってたやつと違う...
もっとカタカタ...ｯﾀｰﾝ みたいなプログラミングがしたーーーーい！！！

今回はみなさんの願いを叶えられる(かもしれない)、競技プログラミングをご紹介します。

趣味としても楽しいし、就活や転職でも役立ちますよ。

競プロとは

例えば、こんな問題があるとしましょう。

・数字が2つ入力されるので、これらを掛け算してください
・英語の文章が入力されるので、"Hello"という単語がいくつあるか数えてください

参加者は、これをプログラムを用いて解き、そのプログラムを提出します。

問題を解いて解答を提出するのではなく、「その問題を解けるプログラムを提出する」という感じです。

面白そうですね。実際にやってみましょう。

実際にやってみる

まず、問題を解くに先立って、プログラミングができる環境を作る必要がありますね。

今回は、PCまたはiPadなどで簡単にできる方法をご紹介します。
慣れてる人は全然好きな環境使ってもらって大丈夫です。

step1

問題文を画面左側に配置します。今回はこのページを配置してください。

step2

https://paiza.io/ を開いて、「コード作成を試してみる(無料)」というボタンを押し、

左上のボタンから Python3(またはお好きなプログラミング言語) を選択します。

これを画面右側に配置したら準備完了です！！
早速問題を解いてみましょう。

練習問題

1年が M ヶ月、1ヶ月が D 日からなる異世界があります。

その異世界で y 年 m 月 d 日の翌日は何年何月何日であるか求めてください。
入力は以下のように渡されます。

M D
y m d

面白い問題ですね。こんな感じで解けるでしょうか。

###入力-------------------------------
M,D   = map(int,input().split())
y,m,d = map(int,input().split())


###翌日が何年何月何日か計算--------------
d += 1

if d > D: #翌月への繰り上がり計算
  m += 1
  d = 1

if m > M: #翌年への繰り上がり計算
  y += 1
  m = 1


###出力-------------------------------
print(y,m,d)

一応入力の部分だけ解説しておくと、

input().split()

とすることで、たとえば2 5みたいなスペース区切りの入力を"2","5"のように受け取れるのですが、このままでは"2"と"5"は文字列として扱われていて、数字として計算できないので、

map(int,input().split())

とすることで、ちゃんと計算できる数字が受け取れます。
これと、list(map(int,input().split()))はめっちゃ使うので覚えておくと良いです。

試してみる

それじゃ、今作ったプログラムがちゃんと動くか試してみましょう。
いま画面の右側に表示されているであろうpaiza.ioにコードを貼り付け、下の「入力」タブに

12 30
2023 12 30

とか、

36 72
6789 23 45

と入力してみましょう。そしたら出力は

2024 1 1

6789 23 46

のようになるはずですね。

提出する

実は今やってもらった問題は、AtCoderという会社が毎週土曜日に開催しているAtCoder Beginner Contest(通称ABCコンテスト)の過去問でした。

せっかくですので提出してみたい！という方は提出してみましょう。

① https://AtCoder.jp の右上のボタンから、新規登録/ログインをします。

② 「コンテスト一覧」の終了済コンテストから、「大和証券プログラミングコンテスト2023」を探します。　まぁ探すのが面倒な人は、ここです。

③上の「問題」タブから、 A - Tomorrowを開き、下の方にスクロールすると、プログラムを提出する場所があります。

④「言語」から、どれでもいいのでPythonを選び、コードを貼り付け、提出ボタンを押します。

⑤提出できた！！！やった！！！！！
⑥画面が切り替わり、「結果」のところに結果が表示されます。すごい。
結果の確認方法は、
AC : 正解
WA : 不正解
CE : 不正解(実行中にエラーが発生)
TLE : 不正解(処理に時間がかかりすぎたため中止)

とかがあります。

何の役に立つん

思ったより簡単じゃん。でも何の役に立つんですか？これ。

答えは、コーディング能力が伸びる です。
先に言っておきますけど、例えばDockerを使った環境構築とか、顧客の要求を満たす要件定義とかは競プロで身につきません。そりゃそうだ。

でも、コーディング能力を伸ばせば、エンジニアとしてある程度の価値は担保されるでしょう。

実際に、Yahoo株式会社の募集要項(2023年9月30日時点)では、競技プログラミングのレートが加味されていました。

まぁ、AIがどうのこうのでエンジニアがコード書くのはうんぬんかんぬん〜〜とかいう話はありますが。

少なくとも、制作物やポートフォリオがなくて就活に困ってる学生とか、自分のコーディング能力を可視化したい人なんかには、かなり強くお勧めできます。

各競プロサイトの比較

競プロサイト、わりとたくさんあるので、それぞれの特徴や所見を紹介します。

AtCoder

さっき解いてもらったやつ。特に理由がなければ、これから始めるのがおすすめです。

・日本語対応

・基本は毎週土曜21時にコンテストを開催

・Beginner, Regular, Grand コンテストなどがあり、自分のレベルに応じて参加するかしないか選べる

・レート0~400は灰色、400~800は茶色...みたいに、強さが色分けされている

・過去問が公開されており、いつでも解ける。また、コンテスト終了後は他の人が提出したコードを見ることができる。

・AtCoder Jobsという、AtCoderのレート等を利用した就職・転職サイトがある。 僕は後述のPaizaしか使ってないけど、これもかなりおすすめ。

CodeForces

あんま知らないけど面白そう。世界的にはAtCoderより有名なハズなので、英語で就活して外資系とか目指すぜみたいな人には、おすすめかも？？

・英語とロシア語に対応
・日本時間の23:35〜や0:35〜から2時間程度開催されることが多い
・これもレートによって色分けがある
・これも過去問は解けると思う。多分。
・コンテスト中に、他人のコードの脆弱性を攻撃するシステムがある。これが最大の特徴。詳しくは調べてね。

Paizaスキルチェック

さっき画面右側でコードを実行するのに使った"Paiza"運営のやつ。
競技プログラミングとは違うんだけど、就職や転職をするなら一番おすすめです。

・Cランク問題を一問でも解けばCランク、S問題を一問でも解けばSランクに昇格できる

・コンテストとかはないのでいつでも昇格チャレンジができ、制限時間も無いようなものなので1問にじっくり時間をかけられる。

・Paizaラーニングというサイトがあり、競プロやWeb制作、機械学習の教材が揃ってる。

・ちゃんと自己PRを書き、たくさんログインしていて、AランクとかSランクになっていると、めっちゃスカウトが来る。 これか先述のAtCoder Jobsは、職を探しているならぜひ登録するといいよ

Track Job

これも競技プログラミングとはちょっと言えない気もしますが、一応紹介しておきます。基本的に企業と提携して、不定期でコンテストみたいなのを開催してるっぽいです。

・特にランクとかはない

・プログラミングテストに参加して、上位はインターンに招待！とか選考スキップ！とかが多い感じ

・他のサイトと似たアルゴリズム問題もあるが、飲食店の会計システムを実装せよ！みたいな、業務志向の問題が多数あり、また違った経験が積める。

他にもTopCoderとか、いろいろあります。

練習方法

とりあえず、AtCoder Beginner Contestの過去問A問題から順番にやっていくか、PaizaスキルチェックのDランク問題から順にやっていくのがいいです。大まかな解き方とか難易度を紹介しますね。

ちなみに

競プロにおけるプログラミング言語はPythonかC++がメジャー。
それぞれの特徴は、

Python : 初心者向け。わかりやすい　記述量が少ない
C++ : 実行速度が速い。

といった感じです。

ABCコンテストA問題 または Paiza D,Cランク問題

この辺は、基本的な入出力やif文、for文が使えば解けます。
難しいと感じる人も、数をこなせば必ず解けるようになります。

ここで鍛えた入出力が後々役に立つので、解説や他の人の提出を見ながら、安定して解けるようにしていきましょう。

ABCコンテストB問題 または Paiza Bランク問題

この辺は、問題文が難しそうに見えても、二重for文などを用いてありうる全パターンを試せば解ける問題が多いです。

例えば、卵をN個買うとき最小何円で買えるか？という難しそうな問題があったときに、ありうる全パターンを試して一番安かったパターンを出力する方法とかがあります。

競プロ的には全探索と呼ばれる手法です。僕はゴリ押しと呼んでいます。

ABCコンテストC,D問題 または Paiza A,Sランク問題

この辺から、計算量や典型的な手法を理解していないと解くのが難しくなってきます。

例えばAtCoderの問題は大抵が2秒以内に処理が完了するプログラムでないとTLEという種類の不正解になってしまいます。

Pythonだと2秒間にできる処理は10^6回(C++は10^8回)ぐらいらしいので、例えば

・実行時間制限2秒
・入力が10^5個ある

というような問題では、1重for文は使えるけど2重for文は使えないな、とか分かります。

あとは典型手法ですね。DFS,BFSとか動的計画法(DP)みたいな名前がついているプログラミングの手法や、ユークリッドの互除法、合同式なんかは役に立ちます。僕はアレルギーが出ます。

計算量について勉強したい方は、オーダ記法について調べてみましょう。
アルゴリズム等を勉強したい方は、Paizaラーニングのレベルアップ問題集やこういったサイトで勉強しましょう。

それ以降

僕がこれ以上のレベルに行ったことがないので、正直分かんないです。
というか、ここから先は「こうやって練習するのが正解だよ!!」とかは特にないです。自分の得意分野を武器にして、自分に合ったやり方で精進していきましょう。そして僕の師匠になってください。

どのレベルを目標にすべき？

僕はPaiza Sランク、AtCoderはC,D問題が解ける時もあるという感じなんですが、日本企業の新卒採用におけるコーディングテストはほぼ大丈夫だなという感じでした。


就職という面だけで考えれば、AtCoder茶色~緑色(レート400~800くらい)を目指し、あとは長期インターンとかで実務経験を積んだほうがいいと思います。実際の業務ではたいしたアルゴリズム使わないことも多いし、ね。

しかし、一部業種(最適化や大量のリクエストを捌くような業務とか?)や大手企業では、茶色や緑色では目を見張る人材とは言えない気もするというのが正直なところです。

そういったところを目指す方はより競プロに比重を置いて、高みを目指してみるのもいいかもしれないですね。

おわり

いかがだったでしょうか。
僕が最近就活に追われてたので就活の話多めになっちゃいましたが、普通に楽しいのでみんなやろうね。競プロ