知識ゼロからAtCoderにチャレンジしてみた話【c++の豆知識とAtCoderの流儀のお勉強】前編

arduino+swiftの民が〜　AtCoderで〜　c++に〜　出会ったぁ〜（ｳﾙﾙﾝ口調

はじめに

• 前回の玉砕については、計算量の把握が出来ていなかったことだと反省して、勉強し直すことにした。
• 前回解けなかったABC356のC,D問題の解き方を理解したけど、やはり、自分で思いついたロジックによる計算量が見積もれないようだと今後困るので、どうしたモノかと思ったけど、atcoderのHPに用意されていた。
• 「C++入門 AtCoder Programming Guide for beginners(APG4b)」のこの問題(EX21 - 計算量の見積もり)によれば、

AtCoderのジャッジでは1秒あたり$10^8$回程度の計算が可能です。

　とのこと。

• そんな重要なことすら知らんかったよ。よって、この問題を含むAPG4bをやってみた。
• 前回のチャレンジでは慣れてるswiftを使ったけど、arduinoIDEでc++の基本的な知識はあるから、APG4bも問題なくやれるでしょ。

APG4bの基礎知識

• 次の四章からなっている。今回は、第2章までからピックアップする。
  • 第1章 基本文法
  • 第2章 複雑な計算処理の書き方 <- 今回はここまで
  • 第3章 競技プログラミングに役立つ知識
  • 第4章 今まで説明していなかったこと
• そして、全四章が始まる前の冒頭ページで重要な事が書かれている。具体的には直接読んで欲しいけど、コードの冒頭は、深く考えず、下記コードを書いておけということ。このヘッダーにより、cout << "Hello, world!" << endl;のような書き方が可能になるから、iostreamも含まれているんだろう。

#include <bits/stdc++.h>
using namespace std;

• また、テクニックとして、リピート処理用のマクロ#define rep(i, n) for (int i = 0; i < (int)(n); i++)が紹介されている。具体的な利用方法は以下の通り。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() { 
  rep(i, 3) { // 処理が3回繰り返される 
    cout << "Hello" << endl;
    cout << "AtCoder" << endl;
  }
}

• なお、この冒頭ページでは、下記のように書かれており、AtCoderのアカウントを所持していない者を対象としていることが分かる。このAPG4bにとり組むことにより、コンテストへの参加方法や解凍の提出方法も学ぶことが出来るため、ここから取り組むのが王道だと思われる。
  
• M - 1.12.文字列と文字では、標準入力から1行を丸ごと1変数で受け取るときのコマンドgetlineが書かれていた。getlineを使った入力は、それまでのcin <<の方法とは異なる。例えば、下記のような感じになる。

#include <bits/stdc++.h>
using namespace std;
int main(){
    
int a,b;
cin >> a >> b;
cout << a << b << endl;

string c,d;
cin >> c >> d;
cout << c << d << endl;

char e,f;
cin >> e >> f;
cout << e << f << endl;

string g;
getline(cin, g);
cout << g << endl;

string h;
getline(cin, h);
cout << h << endl;
}

//標準入力
123 456 789
abc def ghq
hello world!

//標準出力
123456
789abc
de
f ghq
hello world!

• 上記のとおり、int変数やstring変数は、標準入力上の「空白」や「改行」で区切られた値が入力され、char変数は、標準入力から1文字ずつ入力されるところ、getlineは、標準入力上の「改行まで」の値が入力される。

AGP4bで学ぶAtCoder知識（前編：第2章までの話）

• ここでは、1章以降で書かれている、AtCoderに関する知識を書く。
• AP2 - 付録2.提出結果の見方によると、提出後のエラー判定種類は以下の通り。
  
