競プロやろうぜ！

きょーぷろやろうぜっ！ 坂ラッシュ(@sakaiine)

Section 1 きょーぷろって何？ 2

プログラミング プログラミングとは プログラムを書くこと 3

プログラムを書くと いろんなものが作れます 4

競技プログラミング（競プロ） • 与えられた問題を正しく、十分な速さで 解くようなプログラムを作るゲーム（競技） 入力 4 課題 例：与えられた自然数の入力を 3で割った余りを出す プログラムを作成せよ 出力 1 プログラム 入力 8 出力 2 5

「正しい」とは？ • 出題者が用意したテストケースに全て正解すればOK ちなみにテストケースには正解したものの、本来は正しくない解法を嘘解法とも言う 入力 1 5 7 9 11 15 本来の出力 （答え） 1 2 1 0 2 0 テストケース （非開示） プログラム の出力 1 ○ 2 ○ 1 ○ 0 ○ 2 ○ 0 ○ プログラム の出力 1 ○ 0 ✕ 1 ○ 0 ○ 1 ✕ 0 ○ Accepted (受理) a Wrong Answer (間違い) 6

「十分に速い」とは？ • 問題に設定される時間内に解ければOK コンテストや問題によって多少は異なる • 間に合わなかったら？ Time Limited Exceeded (時間切れ) • 「このプログラム、24 時間動かせば正しい答え 出すんだけどなぁ…」 は 7

Section 1 AtCoder やろうぜっ！ 8

AtCoderってなんやねん • 世界最大級のコンテストサイト • 社⻑は 高橋直大(@chokudai) さん とても優秀な競技者でもある • ほぼ毎週コンテストを開いていて 結果に応じてレートがつく 9

コンテスト • AtCoder Beginners Contest (ABC) 初心者から中級者までが対象、全く易しくはないが、教育的な問題が出る • AtCoder Regular Contest (ARC) 中級者から上級者までが対象、とてもとても難しい、99.9%以上の人は解ききれない • AtCoder Grand Contest (AGC) 上級者から国を代表するような世界トップクラスが対象、気にしなくていい • その他 ABC、ARCなどを企業がスポンサーになって開催する企業コンテストや 少しルールの異なる Heuristic コンテストなども時々開催される 10

ABCについて • 8 問出題される (A ~ H 問題) A 100 B 200 C 300 D 400 E 500 F 500 G 600 H 600 • 世界って厳しい… 11

コンテストの仕組み • 問題をより多く、より早く解いた順にランキング • などで間違えるとペナルティ (+5分) • 問題には点数がついている • 獲得点数が高い順で並べて、同じなら早い順 1000点 50分 > 1000点 47分 (+10分) > 700点 30分 > 500点 60分 12

その他のステータス • Runtime Error (実行時エラー) • Compile Error (コンパイルエラー) • Memory Limited Exceeded (メモリ超過) • Waiting Judge (ジャッジサーバー待ち) • ジャッジ中 (65ケース中25ケースに成功) 13

レート • コンテストの結果に応じてレートがつく • レートに応じて色がつく 0 400 灰 800 茶 1200 緑 1600 水 2000 ⻘ 2400 黄 人外 2800 橙 赤 14

Section 2 ICPC やろうぜっ！

ICPCってなんやねん • 国際大学対抗プログラミングコンテスト International Collegiate Programming Contest 国内予選 アジア予選 World Final • 国内予選にみんなで出る • アジア予選出場を目指す！ その上はちょっとかなりとても大変 16

ルール • 3 人 1 組で出場 • 競技時間は 3時間 • ペナルティは +20分 • 使う計算機は 1 人 1 台まで • 選手同士の会話は良いが、他の人とは話せない 17

ジャッジの方法 • テストケースの入力をダウンロードして、手元実行 • 出力とプログラムを提出、結果を確認 • テストケースは複数あり、2 連続成功してAC 用意されたテストケースを使い果たしてもAC出来なければ、その問題には取り組めない • 手元実行なので、10 分くらいはセーフ！ 18

順位表 • 解いた問題数で順位付け • 同じ → 各問題が解けた時点の経過時間の和が小さい順 A 25:40 B 60:20 C 100:15 (+20) D 160:20 E F G H 25:40 + 60:20 + 100:15 (+20) + 160:20 = 366:35 19

ICPC国内予選の通過基準 • ICPC国内予選は、色んな大学の人が通過しやすいような ルールになっている → 私たちのような弱小校にもチャンス！ • 同じ大学からチームを多く通過させるには 圧倒的な実力差を有する必要がある 比例代表制の選挙では少数政党が勝ちやすく、多党制になりやすいのと同じイメージ 伝わるかな？ 20

Section 3 計算量を知る 21

注意 • 今までもそうですが、ここからは特に適当です 単語の雰囲気を理解してもらうためのものなので、厳密さに欠けます • ループのお気持ちを理解していることを 前提とします 22

