AtCoderチャレンジまとめ（１）
やりたいこと
そんなわけでAtCoderにチャレンジ ！ の前の準備笑
教科書
けんちょんさんわかりやすい記事ありがとうございます！
計算オーダー
名言 : 標準ライブラリがあっても、中身の計算量を意識しよう！ ex: list (Python) からの検索処理は遅い
計算回数の目安: 1秒間で処理できる for 文ループの回数は、100,000,000 回程度(10の8乗)
計算時間の比較: logn < n < nlogn < n2 < n3 < 2n < n!
- 実用的なレベルとして、n3あたりが限界
全探索
幅優先探索 : グラフ を始点から近い順に1つずつ調べていく探索法
- 深い階層まで一本道で探索する場合は幅優先探索が有用。 ex: 迷路でスタートからゴールにたどり着きたいケース
深さ優先探索 : ある状態から始めて、遷移できなくなるまで状態遷移を続け、遷移できなくなったら一つ前の状態に戻って・・・を繰り返すことで、 グラフ の全頂点を漏れなく調べる探索法
- 1つの階層に大量のノードが存在する場合は深さ優先探索が有用。 ex: 辞書順で最初の解を求めるケース
があり、どちらを選択するかは問題に依る。
ソート
既存のライブラリの性能が高い。 ex: C++ の std::sort() はクイックソートをベースとしながらも最悪時の計算量も O(nlogn)O(nlogn) になっている
安定ソート : 同等なデータのソート前の順序が、ソート後も保存されるもの
ソート種類
- 挿入ソート : 基本的にはそんなに速くない安定ソート。
- マージソート : 高速な安定ソート。
- クイックソート : 安定ソートでないが高速。C++ の std::sort() もクイックソートがベース。
- ヒープソート : 最小値や最大値を常に取り出せるようなアルゴリズムで、安定ソートではない。
参考: ソートを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
bit演算
45をbitで表すと？ : 0b00101101(0bは二進数を表す)
AND : int a,b; cout << a&b << endl;
OR : int a,b; cout << a|b << endl;
& ビットごとの AND | ビットごとの OR ^ ビットごとの XOR ~ ビットごとの反転（1 の補数） << 左シフト >> 右シフト
bitsetsで出力 : int a,b; cout << bitset<8>(a&b) << endl; // 00001001のように表示される
a ,b ,c 番目のフラグが立っている状態 : (1<<a) | (1<<b) | (1<<c)
マスク演算 : bit & mask ; // mask で表された部分の情報のみを取り出したもの
所感
次は練習問題をいろいろ解いてみよう。 D問題普通に難しい。。。
