Arc's blog

競プロなど

競技プログラミングを始めよう

追記: 2020年版を書き直しました

Arcです。今日はレビュー記事じゃない事を書きます。

新年度、なにか新しいことを始めたいと思っているそこのアナタに向けた布教記事です。

対象読者層

  • 問わず

できるだけ専門用語を使わずに書いていこうと思います。

競技プログラミングって何それおいしいの?

人に説明するのが難しいんですが、僕が思うに競技プログラミング(以下「競プロ」)は「プログラミングをして様々な問題を解くスポーツ」です。食べ物ではありません。

競技性はもちろんあるし(競技プログラミングなんだからそれはそう)、生涯スポーツとしても有用です。

競プロには大きく分けて2つの楽しみ方があります。1つは「過去問を解く」こと。もう1つは「コンテストに参加する」ことです。

コンテストは「競プロの大会」。与えられた問題を解くプログラムを速く作る事が求められます。「解いた問題の難度」、「問題を解くのに掛かった時間」で順位が決められます。

また、過去にコンテストで出題された問題の多くは(全ては?)そのまま公開され続けるので、様々な問題を解きまくるのも楽しいです。

競プロの効果は?

C++が身につく

競プロではこのプログラミング言語が主流です。世界で幅広く使われています。

C++は「C言語」の上位互換言語なので、初めにC言語を学習してからC++へステップアップする、というやり方でもOK。僕はそうしました。C++はメチャクチャ複雑な言語なので、最初からC++だと言語習得で挫折しそう……。C言語C++よりはシンプルです。

高度なプログラミング能力が身につく

競プロer(競プロをする人のこと)は世の中の平均的エンジニアと比べて相当高いプログラミング能力(特にアルゴリズム分野における能力)を持っているようです。ハイレベルな能力が自然と身につきます。

「競プロ界の『下の上』ぐらい」だと思っている自分がどこらへんのポジションにいるのかは分からない。

楽しい!!

最終的にはここに帰着します。高難度問題を解けたときの快感はたまらない。

どんな問題が出るの?

よしよし、ここまで読んでくれたということは興味を持ってくれたということですね?嬉しいです。具体的にどんなことをしているのか紹介します。

簡単な問題

たとえばこんな問題

競プロの問題は、「時間制限・メモリ制限」「問題文」「入力」「出力」「制約条件」から成り立っています。

「問題文を読む」→「入力で与えられるデータを適切に処理して、形式通りに出力するプログラムを書く」→「書いたプログラムを提出する」というのが一連の流れです。

また、入力される値は「制約条件」に従っています。これが無いとメチャクチャ大きな値を入れられてしまうので……。

さらに、「時間制限」「メモリ制限」を守ったプログラムを書かなくてはなりません。

「時間制限2秒」の場合、プログラムを実行してから2秒以内に出力する必要があります。効率の悪いプログラムを書くと時間制限に引っかかってしまいます。競プロは効率化との戦い。

「メモリ制限128MB」の場合は、変数を格納する場所であるRAMメモリの使用量を128MB以内にする必要があります。専門用語が漏れてしまった。とりあえず理解できなくても大丈夫です(そのうち理解する必要はありますが)。

では、この問題について考えてみましょう。

入力Aと入力Bを受け取る

(A*B)の値と、(A*2+B*2)の値を出力する

というプログラムを書けば良さそうですね。

この処理を記述して、サーバーに提出すると、サーバーがプログラムを実行してくれます。しばらく待つと、正解したかどうかが通知されます。「AC」と通知されたら正解。やったね。

難しめの問題

こんな問題も出ます。

初見で解けたら才能あります。保証します。

ほとんどの人はわからないと思います。僕も全然解けませんでした。でも、なんだかんだ言って解けるようになります。解けます解けました。

難しい問題をあーだこーだ考察するのが競プロの醍醐味、だと個人的には思っています。

どこで競プロができるの?

ざっくり分けると「ウェブ」と「オンサイト」です。

ウェブ

ブラウザでアクセスする形式。有名なサイトを幾つか紹介します。

AtCoder (たぶん)日本最大手の競プロサイト。毎週末にコンテストが行われています。僕も参加しています。いくつかレビュー記事書いてるので読んでね(露骨な宣伝)

Aizu Online Judge 通称AOJ。会津大学が運営している競プロサイト。後述の学生向けオンサイトコンテストで出題された過去問が充実しています。いわゆる「典型問題」もたっぷり。

yukicoder 問題を「出題できる」ことが特徴。僕も何か作ってみたい。

オンサイト

参加者が会場に集まって行うタイプ。「ウェブ上で予選コンテスト」→「オンサイトで本選コンテスト」といったパターンが多いです。

学生向けオンサイトコンテストを紹介します。

日本情報オリンピック 通称JOI。日本の高校生以下競プロerが参加できるコンテスト。ウェブで予選を行った後、最大80人ぐらいが本選へ出場できます。本選上位20人は「春合宿」に参加できます。

国際情報オリンピック(リンクは2018年日本大会) 通称IOI。世界屈指の高校生以下競プロerが出場するコンテスト。日本からは、前述の「春合宿」でいい成績を収めた上位4人(2018年のみオープン参加枠4人追加)が出場できます。