• 論理エラーとは、コンパイルも通って、実行時エラーも発生しなかったけど、標準出力に出力された答えが間違っていたと言うこと。実際は、提出前にコードテストするだろうから、実際に目にするのは、WAかTLEだけだろうね。
• W - 2.06.計算量は、今回、APG4bを読んでみようと思った主目的。
• ここでは、オーダー記法$O(・)$についての説明がされているけど、ここはちょっと説明の順番が悪いね。for文のN回ループの時間計算量が$O(N)$ですと示した直後、いきなり「$3N^2+7N+4$という式はオーダー記法では$O(N^2)$と表されます。」と書いていて、初学者はポカーンとなる事間違いなし。$N^2$はfor文の入れ子と関連するステップ数を表すのかな？と勘のいい人は思うかも知れないけど、そもそも、for文の入れ子の外側と内側の繰り返しの数が一致する事なんて一般的じゃないから、普通は「いきなり出てきた$N^2$って何なの？」と思うよね。
• まあ、後から$N^2,logN,NlogN$の実例は出してるね。でも、$2^N$の例は出してないのに、計算量比較で、$O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N)$とか説明している。$2^N$はAC - 3.05.ビット演算に出てくるbit全探索の計算量だね。
• この項目で、「AtCoderのジャッジでは1秒あたり$10^8$回程度の計算が可能です。」と書かれている。
• EX21 - 計算量の見積もりの問題の正解を選んで、コードテストで試す(N=10^6,M=10^2)と44msで時間内に終わるけど、間違えると10511msもかかって、timeoutとなった。ちなみに、paiza.ioで試すと、正解を選ばなくても、timeoutにならずに計算できた。

AGP4bにおけるc++の豆知識（前編：第2章までの話）

• AtCoderに直接関係しないけど、c++について気付いてなかった豆知識的なことが大量に書かれてたから、自分用の備忘の意味も込めて書いておく。

• ちなみに、c++の文法の基礎から書かれているから、他言語からc++に移った人は、まず、AGP4bの一章から一通りやった方が良いと思ったよ。

• B - 1.01.出力とコメントにC++で文字列を出力するには cout（しーあうと） を使います。と書いてあった。初めて読み方を知ったよ。まあ、他の読み方はないかもしれんけど、下手したら、人前で「こーと」と読んで、恥をかいたかもしれない。ありがとう、AtCoder!

• 剰余計算「A % B」について、下記の通り、Bの正負は無関係というのは認識がなかった。この理由は、「(A / B) * B + (A % B)　＝　A　とするため」とのこと。
  

• Y - 3.01.数値型に書いてあったけど、c++も自動的な型変換はあるのね。c++は自動的な型変換はないと誤解してたわ。
  

• E - 1.04.変数と型をみると、c++の変数って、初期化しないまま使っても、コンパイルエラーも実行時エラーも起きないのね。バグ取りの時、不便じゃないの？

#include <bits/stdc++.h>
using namespace std;

int main() {
  int name;
  cout << name << endl; //なにが出力されるかわからない
}

• I - 1.08.変数のスコープでは、使うべきではないけどエラー無く動いてしまう仕様（内側スコープで、外側スコープの変数名を上書きできる）も紹介されていた。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int x = 5;
  cout << x << endl; // 5

  if (x == 5) {
    cout << x << endl; // 5

    string x = "hello"; // int x = 5;のスコープと重なっている
    cout << x << endl; // hello
  }

  cout << x << endl; // 5
}

• M - 1.12.文字列と文字 では、文字列リテラルにsを付けることで、string型のメソッド（例：size()）を利用できることが書かれていた。arduinoでは使う場面がなかったから、知らんかったよ。

  string str = "Hello";
  cout << str.size() << endl; // 5
  cout << "Hello"s.size() << endl; // 5（sを末尾につける）

• そういえば、arduinoで配列を使ったことなかったから、N - 1.13.配列でvectorを今回初めて知ったわ。ちと恥ずかしい。
• でも、vector<型> 配列名(要素数, [初期値]);の書式は、馴染みのあるswiftの配列と定義の仕方が似ててちょっと安心。考えてみたら、swiftはc++ ⇒ objective-c ⇒　swift のように発展してきてるもんね。

// 3個の入力を受け取れるように 3要素の配列 {0, 0, 0} で初期化
vector<int> vec(3);

// atを使って1つずつ入力
cin >> vec.at(0) >> vec.at(1) >> vec.at(2);

• 下記の関係を見ると、string型の実体は、char型の配列（vector）の機能拡張版って感じ？

  // 文字列
  string str; // 文字列変数を宣言
  str = "abcd"; // 'a', 'b', 'c', 'd' という文字(char)の列を代入
  cout << str.at(0) << endl; // 1つ目である'a'を出力
  cout << str.size() << endl; // 文字列の長さである4を出力
 
 
  // 配列
  vector<int> vec; // int型の配列変数vecを宣言
  vec = { 25, 100, 64 }; // 25, 100, 64 という整数(int)の列を代入
  cout << vec.at(0) << endl; // 1つめである25を出力
  cout << vec.size() << endl; // 配列の長さである3を出力

  //要素の追加と削除
  vec.push_back(10); // 末尾に10を追加
  

