競プロ入門(C++)

--- tags: 講習会 --- # 競プロ入門(C++) ## はじめに ### 目標ここでは、来たるパソコン甲子園(以下PCK)に向け今までプログラミングのプの字もやったことがない人にも競技プログラミングとは何かを理解しある程度問題を解けるようになるくらいまでになってもらうことを目標としています。 ## 本題 ### 競技プログラミング(以下競プロ)とは競プロとは、与えられた問題に対しての回答をプログラムを通して出力する早さやその正解数を競う競技です。 ### 何故С++なのか `C++`は***PCKで使用可能な言語の中で***(外の世界にはもっと使いやすい言語がたくさんあります)一番ポピュラーで競プロに向いていると我々は考えています。また，`C++`は静的型付け言語なのでデータの型(種類)が実行前に決まっています。また，`C++`には競プロに必要なデータ構造のためのライブラリが揃っています。そして，何より実行速度が速いのが競プロに向いている一番の要点です。 ### C++の基本的な形 `C++`は基本的に以下のような形で書かれます。 ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ // ここに処理を書く return 0; } ``` 最初の#から始まる文は競プロに必要な処理をまとめたものをこのプログラム(ソースコード)に読み込むためにあります。 `using namespace std;`は名前空間と呼ばれるものを制御するために使います。これは***競プロ専用の構文だと思ってください***。実際の開発ではこれを使うことは**推奨されません**。詳しく知りたい人は部長まで聞きにきてくれると喜ぶと思います。 `C++`ではmain関数の処理が行われます。なのでこのmain関数の中に処理を書く必要があります。また，`C++`は一つの処理の最後に必ずセミコロン(;)を付ける必要があります。これを忘れるとそもそもプログラムが動かないので注意してください。 ### 実行方法 `C++`は実行するときにコンパイルという処理を挟む必要があります。コンパイルを行い，ソースコードをコンピュータが理解できる機械語に翻訳する必要があるんですね。では実際にコンパイルをしてみましょう。以下のソースコードをコピーして`hello.cc`として保存してください。 ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ cout << "Hello World!!" << endl; return 0; } ``` ではこのコードが保存されているディレクトリ(Windowsで言うフォルダ)でターミナルを開いてください。(ターミナルの開き方がわからない人は近くの先輩方に遠慮なく聞いてください) 開いたら次のコマンドを入力してください。 ```shell c++ hello.cc ``` 正常に動くと何も出力されないと思います。コンパイルが終わったら`ls`などを使って`a.out`というファイルが生成されていることを確認してください。確認できたら次のコマンドで実行してみてください。 ```shell ./a.out ``` これを実行して`Hello World!!`と出力されれば成功です。おめでとうございます。 ### 変数変数とはデータを入れるための領域です。変数には型と呼ばれるデータの種類を指定する必要あります。これはとても大事なことです。||~~Pyth○nとかいう型を放棄している頭の悪い型無し言語はこれを持っていません。まったく話にならないですね。~~|| さて，それでは`C++`で使える型を見ていきましょう。 #### int 本名はInteger。意味は**整数**。2進，8進，10進，16進の整数が含まれる。値が何進数で表されたものなのかくらい`C++`側が察して欲しいものだが，そういう訳にもいかないので，接頭辞(Prefix)をつけることでそれぞれを区別する。マイナスの値を表現するときは，接頭辞の前に`-`をつける。この型は32bitで保持される。競プロ的には値の範囲-2147483648~2147483647を覚えておけばOK.この範囲を超えるとオーバーフロー/アンダーフローという現象を起こし値がおかしくなる. ##### int: 2進数接頭辞は`0b`。`0`と`1`のみが使われる。例: `0b1010` ##### int: 8進数紹介したは良いものの，実際に使う機会はほぼ無い。接頭辞は`0o`で，`0-7`が使われる。例: `0o7654` ##### int: 10進数現実世界で大流行している表現。接頭辞は無く，`0-9`が使われる。例: `9876` ##### int: 16進数整数の域で究極に情報量を高めた形。接頭辞は`0x`で，`0-9`と`a-f`が使われる(`0,1,2,……8,9,a,b,……e,f,10,11,……`の順番)。例: `0xfeba9876` #### long long intの2倍のデータ容量を持った型 -9223372036854775808~9223372036854775807の範囲を表現可能。迷ったらとりあえずこれを使えばいい。ちなみに`using namespace std;`とかのあたりに`typedef long long ll;`と書いておくと`ll`で使える #### float 実数型とも呼ばれる。簡単に言えば小数にも対応した数字型。データ容量は小さめなのであまり使われない。 #### double floatと同じように小数を表すことができる。floatよりこちらのほうがデータ容量が多いのでより大きい値を保存することができる。 #### char 文字(1文字)のこと。シングルクォート(`'`)で囲まれた文字のこと。また，ASCIIコードの数字もchar型で表せる。例('A'は65でも表せる) #### string C++においてstring型の値はダブルクォート(`"`)で囲んだ文字列のこと。 charの配列 #### bool 真偽値のこと。 `true`が真で`false`が偽。 #### 使い方型について知ったところで，実際にソースコードでどのように使うのかについて知っておこう。||~~うーーん。複雑だね。じゃ!~~|| ```cpp= int a; // 値を指定せずに領域だけ確保(中身はランダム) int b = 3; // int型の変数を宣言すると同時に値を代入(初期化とも言う) char c = 'd'; // char型の変数を宣言 string s = "Densan"; // string型の変数を宣言 bool flag = false; // bool型の変数を宣言 ``` このように型名と変数名をセットで書くことで変数を作ることができます。ちなみに変数を作ることを変数を宣言すると言います。変数名にはいくつかのルールがあります。先頭を数字で始めてはいけない,アンダーバーと半角英数字以外は使用してはいけない,予約語という既にC++で使われている単語(`if, for, include`など)は使用できないなどがあります。 ### 四則演算 #### 演算子基本的にどのプログラミング言語でも四則演算ができる。それぞれの演算記号は次のようになっている。 | 計算 | 数学 | C++ | | :----: | :----: | :----:| | 加算 | + | + | | 減算 | - | - | | 乗算 | × | * | | 除算 | ÷ | / | | 剰余 | mod | % | ちなみに計算の順番は数学と同じである。また，()をつけると()の中が優先される。 ```cpp= a = 1 + 3 * 4; // => 13 a = (1 + 3) * 4; // => 16 ``` #### 複合代入演算子 C++には変数への計算と代入が同時できる演算子がある。これはそれぞれ次のような形式で書く。 | 計算 | 実際の動き | 複合代入演算子 | | :----: | :----: | :----:| | 加算 | a = a + b | += | | 減算 | a = a - b | -= | | 乗算 | a = a * b | *= | | 除算 | a = a / b | /= | | 剰余 | a = a % b | %= | これは変数を加算したりするときに使われる。 ```cpp= int a = 3; a += 5; // a == 8 a -= 2; // a == 6 a *= 3; // a == 18 a /= 6; // a == 3 a %= 2; // a == 1 ``` #### インクリメント，デクリメントプログラミングでは変数に1を加算する，減算するといった処理がよく使われる。そのため複合代入演算子よりも簡単に書ける式がある。 | 計算 | 実際の動き | 記号 | 呼ばれ方 | | :----: | :----: | :----:| :----: | | 1を足す | a += 1 | `++a`,`a++` | インクリメント | | 1を引く | a -= 1 | `--a`,`a--` | デクリメント | ちなみに`++a`と`a++`で若干意味が変わってくる。 <details> <summary>詳しく知りたい方向け</summary> ```cpp= int a = 10; int b,c; b = ++a; a = 10; c = a++; ``` 上記のコード(main関数省略)ではbは11,cは10になる。 `++a`ではaに1を加えてからbへの代入が行われるのに対し、`a++`ではcへの代入を行った後にaに1が加えられている。つまり、`++a`は真っ先に計算されるが`a++`は一連の計算が終わった後に計算される。 </details> ### 標準入出力標準入出力とはターミナルにデータを出力したり，逆にターミナル上からキーボードで入力した文字をプログラム側で読み込んだりする処理の事です。では，`C++`での標準入出力のやり方をみていきましょう。 `C++`では出力には`cout`(シーアウト)，入力には`cin`(シーイン)を用います。例を見てみましょう。 ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ cout << "Hello, World!!" << endl; // "Hello, World"と出力(endlは改行,'\n'でもいい) int a; cin >> a; // ターミナルからの入力をaに格納 cout << a << endl; // aを出力 return 0; } ``` 競プロでは問題文に入力が書いてあるので，テストしたいときはそれをターミナルにコピペしましょう。実際の提出では問題の入力は自動で行われます。 #### 小数の桁数を指定したい場合 C++で小数型の値を出力しようとした場合、 ```cpp= double pi = 3.141592654, e = 2.71828182846; cout << pi << endl; //3.14159と出力される printf("%.9lf", p); //3.141592654と出力される printf("%.9lf %.4lf", p,e); //複数出力したい場合はこんな感じ ``` のように`cout`を使用するとせいぜい小数点以下5桁程度しか表示されませんが`cout`とは別の出力の関数`printf`を使うと表示する桁数を指定して表示できます。これについてちゃんと説明しようとするとフォーマット指定子というものについて説明しなくてはなりませんがここに書くにはスペースが小さすぎるので知りたい人はまた部長に聞いてみてください。ここでは ```cpp %.(数字)lf ``` ~~の数字を変えると出力する桁数を指定できるんだな、くらいの認識でいいです。~~ やっぱり[苦しんで覚えるC言語のこのへん](https://9cguide.appspot.com/05-04.html)を見ておいてください。 ### 条件分岐特定の条件によって処理内容を変えたい場合の方法などについて説明する。 #### bool 真偽値のこと。 `true`が真で`false`が偽。 #### if文条件式が真の場合，それ以外の場合に処理を実行する。 `else`や`else if`は`if`が無いと動かないが、`else`や`else if`を書く必要が無いときは`if`だけでもいい。 ```cpp= if(条件式1){ 条件式1がtrueの場合に実行する }else if(条件式2){ 条件式1がfalseかつ条件式2がtrueの場合に実行する }else { 条件式1，2がどちらもfalseの場合に実行する } ``` #### 比較演算子 `a == b`のように書き、この場合`a`と`b`が等しければ`true`になり等しくなければ`false`になる。前項の`if`や`else if`,後述の`while`の条件式というところにこれが入る。 ```cpp= aとbは等価 a == b // "="は二つ!!!! aはbではない a != b aはb以上、aはbより大きい a >= b, a > b aはb以下、aはbより小さい a <= b, a 0 && b > 0 aかbのどちらかが正の数(||) a > 0 || b > 0 cではない(!) !c ``` ### ループ処理ここでは繰り返し処理をする記述について解説する。 #### while 条件式が真の場合のみ処理を繰り返し実行する。 ```cpp= while(条件式){ 条件式がtrueの間実行され続ける } ``` 使用例 ```cpp= int i = 0 while(i > 10){ cout << i << endl;; i++; } ``` #### for 決められた回数だけ処理を実行する。 ```cpp for(int i = 0; i < 10; i++){ //実行文(10回実行される) } ``` どういうことか解説する。 ```cpp int i = 0; ``` これはループの回数を記録するための変数を定義している。なお，プログラミングの世界では基本的にカウントは0から始まることに注意。 ```cpp i > 10; ``` これはループを続ける条件を示している。これが```true```の間ループし続ける。 ```cpp i++ ``` これは1回のループが終わる毎にする処理をここに書いている。 - **でも途中で抜け出したいときもある!** そんなときは，`break`を使おう！ ```cpp= while(条件文){ 実行文 if(条件式){ break; // この命令でこの while から脱出! } } ``` - **でも条件によってはもう一度戻りたい…** でも大丈夫 `continue`を使おう！ ```cpp= for(int i = 0; i < 10 i++){ if(i % 2 == 1){ continue; // この命令で現在の周回をすっ飛ばして次の周回まで行く } } ``` --- これにより，メインプログラムを無限実行とかも可能ですよね。 例(応用)： ```cpp= while(true){ 実行文 //ここで何かを入力したり，描画しよう // 脱出するためには if(条件式){ break; //こう書くだけでok } } ``` ### 関数いくつかの処理を一つにまとめたものを関数と言い、関数は一度定義してしまえば何度でもそのコード内で使えるので便利である。関数は以下のように定義する。 ```cpp= int sum(int a, int b){ return a + b; } cout << sum(2, 4) << endl; //6と出力される ``` まず最初に戻り値(ここでは`a + b`)の型を宣言する。次に関数名を宣言する。そして，`()`を付け，中に引数(関数の中で使う変数)の名前，型を宣言する。(引数は省略可能) 次にブロックの中に処理を書いていく。最後にその関数の呼び出し元に返すものを`return`の後に続けて書く。これで関数が定義できる。このとき，関数は ```cpp= sum(1, 2) // 3 ``` のようにして実行できる。 `return`の後に書いたものが返される(ここでは3)。 ### 配列競プロではよく$A_1,A_2,…,A_n$の数列が与えられ、それをｺﾞﾆｮｺﾞﾆｮして答えを出す問題が出てくる。ではこのとき、どうやってその値を保持しておくべきだろうか。`a1`,`a2`,`a3`,……として$n$個の変数を作ろうか？それではすごく非効率的である。$n$の値は時として$10^9$にも及び、その数の変数をいちいちひとつずつ定義していたのでは書くのがとてもしんどいし何より冗長なコードになってしまう。ここで、配列の登場である。配列とは変数をまとめたもののことである。そして中に入っている複数個の変数を番号(インデックスともいう)で管理できる。習うより慣れろなので実際のコードを見ていこう。 ```cpp= vector<int> array(n); // int型でn個の要素が入る配列 ``` これでn個のint型の変数が入る配列が宣言できた。ちなみに ```cpp= vector<long long> a; ``` のようにすると`long long型`の空の配列(長さが0の中身のない配列)`a`が宣言できる。簡単な扱い方についてみていこう。 ```cpp= vector<int> a = {1,2,3,4,5}; // 宣言と同時に初期化 a[0] // 0番目の値(ここでは1) a[1] // 1番目の値(ここでは2) ... a[4] // 4番目の値(ここでは5) // a[5] これは範囲外でエラー ``` このように配列名とインデックスを使ってn番目の要素を扱うことができる。ここで，`a[n]`はいつもの変数のように使える。 ```cpp= // ↑の続き a[0] + 1 // 2 a[0] += 2 // 4 if(a[0] == 4){ cout << "a[0] == 4" << endl; } ``` このように四則演算や代入，条件文など他の変数と同じように扱える。では，配列を1つ1つ取り出して何かの処理をするためにはどうすればいいだろうか。そこでfor文が役に立つ。 ```cpp= // ↑の続き for(int i = 0; i < n; i++){ if(a[i] % 2 == 0){ cout << "a[i]は偶数" << endl; } } ``` このようにインデックスにループ変数を用いることによって配列内のすべての要素にアクセスできる。また，C++ではこの処理専用のfor文がある。 ```cpp= // ↑の続き for (int i : a){ cout < b; // 要素数を指定せずに宣言 ``` 要素を追加するにはpush_back()関数を用いる。 ```cpp= vector<int> a; a.push_back(4); ``` これで`a`という配列に4という値が入った。 ### その他関数竸プロでは配列にいろいろな処理をするときがあります。その中には関数で一発でできちゃうものもあります。 #### ソート数字の配列を昇順に並び変えることは竸プロではよく必要になります。ここでは配列をソートする方法について見ていきましょう。 ```cpp= vector<int> a = {5,2,6,1,3}; sort(a.begin(), a.end()); ``` これで配列を出力すると，`1, 2, 3, 5, 6`と出力されるはずです。こうすることで配列をソートすることができます。 ## 実際に書いてみよう #### 1.標準出力の練習 ##### 問題1.1 次のプログラムに1行追加して標準出力に`Hello World`と出すようなプログラムを作成してください ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ /*ここに1行追加*/ return 0; } ``` ##### 問題1.2 標準出力に`プログラミングは超絶カンタンだよ`と出すようなプログラムを作成してください ##### 問題1.3 1行目に`Hello World`,2行目に`d3bu`と出力するようなプログラムを作成してください #### 2.標準入力と四則演算の練習 ##### 問題2.1 以下は標準入力で整数$A$と$B$が与えられると$A+B$を返すプログラムである ```cpp= #include<bits/stdc++.h> using namespace std; int main(){ int A,B; cin >> A >> B; cout << A+B << endl; return 0; } ``` このプログラムを参考にして、標準入力で整数$A$と$B$が与えられたとき、$A*B$を返すプログラムを作成してください ##### 問題2.2 標準入力で$0$でない整数$A$と$B$が与えられたとき、1行目に$A÷B$の商(整数値)を、2行目に$A÷B$の余りを出力してください。 ##### 問題2.3 標準入力で$0$でない実数$A$と$B$が与えられたとき、$A÷B$の値を小数点以下9桁まで出力してください ##### 問題2.4 標準入力で文字列$S$が与えられるので、`私の名前は`のあとに文字列$S$を出力してください入力例 ``` 電算太郎 ``` 出力例 ``` 私の名前は電算太郎 ``` ##### 問題2.5 標準入力で文字列$S$と$T$が与えられるので、次の形式で出力してください ``` すみません、Sには行けません私は今Tにいます ``` 入力例 ``` 同窓会シンガポール ``` 出力例 ``` すみません、同窓会には行けません私は今シンガポールにいます ``` #### 3.条件分岐 ##### 問題3.1 標準入力で整数$A$,$B$が与えられるので、$A$が$B$以上であれば`Bigger`を、そうでなければ`Smaller`を出力してください ##### 問題3.2 標準入力で整数$N$が与えられます。もし$N$が奇数ならば`odd`、偶数ならば`even`を出力してください。 ##### 問題3.3 標準入力で文字列$S$が与えられます。もし入力された文字列が`d3bu`ならば`Yes`を、そうでなければ`No`を出力してください。 ##### 問題3.4 標準入力で整数$N$が与えられます。もし入力された整数が$2$の倍数であれば`2の倍数`を、$3$の倍数であれば`3の倍数`を、$2$の倍数かつ$3$の倍数であれば`6の倍数`を出力してください入力例 ``` 12 ``` 出力例 ``` 6の倍数 ``` #### 4.繰り返し文と配列 ##### 問題4.1 標準入力で整数$N$が与えられるので、$1$~$N$の整数を空白区切りで出力してください入力例 ``` 5 ``` 出力例 ``` 1 2 3 4 5 ``` ##### 問題4.2 標準入力で非負整数$N$と要素数$N$である配列$A$が与えられます。この配列の要素の合計を出力してください入力は以下の形式で与えられる ``` N A_1 A_2 ... A_N ``` 入力例 ``` 5 1 2 3 4 5 ``` 出力例 ``` 15 ``` ##### 問題4.3 標準入力で非負整数$N$と要素数$N$である配列$A$が与えられるので、この配列を昇順に並び替えたものを出力してください。入力は以下の形式で与えられる ``` N A_1 A_2 ... A_N ``` 入力例 ``` 5 4 2 5 7 4 ``` 出力例 ``` 2 4 4 5 7 ``` ##### 問題4.4 標準入力で非負整数$N$と要素数$N$である配列$A$が与えられるので、この配列を降順に並び替えたものを出力してください。入力は以下の形式で与えられる ``` N A_1 A_2 ... A_N ``` 入力例 ``` 5 4 2 5 7 4 ``` 出力例 ``` 7 5 4 4 2 ``` #### 問題4.5 文字列が入っている配列(`vector<string>`)をソートすると辞書順で早い順に並び替えられる。これを用いて以下の問題を解いてください。標準入力で非負整数$N$と$N$個の文字列$S$が与えられる。与えられた文字列を辞書順で早い順に出力してください入力は以下の形式で与えられる ``` N S_1 S_2 ... S_N ``` 入力例 ``` 5 a aba babab ba b ``` 出力例 ``` a aba b ba babab ``` ここまでできた人は高難易度問題(https://hackmd.io/@kcctdensan/SJ3-Ake_h)も用意しているのでチャレンジしてみよう！！！ ### さいごに競技プログラミングは狭義プログラミングです。競プロがプログラミングの全てという訳ではありません。競プロの他にもアプリ開發とかやってみましょう(多分そっちの方が楽しい)。