ACM国際大学対抗プログラミングコンテスト 通称ACM-ICPC、もしくはICPC。大学生競プロerが参加できるコンテスト。チーム戦であることが特徴。こちらも多くの予選を突破しないと世界大会には出られない。出てみたいです。

この他にも、IT系企業がオンサイトコンテストを主催したりしています。

必要なものは?

最低限、インターネットに繋がるPC1台でOK。ソフトウェアはいろいろインストールしないといけませんが……。

あとは問題考察用に紙とペン、リフレッシュ用に飲み物とかお菓子とか。

競プロしてみたい!

やったぜ。

そんなあなたに僕のオススメ学習法を伝授します(あくまで個人の意見ですが)。

以下、Amazonへのリンクを張りまくりますが、アフィリエイトでは無いことを一応書いておきます。

プログラミングの環境を整える

まずはPCでC言語C++を扱えるようにセットアップします。

……といっても、ここらへんについては「ググれ」としか言えません。使っているPCによってやり方が異なるので……。

流石にこれだと投げやりすぎるので、いくつかアドバイス。最低限必要なソフトウェアは

です。以上2つが1つのソフトウェアとしてまとまっている「IDE統合開発環境)」というのもあります。

使っているPCのOSとかにあわせて好きなものをインストールしてください。

とりあえずC言語を使えるようにする

前にも書きましたが、最初からC++を使おうとすると挫折する危険性があります。とりあえずCから始めましょう。

おすすめの教材はこちらの苦しんで覚えるC言語。だいぶ怪しげなタイトルですが、中身は非常に良いです。

よくあるC言語入門本だと「おまじない」とかいうファンタジーワードが羅列されているんですが、この本はそういった類の言葉を一切使わずにきちんと説明してくれることが特徴。「苦しい」と思うことはあっても、その後の理解度が半端じゃない。

「苦しんで覚えるC++」があったらC++から始めても問題ない、と言いたくなるぐらいの名著です。

簡単な問題を解いてみる

大体分かってきたな、と思ったら今度はアウトプットしましょう。全て理解してから、じゃなくても大丈夫。

基本的なことを学べば、簡単な問題は解けるようになります。

AtCoder Beginner Contest(通称ABC)にも出てみましょう。

(20180315 追記)

ここらへんのレベルまで辿り着いた方には、こちらのAtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~(drkenさん著)を読んでおくことをオススメします。AtCoder登録からABC参加の利点、重要過去問のピックアップ&解説までサポートしてくれます。

(追記ここまで)

アルゴリズムに手を出す

解けない問題に直面し、解説を読んでも「幅優先探索」「累積和」「動的計画法」とかいう謎ワードが並んでいて分からない……。

そういった感じになってきたら、「アルゴリズム」「データ構造」について勉強する必要があります。ようこそ競プロの真髄へ。

アルゴリズム」とは、「プログラミングで問題を解くための手段」の事です。

「データ構造」とは、「プログラミングで効率的にデータを処理するための形式」の事です。

とりあえずこちらのなっとく! アルゴリズムを読んで雰囲気を掴みましょう。この本も名著だと思います。すげーわかりやすい。イラストがたくさんあるので視覚的にアルゴリズムを学べます。中身のソースコードPythonという言語で書かれていますが、そこは分からなくてもなんとかなります。

今度はこちら、プログラミングコンテストチャレンジブック。通称「蟻本」。競プロerで持っていない人はいないんじゃないかと思うぐらいの「聖書」。主要アルゴリズムとデータ構造が網羅されています。

また、僕は持っていないのですが、プログラミングコンテスト攻略のためのアルゴリズムとデータ構造も良さげです。借りて読んでみた印象だと「なっとく! アルゴリズム」の内容をもう少し深めた感じ。

C++に手を出す

アルゴリズムに手を出すと同時に、C++の習得も目指していきます。

でも、「Cを学んだ人向けのC++入門本」を見たことがないんですよね……。僕はオンライン資料を読みまくることで乗り切っちゃいました(嘘です)

(20180306 追記)

オンライン資料で乗り切ろうとしていますが、そもそもC++を完全に理解するのは不可能レベルだという話もちらほら。

使う機能だけ理解しておけばいいと思います。

(追記ここまで)

ちなみにC言語でもJOI予選は突破できますよ。僕がその一人です。C++の方が圧倒的に便利だということに気づいたのは突破後の話。

この後

あとはひたすらアルゴリズムとデータ構造とC++の勉強して、コンテストに出まくるだけです。

これ以上書けと言われても書けない(´・ω・`)

どんどんコンテストに参加して実力を付けていきましょう。

まとめ

新年度の幕開けが近いということで、新生活のお供になるかもしれない記事を書いてみました。長文にお付き合い頂きありがとうございます。

以上で布教は終わり。この記事が、あなたが競プロの魔境に迷い込む世界に踏み出すきっかけになる事を祈ります。

更新情報

20180305/投稿

20180306/「プログラミングの環境を整える」追加、「C++に手を出す」追記、その他誤字修正

20180315/「簡単な問題を解いてみる」追記