• また、配列は主に3つの表現方法があると紹介されているが、AtCoderでの推奨はvector型とのこと。2つ目の書き方はarduinoでもよく見るね。

vector<int> data(3); // vectorによる配列
int data[3]; // Cの配列
array<int, 3> data; // arrayによる配列

• また、AtCoderでは、配列の添字についてもat()方式書くことを推奨しているとのこと。それは、エラー時のメッセージが、at()方式の方が情報が多いためらしい。

  vector<int> vec = { 1, 2, 3 };
 
  cout << vec.at(0) << endl;
  cout << vec[0] << endl; // .at(0)と同じ

• O - 1.14.STLの関数では、STLの関数が説明されている...STL?
• STLって何？Standard Template Libraryのことらしいけど、一般用語なの？wikiで調べたら、c++でのmin,ｍax,sortなどのメソッドもSTLだし、前記の配列vectorもSTLらしい....?
• なお、vectorを使うためには、#include <vector>が必要で、minを使う場合は#include <algorithm>が必要らしいけど、これらは<bits/stdc++.h>に含まれているから、追加でincludeする必要はないみたい。特に便利な関数ライブラリとだけ記憶してれば良いみたい。
• で、配列の並び替えメソッドがsort(配列変数.begin(), 配列変数.end());だと？

    vector<int> vec = {2, 5, 2, 1};
    sort(vec.begin(), vec.end()); // {1, 2, 2, 5}

• 糞面倒だな。.begen .endの必要性が全く理解できない。swiftなら、vec.sort()で終わるのに。
• P - 1.15.関数を見ると、intで定義した関数で、戻り値がない場合でもエラーが起きないんだなc++って。swiftに慣れた身からすると、気持ち悪いよ〜。

#include <bits/stdc++.h>
using namespace std;

// 関数定義
#include <bits/stdc++.h>
using namespace std;

int my_min(int x, int y) {

  if (x < y) {
    return x;
  }

  // x >= y のときのreturn忘れ
}

int main() {
  int answer = my_min(10, 5);
  cout << answer << endl;
}

• 再帰関数の解説もあった。たしかに、そんなのあったね。調べてみたらswiftでも出来るみたい。使ったことないけど。

// 0からnまでの和を求める関数sum
int sum(int n) {
  if (n == 0) {
    return 0;
  }
  return n + sum(n - 1);
}

• R - 2.01.ループの書き方と範囲for文をみたら、範囲for文の書き方が書いてあった。arduinoではあまり使ったことないから、覚えてなかった。

  vector<int> a = {1, 3, 2, 5};
  for (int x : a) {
    cout << x << endl;
  }

• T - 2.03.多次元配列を見ると、2次元配列の宣言がvector<vector<要素の型>> 変数名(縦の要素数, vector<要素の型>(横の要素数));で、初期値を省略すれば、vector<vector<要素の型>> 変数名;でいける。swiftのvar 変数名:Array<Array<Int>>と似てるね。swiftはvar 変数名:[[Int]]とも書けるから、楽でいいけどね。

  // int型の2次元配列(3×4要素の)の宣言
  vector<vector<int>> data(3, vector<int>(4));
 
  // 入力 (2重ループを用いる)
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
      cin >> data.at(i).at(j);
    }
  }

• c++だと、二次元配列の初期化時の要素数省略は、下層のみ可能で、上記例(3x4要素)で言えば、vector<vector<int>> data(3);(3x？要素)と書くのが精一杯。ダサいわ〜。
• 二次元配列の初期化方法は、他にもある。

// vector を用いた2次元配列
vector<vector<int>> data(3, vector<int>(4));  // 縦3 x 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス　(1番目から数えていることに注意)

// array を用いた2次元配列
array<array<int, 4>, 3> data = {};  // 縦3 × 横4 の2次元配列
data.at(1).at(2)  // 上から2番目、左から3番目の要素へのアクセス

// Cの配列を用いた2次元配列
int data[3][4] = {};  // 縦3 × 横4 の2次元配列
data[1][2]  // 上から2番目、左から3番目の要素へのアクセス

