今までいろんな人に何回も説明した内容は、これからも何回も説明することになりそうなので、記事としてまとめておいてみます。 自分としてもこの記事へのリンクを貼ればよい上、読んだ人が(辞書で隣の単語もまとめて覚えるみたいな感じで)別のことも知れたらよさそうだと思ったので。
「これはこう書けるよ」系の紹介をするのではなく、「このおまじないがわかりません」系の解説をしたいと思っています。
わからないことがあれば、#助けて競プロer のタグでツイートする か、PROCON-QA で質問する (サイト閉鎖しちゃったね)といいと思います。
よく見る質問については追記しようと思います。直接えびちゃんにリプライしてくれてもいいです。
以下では std::
をつけて表記しますが、using namespace std;
などをしている人は、(ここで紹介されたイディオムを書く際に)省略して構いません。
たとえば、std::cin
を cin
と書けます。
↑これはわざわざ明記しなくてもいい気もしたんですが、std::
を見たことすらない状態で using namespace std;
をおまじないとして使っている人にとっては非自明かもしれないと思ったので。
説明が必要そうな用語については、一番下のセクションでカバーできるように努力します。
「この文はどういう意味ですか」系
std::cin.tie(nullptr)
標準入力からの読み取りをする std::cin
は標準出力へ書き込みをする std::cout
に結びつけ (tie) られています。
この状態では、std::cin
から読み込みをするたびに std::cout
が flush されます。
flush は比較的重い処理なので、入力のたびにそうした重い処理をさせるのを防ぐための文です。
tie
の引数は結びつけられる出力ストリームへのポインタです。
nullptr
を渡すことで、どのストリームも結びつけられていない状態にできます。
何かしらの理由でデフォルトの状態に戻したい場合は std::cin.tie(&std::cout)
をするとよいです。
std::cin.tie(0)
でも std::cin.tie(nullptr)
と同じ動作をしますが、ポインタを渡しているように見えやすい後者の方を推します。
flush の説明は下に書くとして、tie(nullptr)
な状態だと次のような感じになります。
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << "整数を入力してね\n"; int n; std::cin >> n; std::cout << n << '\n'; }
std::cin
の入力待ちの際に「入力してね」のメッセージが出力されないため、困ってしまいます。
なんですが、競プロの文脈ではこうしたメッセージを出力する必要はないですから、tie させておく理由はないでしょう。
std::ios_base::sync_with_stdio(false)
C の <cstdio>
での入出力(典型的には scanf
/printf
など)と C++ の <iostream>
での入出力(典型的には std::cin
/std::cout
)がありますね。
C++ の入出力と C の入出力が混在してもこわれないように同期が取られているんですが、これを呼ぶことで各々を独立に扱うようになります。 C++ 側の入出力クラスが、勝手にバッファしたりできるので高速になったりすると思います。
while (std::cin >> n, n)
AOJ でよく見ますね。複数のテストケースを一回の実行で処理する場合のイディオムです。
この ,
はカンマ演算子と呼ばれるもので、a, b
は「a
の後に b
を処理して、b
を返す」ものです。
標準入力から整数を読み、それが 0
でない限りループする、という文です。整数を bool
に変換すると 0 のとき false
、それ以外のとき true
になります。
ところで、えびちゃん的には、複数のテストケースはループよりも関数で処理した方がバグらせにくいと思っています。
初期化忘れや変数名の衝突を防げたり、多重ループの途中で処理を終えたら return 0;
で抜けられる(余計なフラグ変数などを増やすことによるバグを防げる)などがメリットです。
int testcase_ends() { if (入力終わり) return 1; 処理をがんばる return 0; } int main() { while (!testcase_ends()) {} }
返り値については、単一テストケースの場合の main
と揃えています。
while (std::cin >> n)
「std::cin >> n
が真である限りループする」なんですが、std::cin >> n
の真偽がおまじないだと思います。
std::cin >> n >> m
という書き方ができることをイメージするとわかりやすいと思うんですが、std::cin >> n
は n
を読んだ後の std::cin
自身を返します。
よって、上のループは次のループと同じです。
while (std::cin >> n, std::cin)
そこで、bool(std::cin)
が何かなんですが、読み込みに失敗していたら false
になります。
失敗というのは「入力の末尾に達した」とか「整数を読みたいのに整数でないものを読んだ」とかです。
すなわち、入力に失敗するまでループを継続します。
std::cout << std::fixed << std::setprecision(16)
デフォルトでは浮動小数点数は 6 桁くらいしか表示してくれないので、誤差に厳しい問題では望み通りの値が出力されません。
そこで、std::setprecision
で所望の桁数を指定することでそれを解決しています。
std::fixed
は固定小数点数として表示するもので、0.000000001
が 1e-09
のように出力されるのを防ぎます。
while (scanf("%d", &n) != EOF)
動作自体は while (std::cin >> n)
に似ています。
scanf
にも返り値があり、読み込みをした個数を返します。
ただし、1 個も読めずに入力の終端に到達した場合は EOF
を返します。
(注)%d
で読み込む場合、入力が "a"
の場合は 0
が返りますが、""
の場合は EOF
が返ります。
よって、(入力の形式が想定通りという仮定の下で)整数の入力がある限り処理を続けることになります。
while (~scanf("%d", &n))
EOF
の値は処理系定義で、負の値であることしか定められていませんが、-1
であることが多いです。
さらに、負数は 2 の補数表現を用いて表す処理系が多い(そのうち処理系定義ではなく規格でそうなりますが)ので、ビット反転の演算子 ~
を用いることで、上の != EOF
を短く書けるというものです。
(個人的には)あまりすきな書き方ではないです。
#define _GLIBCXX_DEBUG
デバッグ機能を有効にします。GCC で使えます。
std::vector
で配列外参照をした場合、普通は未定義動作(実行時エラーとは限らない)なのですが、これをしていると実行時エラーになってくれます。
std::vector
以外の STL の各コンテナにおける多くの未定義動作を実行時エラーにしてくれて、バグの存在を知りやすくなります。
「これはどうしてだめなんですか」系
std::cout << std::endl
まず、<< std::endl
を「改行する(だけ)」として認識されているのがよくなさそうです。
改行した後に flush を行います。なので重くて、TLE したりします。
#define int long long
A translation unit shall not
#define
or#undef
names lexically identical to keywords
と規格に書かれているからです。未定義動作でも動けばいいと思っている派閥の人は好きにしたらいいと思います。 GCC では許されているらしいです。ソース
「デバッグしてほしい」と他人にコードを見せる際は行わない方が無難です。 これをしていない人にとっては読みにくいことが多いので。
std::set
に対する std::lower_bound
\(O(\log(n))\) 時間で行えないからです。\(O(n)\) 時間になります。
過去に詳しめの記事を書きました。
std::multiset
に対する .erase(x)
や .count(x)
過去に詳しめの記事を書きました。
ループ中での std::ios_base::sync_with_stdio(false)
入出力をしてからこれを読んだ場合、(処理系定義ですが)バッファが破棄されたりすることがあるので、こわれる場合がありそうです。
while (std::cin >> n)
が手元でうまくいかない
うまくいっています。
前述の通り、これは「失敗するまで入力を行う」ので、入力を失敗させてやる必要があります。 具体的には、入力終端 (EOF; end of file) を送ってあげる必要があります。
方法は簡単には二つあります。
入力をファイルにしてしまって、そこから読み込む方法です。
$ ./a.out < sample.in
Windows のシェルだとできないかも?
あるいは、EOF をキー入力で伝える方法です。 「Ctrl+Z を押して Enter」か「Ctrl+D」でできると思います。シェルによります。
#define _GLIBCXX_DEBUG
そもそもデバッグ用の機能であることを意識しましょう。
std::vector
の operator []
などでは、境界チェックを行うので定数倍が重くなります。
一方で、std::lower_bound
など、前提条件のチェック(二分探索が可能か?)に線形時間かかるものは、全体のオーダーも悪化しうるので、注意が必要です。
sort
の比較関数にメンバ関数を渡す
蟻本にある接尾辞配列をクラスの形で実装しようとする人がほぼ陥るやつです。
渡せないことになっているからです(なんで?)。
static
のついたメンバ関数であれば渡せますが、そうした関数はインスタンスに関係なく呼び出せる必要があります。
すなわち、メンバ変数(今回の例における rank
など)は参照できません。
よって、今回の例においてメンバ関数を用いるのは適当ではなさそうです。
ラムダ式を用いて rank
をキャプチャしてしまうのが楽でしょう。
std::sort(sa.begin(), sa.end(), [&](auto i, auto j) { // rank などを用いた比較を書く });
「なんでこう書く必要があるんですか」系
重複を取り除くやつ
a
から重複を取り除くときのイディオムとして、次のものがあります。
std::sort(a.begin(), a.end()); a.erase(std::unique(a.begin(), a.end()), a.end());
std::unique
は、「連続する値について、重複していたら先頭以外を取り除く」ことをします。
ここで言う「取り除く」というのは、後ろの方に追いやることを意味します。
なので、たとえば "abcbbcaaabb"
は "abcbcabxxxx"
になります。
xxxx
の部分は未規定な値になります*1。
(std::vector
以外にも使えます、念のため。)
予めソートしておくことで、すべての重複を除いて "abcxxxxxxxx"
にできます。
「std::unique
を呼ぶだけで "abc"
にしてほしい」と言いたげな人がたくさんいると思うんですが、それは無理というものです。
std::unique
に渡す引数はコンテナではなくイテレータなので、関数側からコンテナ自体の大きさを変えることができないためです。
さて、std::unique
の返り値は、上の説明の x
の開始位置を指すイテレータです。
そこで、その位置からコンテナの末尾までを消すことで、所望の結果を得ます。
std::next_permutation
の前の std::sort
について
a
の全順列についての処理をするイディオムとして、次のようなものがあります。
std::sort(a.begin(), a.end()); do { a についての処理 } while (std::next_permutation(a.begin(), a.end()));
next
の部分に注意して読みましょう。
この関数は、与えられた範囲について、辞書順で次に大きい順列にして、true
を返します。
辞書順で一番大きいものを渡した場合は、辞書順で最も小さい順列にして false
を返します。
なので、辞書順で一番小さいところの、sorted なものから始めることで全順列を生成できます。
知られてなさそうなんですが std::prev_permutation
もあります。
rep
マクロを使っている人にとっては、sort
するよりは 2 回繰り返す方がタイプ数が短そうですね。
rep(2) do { がんばる } while (std::next_permutation(a.begin(), a.end()));
最大値を求める場合はそれでいいですが、数え上げの場合はこわれるのでおすすめしません。
「この用語はどういう意味ですか」系
flush
標準出力に何かしらを書き出す処理をしたとしても、その時点で実際に出力が行われるとは限りません。
int main() { std::ios_base::sync_with_stdio(false); std::cout << "one\n"; 時間のかかる処理 std::cout << "two\n"; }
one
と two
が同時に出力されたりすると思います。
バッファリング (buffering) とか呼ばれていて、出力内容をためておいて必要になったらまとめて流す (flush) ようになっています。 flush は重めの処理です。読むといいかも
'\n'
の代わりに std::endl
を流すと同時でなく出力されたりすると思います。
競プロの文脈では(インタラクティブでない限り)、最終的に全部出力されていればよくて、この時点でどうだったとかは関係ないので、std::endl
を使う理由はあまりないでしょう。
とりあえずおわり。
何かあれば追記します。
*1:アクセスするの自体は許されています。