RICORA_競プロ入門
1.3K Views
April 25, 25
スライド概要
2025年度に行った競技プログラミング入門講座で使用した資料です。
（ダウンロード不可）
関連スライド
Meta XR SDK(V66-74)でQuestアプリを開発
あうぜん
1.2M
各ページのテキスト
競技プログラミング入門 RICORA Programming Team kuradai 1
競技プログラミングとは？ ● 与えられた問題をプログラミングで解決し、 その過程や結果を競うものを競技プログラミングという ● 解答はプログラムで表しますが、 ○ どのような計算をさせるか ○ どのアルゴリズムを使うか を考える必要があり、プログラミングの力だけでなく、 思考力、数学力、知識が求められる 2
競技プログラミングは初心者の方におすすめ ● ゲームやWebサイトを作りたいなどの目的がなくても、 問題を解くという目的でプログラミングに取り組める ● 競技プログラミングではコーディングの速度も求められるため、 早くコードが書けるようになる ● コードが間違えていた場合に、 自分で間違いを見つける必要があるため、 デバッグの力が鍛えられる 3
AtCoderとは？ ● AtCoderとは、プログラミングを用いて戦う頭脳スポーツ 「競技プログラミング」のコンテストサイトの一つ ● 約20万人がコンテストサイトに登録し、 小学生から社会人まで、毎週1万人ほどのユーザが、 リアルタイムのコンテストに参加している ● 初心者向け問題を含む、約5000問の過去問や、 豊富な解説などの教材が存在するため、 誰でも気軽に挑戦できる 4
Algorithm Contest(今回実践する問題) ● 与えられた問題を解決するプログラムを、 早く正確に提出し、その正解数と順位を競うコンテスト →与えられた問題の正解を導くプログラムを作成する ● AtCoderでは以下のコンテストにあたる ○ AtCoder Beginner Contest(ABC) ○ AtCoder Regular Contest(ARC) ○ AtCoder Grand Contest(AGC) 5
Heuristic Contest ● 最適解を求めることが難しい複雑な問題に対して、 どれだけ良い解を求めることができたかを競うコンテスト →与えられた問題に対してできるだけ良い解を導く プログラムを作成する ● AtCoderではAtCoder Heuristic Contest(AHC) にあたる 6
Algorithm Contestの問題を解いてみる ● AtCoderのアカウント登録 https://info.atcoder.jp/overview/contest/intro の「AtCoderへユーザ登録する」を参考にして、 登録してください 7
GitHub Codespacesを開こう 1. リンクにとぶ 2. 緑色の「Code」を押して、Codespacesタブに移動して、 緑色の「Create codespace on main」 を押す 8
C++のコードを実行しよう 1. sample.cppをコンパイルする ➡ 現在のディレクトリに「a.out」が作成される 2. 「a.out」を実行する $ g++ sample.cpp $ ls a.out … sample.cpp … $ ./a.out 10 20 (自分で入力) 30 9
C++について
● プログラムコード(sample.cpp)
○ ２つの整数を入力で受け取り、その和を出力するプログラム
#include <iostream>
#include <string>
int main(){
int number1, number2;
std::cin >> number1 >> number2;
int sum = number1 + number2;
std::cout << sum << std::endl;
}
10
C++について
● プログラムコード(sample.cpp)
○ ２つの整数を入力で受け取り、その和を出力するプログラム
#include <iostream>
#include <string>
int main(){
実際に書く部分
int number1, number2;
std::cin >> number1 >> number2;
int sum = number1 + number2;
std::cout << sum << std::endl;
}
11
C++について ● 変数の宣言 ○ 値を入れる箱を作成する ○ 変数名は「_」（アンダースコア）か半角英字で始まるものが 使用できる int 変数名; // 整数の変数 std::string 変数名; // 文字列の変数 int 変数名 = 初期値; 12
C++について ● 出力 「std::cout」で出力 (std::endlは改行) 使用例 int num = 5; std::cout << num << std::endl; ➡ 5 std::cout << "Hello, World!" << std::endl; // 出力 ➡ Hello, World! std::cout << 変数名 << std::endl; int num1 = 3, num2 = 7; std::cout << num1 << " " << num2 << std::endl; ➡ 3 7 13
C++について ● 入力 「std::cin」で入力 スペースや改行で区切って１つずつ入力される 使用例 int num1, num2; // 入力 std::cin >> num1 >> num2; std::cin >> 変数名; ➡ 5 12 (入力) std::cout << num1 << ":" << num2 << std::endl; 5:12 ➡ 5 12 (ここまで入力 ) 5:12 14
C++について ● 演算 // 加算 int sum = 2 + 3; std::cout << sum << std::endl; ➡ 5 // 除算 int div1 = 9 / 3; // 減算 std::cout << div2 << std::endl; int sub = 10 - 7; ➡ 3 std::cout << sub << std::endl; ➡ 3 int div2 = 5 / 2; std::cout << div2 << std::endl; // 乗算 ➡ 2 int mul = 3 * 4; std::cout << mul << std::endl; ➡ 12 15
C++について 条件式の例 // num1がnum2に等しい ● if文 num1 == num2 条件式の真偽で処理を分岐させる文 // num1がnum2より小さい num1 < num2 if(条件式1){ // 条件式1が真のときの処理 // num1がnum2より大きい num1 > num2 } else if(条件式2){ // 条件式1が偽で // num1がnum2以上 num1 <= num2 // 条件式2が真のときの処理 // num1がnum2以下 } num1 >= num2 else{ // 条件式1,2が共に偽のときの処理 } // num1がnum2より大きくnum3より小さい num2 < num1 && num1 < num3 16
例題１ ● AtCoder Beginner Selection PracticeA - Welcome to AtCoder ● コーディングの進め方 1. 2. 3. 4. 5. 定型文を書く 入力を入れる変数を宣言する 変数に入力する 受け取った変数に適切な処理を行う 結果を出力する 17
例題１ ● プログラムを書くファイルを作成する ○ CLI touchコマンドで作成 $ touch example1.cpp ○ GUI 「新しいファイル…」を押し ファイル名を入れる 18
コーディングの進め方 例題１ #include <iostream> 1. 2. 3. 4. 5. 定型文を書く 変数を宣言する 変数に入力する 適切な処理を行う 結果を出力する #include <string> int main(){ // 実際に処理を行うコードを書く } 19
コーディングの進め方
例題１
#include <iostream>
#include <string>
1.
2.
3.
4.
5.
定型文を書く
変数を宣言する
変数に入力する
適切な処理を行う
結果を出力する
int main(){
// 変数を宣言する
int a, b, c;
std::string s;
}
整数３つと文字列１つが
入力される
➡それらを入れる変数を
➡宣言する
20
コーディングの進め方
例題１
#include <iostream>
#include <string>
1.
2.
3.
4.
5.
定型文を書く
変数を宣言する
変数に入力する
適切な処理を行う
結果を出力する
int main(){
// 変数を宣言する
int a, b, c;
std::string s;
// 入力する
std::cin >> a >> b >> c >> s;
}
「std::cin」を使って
宣言した変数に入力する
21
コーディングの進め方
例題１
#include <iostream>
#include <string>
1.
2.
3.
4.
5.
定型文を書く
変数を宣言する
変数に入力する
適切な処理を行う
結果を出力する
int main(){
// 変数を宣言する
int a, b, c;
std::string s;
// 入力する
std::cin >> a >> b >> c >> s;
// 処理を行う
int sum = a + b + c;
}
３つの整数は和を出力する
➡和を計算する
文字列はそのまま出力
➡処理は必要ない
22
コーディングの進め方
例題１
#include <iostream>
#include <string>
int main(){
1.
2.
3.
4.
5.
定型文を書く
変数を宣言する
変数に入力する
適切な処理を行う
結果を出力する
// 変数を宣言する
int a, b, c;
std::string s;
// 入力する
std::cin >> a >> b >> c >> s;
// 処理を行う
int sum = a + b + c;
// 結果を出力する
std::cout << sum << " " << s << std::endl;
}
処理で求めた和と文字列
を空白区切りで出力する
23
例題１ ● プログラムを実行する $ g++ example1.cpp $ ./a.out ● プログラムが正しいか確かめる ○ 自分で入力する ○ 与えられている入力例を使用する 24
例題１ ● プログラムを提出する 1. ページの最下部に移動 2. ソースコードに 作成したコードを貼り付け 3. 言語で使用したプログラミング言語を選択 C++の場合は「C++20(gcc 12.2)」 25
例題１ ● 結果を確認する 1. タブの 提出結果＞自分の提出 に移動 2. これまでの提出結果が 表示される 3. 詳細からテストケースごと の結果を確認できる 結果 ● AC すべてのテストケースで正解 ● WA 一部のテストケースで不正解 ● TLE 一部のテストケースで 実行時間が超過した ● RE 一部のテストケースで プログラムのエラーが発生した 26
問題１ ● AtCoder Beginner Contest219 A - AtCoder Quiz 2 ● プログラムを書いてみよう！ ○ １から書きたい方 ➡ problem1_1.cpp（定型文のみ） ○ 始め方が分からない方 ➡ problem1_2.cpp（穴埋め） ○ 解答例 ➡ problem1_ans.cpp 27
問題１ ● 解説 問題文の通り、点数によって以下の４つで場合分けする 1. ４０点未満のとき 2. ４０点以上７０点未満のとき 3. ７０点以上９０点未満のとき 4. ９０点以上のとき 28
問題１ ● 解説 １.～3.は計算の処理が必要で、 1. ４０点未満のとき ➡ ４０点まで「40-点数」点 2. ４０点以上７０点未満のとき ➡ ７０点まで「７０-点数」点 3. ７０点以上９０点未満のとき ➡ ９０点まで「９０-点数」点 ４.が「expert」を出力すればよく、処理が不要 29
#include <iostream>
#include <string>
問題１
int main(){
// 変数を宣言する
int X;
// 入力する
● 解説
解答例
std::cin >> X;
// 処理を行う
int rest;
if(X < 40){ // 0 <= X && X < 40 でも可
rest = 40 - X;
}
else if(X < 70){ // 40 <= X && X < 70 でも可
rest = 70 - X;
}
else if(X < 90){ // // 70 <= X && X < 90 でも可
rest = 90 - X;
}
// 結果を出力する
if(X < 90){ // 0 <= X && X < 90 でも可
std::cout << rest << std::endl;
}
else{
std::cout << "expert" << std::endl;
}
}
30
C++について ● for文 ○ 処理を繰り返す文 ○ 変数は0から「繰り返し回数-1」まで動く 使用例 for(int 変数名 = 0; 変数名 < 繰り返し回数; 変数名++){ for(int i = 0; i < 3; i++){ // 繰り返し行う処理 } std::cout << i << std::endl; } ➡ 0 1 2 31
C++について ● 配列 ○ 変数を入れる連続した箱を作る ○ 箱の番号は０から始まる 使用例 int array[3]; for(int i = 0; i < 3; i++){ std::cin >> array[i]; // 配列の宣言 } for(int i = 0; i < 3; i++){ int 配列名[箱の数]; std::cout << array[i] << std::endl; } ➡ 10 20 30 (入力) // 配列のアクセス 配列名[番号]; 10 20 30 32
問題２ ● AtCoder Beginner Contest384 B - ARC Division ● プログラムを書いてみよう！ ○ １から書きたい方 ➡ problem2_1.cpp（定型文のみ） ○ 始め方が分からない方 ➡ problem2_2.cpp（穴埋め） ○ 解答例 ➡ problem2_ans.cpp 33
問題２
● 解説
解答例
// 処理を行う
int now_rating = R;
for(int i = 0; i < N; i++){
if(D[i] == 1){
if(1600 <= now_rating && now_rating <= 2799){
now_rating = now_rating + A[i];
}
#include <iostream>
}
#include <string>
else{
if(1200 <= now_rating && now_rating <= 2399){
int main(){
now_rating = now_rating + A[i];
// 変数を宣言する
}
int N, R, D[100], A[100];
}
}
// 入力する
std::cin >> N >> R;
// 結果を出力する
for(int i = 0; i < N; i++){
std::cout << now_rating << std::endl;
std::cin >> D[i] >> A[i];
}
}
34
アルゴリズムを使う 問題 昇順に並んでいる数列がある。 この数列の中で、ある数以下で最大の数は何かを調べる。 調査回数をできるだけ減らすにはどうすればよいか？ 2５以下の最大は？ 1 2 3 5 8 13 21 34 55 89 35
二分探索について ● 線形探索 ○ データの先頭から順番に確かめる探索方法 ○ 最大でデータの個数分の調査が必要 2５以下の最大は？ ➡２１（８回） 1 2 3 5 8 13 21 34 55 89 36
二分探索について ● 二分探索 ○ データの探索範囲を半分ずつに絞り込んでいく探索方法 ○ 最大でもデータの個数のlog回程度の調査で済む 25以下の最大は？ ➡２１（4回） 1 2 3 5 8 13 21 34 55 89 ∞ ○ データの数が10000でも14回で済む 37
二分探索の応用 ● 答えを二分探索で絞り込む ○ 二分探索は条件を満たす範囲と満たさない範囲が 分かれているとき、その境界を高速で探すことができる 値が２5以下 left 値が25 より大きい right 38
二分探索の応用 ● コード例 int left = 範囲の最小値 , right = 範囲の最大値 ; while(right - left > 1){ int mid = (left + right) / 2; if(条件を満たす場合の条件式 ){ left = mid; } else{ right = mid; } } 答えはleftに入る 39
// 処理を行う
二分探索について
int left = 0, right = 10; // 範囲の左端と右端を設定
while(right - left > 1){ // 二分探索
int mid = (left + right) / 2;
if(A[mid] <= max_border){
● コード例(example2.cpp)
left = mid;
}
else{
#include <iostream>
right = mid;
#include <string>
}
}
int main(){
// 変数を宣言する
// 結果を出力する
int N, M, A[10] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
if(A[left] <= max_border){
int max_border;
std::cout << A[left] << std::endl;
}
// 入力する
else{
std::cin >> max_border;
std::cout << "条件を満たす値がありません" << std::endl;
}
}
40
問題３ ● AtCoder Beginner Contest365 C - Transportation Expenses ● プログラムを書いてみよう！ ○ 問題全体を解きたい方 ➡ problem3_1.cpp（穴埋め） ○ 二分探索のみ書きたい方 ➡ problem3_2.cpp （二分探索を穴埋め） ○ 解答例 ➡ problem3_ans.cpp ※ 「int」の代わりに「long long int」を使用してください 41
問題３ ● 二分探索を使わないで解くと... 1. xを1増やして払う金額がいくらか計算する 2. 払う金額とMの大小関係を調べる 3. 1.と2.を繰り返して、Mを超えたらそのひとつ前のxが答え xが無限に大きくなる場合は？ 有限だったとしてもどれくらい時間がかかる？ 42
問題３ ● 一般のコンピュータでは、１秒で108回程度の計算ができる ● 前の解法で繰り返される回数を大まかに考えると... ○ xはAiの最大値(最大109)まで答えになる可能性がある ○ １つのxで払う金額を求めるのに、 イベント参加者の人数(最大2×105人)分の計算が必要 ➡ 最大で109×(2×105)=2×1014回の計算が必要 ➡ 2×106秒(約23日)かかる ● もちろんxを無限に大きくできる場合は無限に時間がかかる 43
問題３ ● 解説(problem3_1.cppを使った方） ● 答えは大きく二つに場合分けできる 1. 答えが有限の場合 2. 答えを無限に大きくできる場合 2. であるかを判定する 答えを無限大とした場合、払う金額はそれぞれに 合計で 円となり、 円となる ➡ これがM以下なら高橋くんは払える 44
問題３ ● 解説 ● 1. の場合は ○ 交通費補助額の上限額ｘを大きくするほど、 高橋くんが払う金額は大きくなる ○ 条件を満たすのは払う金額がM以下のとき ➡ これを条件式で表して二分探索しよう 45
問題３ ● 解説 ● 交通費補助額の上限額がｘのときの払う金額を 数式で表すと、 long long int sum = 0; for(int i = 0; i < N; i++){ ● int min; ● となる if(x < A[i]){ min = x; ● } これは右のようにして else{ min = A[i]; sumに求められる min sum } sum = sum + min; } 46
// 二分探索
long long int left = 0, right = 1000000001;
問題３
while(right - left > 1){
long long int mid = (left + right) / 2;
long long int sum = 0;
● 解説
解答例
（二分探索以外は省略）
for(int i = 0; i < N; i++){
int min;
if(mid < A[i]){
min = mid;
}
else{
min = A[i];
}
sum = sum + min;
}
if(sum <= M){
left = mid;
}
else{
right = mid;
}
}
47
問題３ ● 一般のコンピュータでは、１秒で108回程度の計算ができる ● 今回の解法で繰り返される回数を大まかに考えると... ○ xはAiの最大値(最大10⁹)まで答えになる可能性がある ➡二分探索によりAiの最大値のlogに(最大log2109≒30) ○ １つのxで払う金額を求めるのに、 イベント参加者の人数(最大2×105人)分の計算が必要 ➡最大で30×(2×105)=6×106回の計算が必要 48
GitHub Codespacesを終了させる 1. Codespacesのページを閉じる 2. GitHubのページの緑色の「Code」を押して、 Codespacesタブに移動する 3. 「・・・」を押す 4. 「Delete」を押す 5. Codespacesタブに 「No codespaces」と 表示されていることを確認する 49
競技プログラミングを始めよう! ● AtCoderでは初心者向け（後半の問題は上級者向け）の AtCoderBeginnerContest(ABC)が 毎週土曜日の21:00～22:40（100分間）で開催されている ● コンテストに参加することで、正解数と時間で順位が決まり、 それに応じてレートが変動する 50
競技プログラミングを進める上で役に立つサイト ● AtCoder Problems ○ AtCoderで行われたコンテストの過去問をまとめられている ○ 問題ごとの難易度がわかる ○ 解いたとこがある問題が一目でわかる 51
競技プログラミングを進める上で役に立つサイト ● AtCoder Clans ○ その他多くのAtCoder関連サービスを纏めたリンク集 ○ 有志による非公式サービス・ツール・ライブラリ・記事などが まとめられている 52