• U - 2.04.参照に値渡し、参照渡しの話が書いてある。図もあって分かり易い。つかブラウザでこんな風に勉強できちゃうと、参考書って買う意味なくなっちゃうよね。そもそも、手を動かしながら勉強できるブラウザの方が参考書より上だよね。義務教育で使う英語の教科書も、Web上で完結させた方が効率いいんじゃ無いかなと思うわ。音声も動画もすぐに使えるし、紙の教科書を持たせる意味がないわな。重いし。
• 値渡しより、参照渡しを使った方が良い例が示されている。具体的には、値渡しは「コピー」処理が発生するから、それを回避できる参照渡しの有用性が示されている。下記の参照渡しでの実行時間は15msであるところ、値渡しに変更すると、7813msとなり約500倍となる。こういう、具体例で必要性が示されるって、学習者にとっては結構重要だよね。

// 配列の先頭100要素の値の合計を計算する (参照渡し)
int sum100(vector<int> &a) {
  int result = 0;
  for (int i = 0; i < 100; i++) { //先頭100要素だけの加算
    result += a.at(i);
  }
  return result;
}

int main() {
  vector<int> vec(10000000, 1);  // すべての要素が1の配列(1000万要素)

  // sum100 を500回呼び出す
  for (int i = 0; i < 500; i++) {
    cout << sum100(vec) << endl;  // 参照渡しなので配列のコピーは生じない
  }
}

• なお、参照渡しの「&」の位置は自由度高すぎなんだけど、次のことに注意とのこと。つまり、変数の直前に付けた方が勘違いしにくいとのこと。知らんかったわ。

int a = 123;

//&の位置の自由度高すぎ
int &b = a; // 変数の直前
int & c = a; // 型と変数の間
int& d = a; // 型の直後

//気を付けるところ
int & e = a , f = a; //eは参照渡し、fは値渡し

• また、参照先を配列の要素とした場合、要素数を変更させると、参照先が意図した場所とずれてしまうことがあるため注意とのこと。

  vector<int> v = {1, 2, 3};
  
  int &e = v.at(1);
  // 大量のpush_backで要素数を大幅に増やす
  for (int i = 0; i < 1000; i++) {
    v.push_back(i + 4);
  }
  cout << "e: " << e << endl;  // "e: 2"とならないことがある

• 参照渡しの文法がうろ覚えの人は、EX19 - 九九の採点を解いた方が良いよ。関数の引数として参照渡しするときは、swiftの「inout」は型の前に付けるけど、c++の「&」は変数の前に付けるんだよな。こんがらがるわ。
• なお、この「参照」の項目では、「ポインタ」という言葉は使ってなくて、「ポインタ」の説明は4章の最後の方で、「参照渡し」と完全に切り離して行っている。まぁ、何も考えてない参考書の作者は「参照渡し」と「ポインタ渡し」を同時に教えるアホなことを平気でするけど、APG4bでは、そもそも「ポインタ渡し」なんて用語を使わないし、好感度高いっす。アホなことする人はC言語から入った人なんだろうね。C言語には「ポインタ渡し」しかなかったし、関数の引数に値渡しっぽい感じでデータを渡して、実際に関数に渡されるのはポインタの方ってのは、感覚的に許せないのかもね。初学者にとって同時に2つの文法を教えられるのは頭がこんがらがるだけの、作者の自己満足でしかないけどね。つか、swiftでは、関数の引数を参照渡しで渡すとき、&を付けて渡してるけど、これは値渡しとの差異を明確に示してて綺麗だね。やっぱり、swift最高！！
• でも、EX19 - 九九の採点をswiftで書き換えたら、3倍も時間がかかったよ。メモリも倍以上喰ってるしね。駄目だコリャ。コード長は半分以下ですっきりしてるのにね。時間差は、標準入力の取込みの差が出たのかな？
  
• V - 2.05.再帰関数では、再帰関数が威力を発揮する「ツリー構造」問題が例示されていた。再帰関数について、なるほどねぇと理解したわ。つか、こんなの、競技プログラミングで問題が出たときに、前知識なしに解けるワケないね。
• ただし、解説コードの二次元配列名にchildrenって名前を付ける感覚がよく分からない。二次元配列の下層配列の名称がchildrenになるのは分かるけどね。ただまぁ、childrenの配列だからってchildrensって書いたらスペルミスっぽくて格好悪いのも分かる。parent_child_relationsだと長すぎるか。
• また、swiftで書き換えたら、時間3倍、メモリ2倍ですよ。まあ、2000ms、256MBが提出制限だから誤差みたいな差だけどね。
  

終わりに

• APG4bの前半だけでも、かなりお腹いっぱいの内容だった。
• arduinoでは、c++の狭い範囲の知識しかカバーできてなかったと実感した。
• そしてまた、改めてswiftって良いなと思ったね。まぁ、後発言語の方が良いに決まってんだけど。