競技プログラミング初心者のためのTips

この記事は北九州高専コンピュータ研究部の2019年度の一年生の為に書かれたものです．
弊部の教育システムではしっかり教えて入れないのにも関わらず競技プログラミングの問題を解く上で必要な知識を一部ですがまとめました．
独学で競技プログラミングを学んでいた人にとっては常識的なことばかりを書いているかもしれないですがご容赦ください．

cin/cout の高速化

cin, cout は一般に同じ入出力関数である scanf, printf と比較すると遅いと言われています．
その解決方法は以下のように main関数 に記載することで高速化されます.

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

int main() {
  // ↓この２行が追加部分
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  cout << "Hello World!" << endl; 
}

そもそもなぜこれにより cin,cout が高速化されるのかという話ですが,
cinはデフォルトでcoutと紐づいています． これによりプログラムで処理を行う際にデータを一時的に格納するためのメモリ領域であるバッファーと呼ばれる領域内に貯められたデータを吐き出すといった処理をcinを呼び出す度に行われています．
そこで上記の2行でcinとcoutの関係性を切り離すという処理を行い入出力を高速化しています．

ただ，自分で経験した範囲ではこの記載がないとC++では解くことができない問題というものに遭遇したことはないので不要な知識かもしれないですが頭にとどめておいても良いかもしれません．

vector,stringの要素アクセス

普段at関数を用いることで配列の要素にアクセスしています．
これは[]を使うことで各要素にアクセスすることが可能です．

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

int main() {
  vector<int> vec = {1,2,3,4,5};
  string str = "abcde";

  // この２行は同じ結果
  cin >> vec.at(0);
  cin >> vec[0];

  // この２行は同じ結果
  cout << vec.at(0) << endl;
  cout << vec[0] << endl;

  // この２行は同じ結果
  cin >> vec.at(0); //->1
  cin >> vec[0]; //->1

  // この２行は同じ結果
  cout << str.at(0) << endl; //->a
  cout << str[0] << endl; //->a
}

多次元配列にアクセスする際は以下のようになります．

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

int main() {
  vector<vector<int>> vec(4, vector<int>(4));

  // at関数を使用したパターン
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      cin >> vec.at(i).at(j);
    }
  }
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      cout << vec.at(i).at(j) << " ";
    }
    cout << endl;
  }

  // []を使用したパターン
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      cin >> vec[i][j];
    }
  }
  for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
      cout << vec[i][j] << " ";
    }
    cout << endl;
  }
}

基本的にat関数と[]の挙動は基本的には同じですが以下のような違いがあります．

at関数の場合は範囲外を参照したときにエラー(std::out_of_range)になりますが、
[]の場合は普通に配列外参照をし、エラーになりません。

そのため、[]の場合はインデックスの指定をミスしてもとりあえず動き、謎の値が返ってきます。

配列

vectorと似たような機能をもつデータ構造です．

宣言方法は以下のような方法です

型 変数名[要素数];

実際の使用例は以下のようです．

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

int main() {
  int n;
  cin >> n;
  int a[10];
  for(int i=1;i<=n;i++)a[i-1] = i*i;
  for(int i=n;i>=1;i--)cout << a[i-1] << " ";
  cout << endl;
}

注意点として.at()や.size()といった関数は存在しないためvectorより不便に感じることは多いかもしれません．
ちなみに多次元配列を利用する際は以下のようになります．

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

