競技プログラミングって何? (はじめての高校生向け)


競技プログラミングって何?

競技プログラミングは、プログラミングを使ってパズルを解くスポーツ



どんな人にオススメ?


  • プログラミングを使って何かソフトウェアを作るより、プログラミング自体が好き

  • パズルゲームや謎解きが好き

  • プログラミング学んだけど、プログラミングですることがない

  • プログラミングを就職や進学に活かしたい

  • アルゴリズムやデータ構造を本格的に学んでみたい



一番重要なこと

競技と言っても何より楽しむが重要!



最初は自分の実力に合わせて楽しむ!


  • すごい人を見すぎない

  • 自分が「できたこと」を喜ぶ

  • 小さい目標を立てて、コツコツやってく

  • 楽しめなくなったら休むのも重要



実益もあるよ


  • いい成績を収めると大会で優勝賞金


    • 高校生のパソコン甲子園だと30万円とか

    • Google Code Jam など大会だと、賞金25万ぐらい、上位者Tシャツなど



  • 筑波大学のAC入試や慶応大学のAO入試などで活動実績として紹介できたり、慶応大学、首都大学東京、会津大学の特別推薦入試枠がもらえることも

  • ドワンゴの大会など出てるとエンジニア就職面接で一次面接を免除、他の企業も就職やインターンに繋がるコンテストが沢山あるよ



高校生向けの有名な大会

こんなのがあるよ。



パソコン甲子園の予選はN高等学校(全国にあるキャンパス)でも開催 (N高生向け情報)


  • 初心者でも予選参加OK、チャレンジすることで良い経験になる

  • 2人チームで参加

  • チーム募集は Slack の #club_computer まで



今日ははじめての競技プログラミングにチャレンジ

今日やることは以下の通り


  1. 環境構築

  2. プログラミング言語 C++ について

  3. 競技プログラミングのコンテストの Web サービス AtCoder にチャレンジ

※ただし、プログラミングに関しての基礎は知ってるものとする、N予備校入門コース2章4節程度までレベル



競技プログラミングの環境構築

g++ というプログラミング言語 C++ を利用するためのプログラムを使うのでそのインストールだけする。



  • Linux 環境で g++ コマンドをインストール (N予備校 入門コース 2章4節まで進める)




  • Mac 環境で XCode をインストールして g++ コマンドインストール


    • XCodeをApp Storeアプリでインストールして一度開けばOK






環境構築の確認

それぞれコンソールを開いて

g++ --version

を入力。Linux なら (バージョンは違ってもOK)

g++ (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609

Mac なら (バージョンは違ってもOK)

Apple LLVM version 8.1.0 (clang-802.0.38)

と表示されればOK。



g++環境が用意できてない場合

Linux なら

sudo apt-get install g++

でg++をインストール。確認の[y/N]でyを入力してインストール。

MacならばApp StoreよりXCode をインストールして一度起動しておこう。



コーディングする環境

エディタを使う人が多い。

エディタは VS Codeがおすすめ。

ただパソコン甲子園本選は、TeraPadというエディタ。スーパーコンと情報オリンピックではVimかEmacsなので大会考えてる方はVim/Emacsになれるのも良いかも。

Windows の人は Visual Studioとかの統合開発環境(IDE)も便利。



競技プログラミングで使う言語 C++


  • ほとんどの場合 C++ というプログラミング言語。



C++ って何?


  • 他のプログラミング言語に比べて速度が早い

  • 速さが求められるソフトウェアなんかによく使われる

  • コードを書いたあとに、コンパイルということをして、そのマシン向けの機械語と呼ばれる形式に変換して実行する

  • このコンパイルをするのが環境構築で用意した g++ というコマンド



C++ の文法の最速マスター


  • for 文、 if 文、while文なんかは JavaScript とほとんど一緒

  • 変数宣言と関数宣言が少し違う。var とか function の代わりに変数宣言、関数宣言の前に戻り値の型というデータの種類を宣言する必要がある

  • C++0x基礎文法最速マスター 」がオススメ



便利な標準ライブラリもたくさんある



みんなで Hello World! を表示するプログラムを書いてみよう


  • hello.cpp ファイルを作って以下のように編集

#include <iostream>


using namespace std;

int main() {
cout << "Hello World!" << endl;
}


書いたら、コンソールで

g++ -o hello hello.cpp

./hello

で実行。これは、 hello という名前のプログラムにコードをコンパイルして機械語に変換してから実行している。 Hello World! って表示されればOK。



基本的なプログラムの作り方



  • #include <iostream> は、標準入出力を行うライブラリの読み込み


  • using namespace std; は、std という名前空間の利用の宣言

  • 関数の宣言は function の代わりに int (整数型) というものを使う

  • かならず main という名前の関数を使ってプログラムを実行



標準出力を使ったコンソールへの出力


  • cout はconsole output (コンソール出力) を表したオブジェクト


  • cout << "Hello World!" << endl; で、


    • cout に対して、 "Hello World!" とう文字列を渡す

    • cout に対して、endl で末尾改行 を渡してる





数値を2つ受け取ってそれを足す


  • add.cpp ファイルを作って以下のように編集

#include <iostream>


using namespace std;

int main() {
int a, b;
cin >> a >> b;
cout << (a + b) << endl;
}

を書く。


書いたらコンソールで

g++ -o add add.cpp

./add

で実行。2つの数値は、空白、改行、タブキーのいずれかで読み込めばOK。 12 3の場合。

12 3

15

などと足した結果が出てくる。



C++ についてはこれで OK

それでは、競技プログラミングにチャレンジしてみよう!



AtCoder について



Practice Contest をやってみよう


  • http://practice.contest.atcoder.jp/#

  • 問題 A だけで OK

  • サイト内の問題タブを開いて、提出からコードを出して見ましょう。

  • 結果で AC が出れば OK



AtCoder Beginner Contest 050 (ABC050) をやってみよう



AtCoder Beginner Contest 051 (ABC051) をやってみよう


  • http://abc051.contest.atcoder.jp/

  • 問題 A, Bだけで OK

  • サイト内の問題タブを開いて、提出からコードを出して見ましょう。

  • 結果で AC が出れば OK



AtCoder Beginner Contest 052 (ABC052) をやってみよう


  • http://abc052.contest.atcoder.jp/

  • 問題 A, Bだけで OK

  • サイト内の問題タブを開いて、提出からコードを出して見ましょう。

  • 結果で AC が出れば OK



今後もしウデを上げたい時


アルゴリズムを網羅的に演習したい時


  • アルゴリズムを網羅的にやりたい人には、AIZU ONLINE JUDGE の問題セット > Introductionが勉強になるので似たようなシステムなのでこれもアカウントを取って最初からチャレンジしてみよう(Introduction to ProgrammingからLibrary of Number Theoryまでがオススメ)


無料でもっとウデを上げたいという人

drkenさんのまとめてくれている蟻本シリーズがオススメ。


もっと実力をつけるのに本を買ってもいい!という人



相当実力が付いてきたなと思ったら


  • 相当実力が着いてきたなと思ったら、 AtCoder Regular Contest も解いてみよう。

  • もっと競技プログラミングがしたくなったら、海外のCodeforcesTopCoder SRMHackerRankなどもオススメ。


    • 英語だけれど自動翻訳でなんとかなる。英語の勉強にもなるので翻訳して慣れるのも吉。



  • セキュリティ分野向けのコンテストで CTF などもあるのだけどもそれはまた今度紹介していきます〜。