競プロやろうぜ!

1.7K Views

June 16, 23

スライド概要

競技プログラミングをサークルの後輩たちに紹介する際に作成したスライドです。AtCoderやICPCの存在に触れ、これらの概要やルールを紹介しています。内容は2021年当時のものです。

profile-image

法律と情報が好きな電気電子出身の人です。 自然言語処理の研究をする予定です。 ※注意事項: 私は各分野(特に法律)の専門家ではなく、公開している資料は身内の勉強会向けに作成したものが殆どで、正確性は保証出来ません。 また、過去に作成したものを適当にアップロードしているので、最新の情報であることも保証出来ません。 作成日時はアップロード日時より平均して2年程前になります。

シェア

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

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

2.

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

3.

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

4.

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

5.

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

6.

「正しい」とは? • 出題者が用意したテストケースに全て正解すれば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

7.

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

8.

Section 1 AtCoder やろうぜっ! 8

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

Section 2 ICPC やろうぜっ!

16.

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

17.

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

18.

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

19.

順位表 • 解いた問題数で順位付け • 同じ → 各問題が解けた時点の経過時間の和が小さい順 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

20.

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

21.

Section 3 計算量を知る 21

22.

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

23.

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

24.

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

25.

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

26.

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

27.

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

28.

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

29.

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

30.

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

31.

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

32.

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

33.

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

34.

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

35.

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

36.

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

37.

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

38.

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

39.

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

40.

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

41.

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

42.

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