int main() {
  int n;
  cin >> n;
  int a[n][n];
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      a[i-1][j-1] = i*j;
    }
  }
  for(int i=n-1;i>=0;i--){
    for(int j=n-1;j>=0;j--){
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
}

各種参考文献はvectorではなくこちらの配列を使用することも少なくないので頭に入れておくことをお勧めします．

キャスト変換 と 桁数指定

弊部の講義の最終到達地点の範囲外ですがAPG4bの3章の一番最初を読んで見ましょう．
https://atcoder.jp/contests/apg4b/tasks/APG4b_y

200点問題以降必要になる可能性がある知識なので確認するようにしてください．

ASCIIコード

char型は数字として扱うことが可能です．

そのためchar型をint型にキャスト変換をすると以下のようになる．

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

int main() {
  char a,b,c,d;
  a = '0';
  b = '1';
  c = 'A';
  d = 'a';

  //int型にキャスト変換する
  cout << (int)a << endl; //-> 48と出力
  cout << (int)b << endl; //-> 49と出力
  cout << (int)c << endl; //-> 65と出力
  cout << (int)d << endl; //-> 97と出力
}

次は逆に逆にint型をchar型にキャスト変換する．

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

int main() {
  char a,b,c,d;
  a = 48;
  b = 50;
  c = 65;
  d = 100;

  //int型にキャスト変換する
  cout << (char)a << endl; //-> 0と出力
  cout << (char)b << endl; //-> 2と出力
  cout << (char)c << endl; //-> Aと出力
  cout << (char)d << endl; //-> dと出力
}

このようにint型の数値と文字列は1:1で対応している．
その対応表は以下のサイトが参考になります．
https://qiita.com/disapalt/items/7c816f8460c3969662f6

これを利用することで以下のようなことができたります．

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

int main() {
  string s;
  cin >> s;
  cout >> "> ";
  for(int i=0;i<s.size();i++){
    if(65 <= s.at(i) && s.at(i) <= 90){ // この範囲は大文字が格納されている
      cout << (char)(s.at(i)+32); // 大文字を小文字に変換
    }else if(97 <= s.at(i) && s.at(i) <= 122){ // この範囲は小文字が格納されている
      cout << (char)(s.at(i)-32); // 小文字を大文字に変換
    }else {
      cout << s.at(i);
    }
  }
  cout << endl;
}

$ ./test
abcDEF100
> ABCdef100

このように大文字小文字を数字を32だけずらすことで変換できたりします．

long long int 型

int型は32bit変数です．
こんなの言われても「は？」となると思いますが簡単にいうと
最低値が $-2^{31}=-2147483648$ で最大値が $2^{31}=2147483647$
ということです．
Atcoderの300点以上の問題では最大値最小値がそれを超える場合があります．
その対策として long long int 型を使用するというものがあります．
これは64bit変数と呼ばれるもので
最小値が $-2^{63} = -9223372036854775808 $
最大値が $2^{63} = 9223372036854775807 $
という変数です．

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

int main() {
  int a = 9223372036854775807;
  cout << a << endl;
  long long lla = 9223372036854775807;
  cout << lla << endl;
}

これを実行すると

$ ./test
-1
9223372036854775807

範囲外に収りきっていない場合は違う値が帰ってくれるのでこれがバグの原因になったりするのでメモリに余裕のある場合はできる限り long long を使用する習慣を意識づけても良いかもしれません．

math

APG4bに記載されていないですがよく使う関数が色々あるので記載

abs

引数の絶対値を返す関数です．二変数の差を求める際によく使います．

cout >> abs(100) >> endl; // 100
cout >> abs(-120) >> endl; // 120
cout >> abs(100-120) >> endl; //20

pow

pow(a,b)の場合, $a^b$ を返します．

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

int main() {
   double x, y, z;

   x = pow(4,2);
   y = pow(2,3);
   z = pow(2,0.5);
   cout << x << endl; // 16
   cout << y << endl; // 8
   cout << z << endl; // 1.41421
}

参考文献

• 競技プログラミングにおけるコードの書き方とその利便性
• C++における「std:flushとstd:endlの違い」
• C++入力の速度測定
• C++高速化
• 競プロ初心者が書く｢標準入出力からはじめる競プロ入門｣
• バッファー ‐ 通信用語の基礎知識
• フラッシュ (処理) ‐ 通信用語の基礎知識
• vector.at(index)とvector[index]の違い
• C++初心者がC++を使って競技プログラミングするための備忘録のようなもの
• 【C言語/C++】データ型の最大値と最小値の一覧【32/64bit環境 limits.h/stdint.h】
• 競技プログラミング for beginners! ～C++実装テク編～