maktopia

make-u-topia

とりあえず授業を生き残るC++のお作法

プログラミング

とある学科のとある講義のシケプリのようなもの

RubyやPythonで簡単にできることが, C++だと面倒だったりする.

そういった非本質な部分で時間を取るのは, あまり意味がない*1 と思うので, 適当に並べておく

文法を忘れたとき

リファレンスを読む. 英語の方が情報が正確だと多分おすすめされるが, 別に日本語でもいいと思う.

Reference - C++ Reference

cpprefjp - C++日本語リファレンス

リファレンスを探すのが面倒なときなどはGoogle先生に聞いてもいいが, 情報が正しくない場合があったり, C言語の情報だったりするので, 自己責任で.

入出力

配列

vectorでちゃんと取るほうが個人的にはおすすめ

\displaystyle N\\ a_1, a_2, ..., a_n

入力のサンプル

#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++)
    cin >> a[i];
  /*  C++11
  for(auto& x: a)
    cin >> x;
  */
}

配列aをグローバル変数におきたいときは,

vector<int> a;
int main(){
  int n;
  cin >> n;
  a.resize(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
}
  • vector(n, val)でvalで配列を初期化できる.
vector<int> a(n, 10);
// a = [10, 10, 10, ...]

  • 要素数が与えられない配列を読むとき(たぶん稀) cin.eof()とかgetline(cin, s)とかで調べる.

  • 大きさが謎な配列bの要素を全部出力したいとき

for(i = 0; i < b.size(); i++)
  cout << b[i];
/* C++11
for(const auto& x: b)
  cout << x;
*/

2次元配列

N×Nの2次元配列

vector<vector<int> > a(n, vector<int>(n));

文字列

std:string使う

#include<string>
int main(){
  string s;
  cin >> s;
}

stringの1文字ずつに何かしたくなったらs[i]で取り出せる.

ソート

#include<vector>
#include<algorithm>
...
  sort(a.begin(), a.end());
  // aがソートされてる
...

デフォルトでは昇順(小→大). 降順にしたいときは

#include<functional>

して,

  sort(a.begin(), a.end(), greater<int>());

ハッシュ

文字列などをキーにして検索したいとき, RubyのHash, Pythonのdictのようなものが欲しくなる C++では #include<map>, #include<unordered_map>が使えるが, 特に理由がなければunordered_mapを使う. C++11以降を要求するのでコンパイルオプションに注意

#include<unordered_map>
...
unordered_map<string, int> mp;
mp["hoge"] = 1;

地味な罠として, 存在しないキーを見に行くだけで勝手に要素が追加されてしまう.

unordered_map<string, int> mp;
cout << mp["fuga"] << endl;
// 何も言わずに0が出力され, mp.size()が1になっている

あとでunordered_map内を総なめするときなどは注意. 防止するには, 存在をチェックしてからアクセスする

if(mp.count(key) != 0){
  cout << mp[key] << endl;
}

関数

返り値を複数渡したい

std::tupleとかstd::pairとか

引数に配列を渡す

int func(vector<int> a);

とかやると, コピーが発生するので, サイズが大きいととても遅い 参照で渡すのが楽

int func(vector<int>& a); // 中身を変更し得るとき
int func(const vector<int>& a); // 中身を変更しないとき

Math系

切り捨て四捨五入

aが正の小数なら

int b = (int)a; // 切り捨て
int c = (int)(a+0.5); // 四捨五入

で済む. 切り上げとか負のときとか, 考えるのがめんどくさければMath.round(), ceil(), floor()などを使う

累乗

n乗( n\in\mathbb{N})なら

x = 1
for(int i = 0; i < n; i++)
  x *= a;

で十分. ( n\not\in\mathbb{N})はMath.pow(double, double)

なんかバグった / ACしなかった

WA

WAの数が多かったら大体アルゴリズムが間違ってるので, もう一度考える. WAの数が1個とかだったら, 制約条件の境界付近とか, その他特徴的な入力で間違っていることが多い気がする. あとは配列外参照で謎なメモリ領域を見てしまってたりとか 極稀にやってしまうのが, デバッグ出力を放置したまま提出するとか

TLE

自分のアルゴリズムが答えを出すのにかかる時間のオーダーを計算して, 間に合うかどうかを考えてみる. 1secで 10^8 くらい演算ができるので, 制約条件を見て確かめる.

どう考えても間に合いそうだったら, どっかで無限ループに入ってるのでバグ取りの翁してください.

RE

だいたい配列外参照 デバッグ用に出してたstd::cerrの出力のせいでREが出ることがある.

なんかよくわからんけど困った！

先生もおっしゃってるように, 同じことをずっと考えてるぐらいなら先生を頼ってください. めちゃくちゃ親切に教えてもらえます.

他思い出したら追記するかもしれない

*1:必要なこともある

i have no words.