プログラムの性能をざっくり知りたい！ • プログラムの性能は色々ある • メモリ（変数）の使用量が少ないと嬉しい • 実行にかかる時間が短いと嬉しい • プログラムの実行に必要な資源を、計算量という メモリ使用量、実行にかける時間 などなど… 23

計算量 • 時間計算量 実行にかかる時間を示す • 空間計算量 使うメモリの量を示す 車 最高速度が速いと嬉しい！ 燃費が良いと嬉しい！ プログラム 実行速度が速いと嬉しい！ 使用メモリが少ないと嬉しい！ 24

時間計算量 • 時間計算量は行われる処理の個数でざっくりと表す 計算量が小さいほど嬉しい（速い） • 基本的な処理を ざっくり１回分とする 例：100 回足し算する → 時間計算量は概ね 100 • • • • • • 変数への代入 変数からの読出し 基本的な演算（四則演算など） 入力 出力 その他一定時間で終わる処理 25

時間計算量と入力 • プログラムの実行にかかる時間は、入力に依存しがち 例：N 個の数値が入力されるので、和を求めなさい → 概ね N 回足し算する → 時間計算量は概ね N 26

時間計算量を比較したい • プログラムの性能を議論したい、どうやる？ 時間計算量 プログラム1 プログラム2 0.5 2 6 プログラム3 0.3 プログラム4 0.2 1 N 27

Nが大きい範囲を考える • Nを大きく（無限大に）した時の差に注目する 大体一緒じゃね？ 時間計算量 プログラム1 プログラム2 0.5 ｖ 2 6 めちゃくちゃ違う！ この大きな差に注目 プログラム3 0.3 プログラム4 0.2 1 大体一緒じゃね？ N 28

Big-O 記法 • Big-O 記法を導入する • 最も支配的な関数のみにして • 係数（定数倍）は無視して 1 として、O( )と書く 例： 3 5= 0.5 2 − 100 = ( ) 2 ! = ( !) log 4 log = 29

Big-O 記法を試す • 時間計算量を Big-O 記法で評価してみる 時間計算量 プログラム1 2= ( ) プログラム2 0.5 ｖ 6= ( ) ざっくりと評価 プログラム3 0.3 プログラム4 0.2 = ( = 1 ) ｖ N 30

プログラムを評価する • ざっくり評価してみよう プログラム1 ( ) = プログラム2 ( ) 大体一緒！ < プログラム3 ( ) = プログラム4 ( ) 大体一緒！ 31

空間計算量も一緒 • 空間計算量は、使用するメモリの大きさ • 時間計算量と同じように、入力に依存しがち • 空間計算量も Big-O 記法でよく表す プログラム1 時間 空間 プログラム2 時間 ( ) 空間 ( ) プログラム3 時間 ( ) 空間 ( ) プログラム4 時間 ( ) 空間 (1) 32

よく出る関数の大小関係 • 覚えておくと比較が楽 計算量は小さい方が嬉しい！ 1 < (log log ) < ( log ) < 定数時間 log < < 対数時間 < ( log ) < log < ソートの計算量 （並べ替え） 2 < Bit全探索など log < 2重ループの 計算量 ! < クソデカ 33

AtCoder と時間計算量 • AtCoderの多くの問題では時間制限は 2 秒 • 時間計算量にして、ざっくり 100000000 (10 ) くらいなら間に合う • ものによっては、ざっくり1000000000 (10 ) くらいでも間に合うことも しかし往々にして想定解はもっと余裕のあるものだったりします

間に合うかを検討する • 10 個のデータが入力されるので、昇順に並べ替えよ クイックソート 時間 log 概ね 2 10 マージソート 時間 log 概ね 2 10 間に合いそう！ シェアソート 時間 概ね 10 微妙なライン… バブルソート 時間 概ね 10 間に合わない！ 35

比較的厳密な Big-O 記法の定義 • = ! 全ての N # ような正定数 & と • ! について0 % ! $ が存在する' $ %& となる は の大きな値において の漸近的上限を与える 36

Section 3 C++ ってなんだろう いまつくってま〜〜〜す、未完成！ 37

C++について • C言語の派生的なプログラミング言語の一つ • 難解とも言われるが、競プロ目的なら入門は簡単 C++で出来ること 競プロで使う 入門 業務で使う 38

実行の方法 • コンパイラでコンパイルして実行する AtCoderならサーバー上でコンパイルして実行してくれる プログラム コンパイル 実行ファイル .exe など コンパイラ gcc他 人間向け コンピュータ向け 39

キホンのキ ライブラリのインクルード（結合）部分 後で解説します main という名前の関数が最初に実行されます 整数型の変数を宣言します x に値を入力します x を 3 で割った余りを出力します endl は改行を意味します（なくてもいい） 40

変数って何 • 数値などを代入しておくもの • 予め、何が入るのか（型）を指定する • 宣言：変数を用意すること • 代入：変数に値を入れること 宣言 代入 読出し • 読出し：変数の値を使うこと 41

よくやる変数の操作（演算子） • 四則演算 • 追加で 1 足す / 減らす （インクリメント / デクリメント） • 追加で 任意の数 足す / 減らす 42