目次
atcoder abc
1-1. 全探索：全列挙
1-2. 全探索：工夫して通り数を減らす全列挙
1-3. 全探索：ビット全探索
1-4. 全探索：順列全探索
2-1. 二分探索
2-2. 深さ優先探索
2-3. 幅優先探索
3-1. 動的計画法：ナップザック DP
3-2. 動的計画法：区間 DP
3-3. 動的計画法：bit DP
3-4. 動的計画法：その他
4-1. 最短経路問題：ダイクストラ法
4-2. 最短経路問題：ワーシャルフロイド法
5-1. 最小全域木問題
6-1. 高速な素数判定法
6-2. 高速なべき乗計算
6-3. 逆元を使う問題
6-4. 累積和
6-5. Union-Find
6-6. その他のテクニック
6-7. 実装問題
6-8. 数学的な問題
調べたこと

atcoder abc

分野別初中級者が解くべき過去問精選 100 問

1-1. 全探索：全列挙

1-2. 全探索：工夫して通り数を減らす全列挙

1-3. 全探索：ビット全探索

おまじない行のうち何行か、列のうち何列かを 1 回だけ裏返し、せんべいが 0 になる枚数を求める問題。わからない
Buildings are Colorful! skip!

1-4. 全探索：順列全探索

C - Average Length 全ての点を通る経路の、長さの平均値を求める問題。
C - Count Order 全探索したい順列を作って、その順列がマッチするか判定すれば ok。
8 クイーン問題 N クイーン問題で調べると良いかも。prac ファイルの 31 行目以降（どのマス目におけば各クイーンは移動範囲が被らないか？の判定ロジックの部分）がわかってない。next_permutation の使い方はわかったので先に進む。

2-1. 二分探索

18 4_B - 二分探索

binary_search で true を返したらカウントをインクリメントして数えた。以前なら map で問いてたな。
19 JOI 2009 本選 2 - ピザ

lower_bound で宅配先から近い店舗を探す。店舗の配列の先頭だけでなく、末尾にも本店を追加することで、アルゴリズムが簡単になる。19 行目が肝。
20 AtCoder Beginner Contest 077 C - Snuke Festival

下の段より上の段のパーツが真に小さいパーツでできる祭壇が、何種類あるかを求める問題。下段を全探索したせいで、中段も一部全探索することになる。計算量が O(N^2(logN)^2)（？）になってしまった。中段を全探索することで、下段・上段は二部探索するのみで済み、計算量が O(NlogN)に。
21 AtCoder Beginner Contest 023 D - 射撃王

「整数 x が与えられた時に、最小のペナルティを x 以下にすることができるか」という判定問題。高さを二部探索。超いい問題。
22 AtCoder Regular Contest 054 B - ムーアの法則

三部探索。下に凸な関数に対して、最小値を求める際に使う。下に凸かどうかは 2 階微分が正であるかどうかで判定できる。考え方は、初期区間の端の点の値が、誤差範囲内で一致するまで区間を狭めていく。ただし点の取り方に注意。
23 JOI 2008 本選 3 - ダーツ

基本的な考え方は、全ての得点の通り（N+1）^4 を m で二分探索する。このままだと取りうる得点の値を準備する段階で TLE する。先に 2 本投げた時の得点の取りうる値は(N+1)^2 通り。次に 2 本投げた時の得点取りうる値も(N+1)^2 通りなので、(N+1)^2 通りに対して二分探索を(N+1)^2 回実行する。探索対象の配列は先に 2 本投げた得点の値で、flag は(m-後に二本投げた得点)。

2-2. 深さ優先探索

24 ALDS_11_B - 深さ優先探索

深さ優先探索の実装方法がわかる。準備するデータ構造: 探索済みかどうかのフラグ。実装の型: dfs 関数を用意し、探索済みでなければ再帰的に dfs を呼び出す処理を書く。注意点: 頂点が 1 初まりで与えられることが多いので、ループの範囲に注意。
25 AOJ 1160 - 島はいくつある？

解法の思いつき方: 「一つの島がどれだけ続いているか？」を調べるのに深さ優先探索を用いる。ある島に dfs を実行し、その周り 8 領域のうち島があるものに関して dfs を実行する。

問題の解法: dfs の中身で d[x][y]を 0 に置き換える。主プログラムでは全領域に対して dfs を実行するので、一度探索した領域を 0 にしておかないと重複して数え上げてしまうため。
26 AtCoder Beginner Contest 138 D - Ki

解法の思いつき方: 「一つの頂点がどれだけ（下に）続いているか？」を調べるのに深さ優先探索を用いる。ある頂点に dfs を実行し、それより下の頂点があればその頂点に dfs を実行する。

問題の解法: （ここが問題によって変わっていく（dfs の中身）。深さ優先の実装の構造(main->dfs)は変わらない）dfs の中身で、親の score をそのまま子供に渡す。子に渡される得点は、親のさらに親の数だけ、まとめられている。

TLE した部分: 問題文の通りに実装すると Q 回の dfs を実行することになる。これを 1 回の dfs にまとめる。（頂点 1, 得点 100）と、（頂点 1, 得点 10）で 2 回 dfs せず、(頂点 1, 得点 110)で 1 回 dfs する。
27 JOI 2009 予選 4 - 薄氷渡り

解法の思いつき方: 「一つの氷がどれだけ続いているか？」を調べるのに深さ優先探索を用いる。

問題の解法: main から dfs を複数回呼び出すのがこの問題が他と違うところ。それ以外は 25 と同じ実装方法。

わからなかった部分: どこから dfs をするか？->全探索でよかった-!(n, m が小さいから)

2-3. 幅優先探索

幅優先探索についてこちらのサイトURLで学ぶ。

幅優先探索の使い所: 最短経路アルゴリズム。探索の始点となる頂点から、各頂点への最短経路を求める。（各辺に重みがないことが条件->ダイクストラ法）

28 ALDS_11_C - 幅優先探索

幅優先探索の実装に必要なデータ構造(dist(訪問済み or 未訪問) と que(訪問予定))を学ぶ。
- 赤: 頂点が訪問済み <-> dist[v] == 1
- 橙: 頂点が発見済み・訪問予定 -> queue.push(v)
- 白: 頂点が未発見 <-> dist[v] == 0
29 AtCoder Beginner Contest 007 C - 幅優先探索

頂点を辿っていくのではなく、二次元の座標を辿っていく。重みが変わらない最短経路は幅優先。こちらのプログラムを参照URL
- セルが訪問済み <-> dist[y][x] == 1
- セルが発見済み・訪問予定 -> queue.push(make_pair(next_y, next_x))
- セルが未発見 <-> dist[y][x] == 0
30 JOI 2011 予選 5 - チーズ

幅優先探索の処理を繰り返す。処理を切り出してループしただけ。(スタートとゴールの設定・最短距離の保存する配列の定義・キューの定義・幅優先探索)の 4 つの処理を繰り返す。コードが汚い...
31 JOI 2012 予選 5 - イルミネーション

難しい。もう一回やる
32 AOJ 1166 - 迷図と命ず

問題文（入力）がよくわからない！実装も重い！とりあえず先に進む。
33 AtCoder Beginner Contest 088 D - Grid Repainting

ゴールまでの最短ステップをまず求める。~~そこから最短経路を逆に求める。field のうち、最短経路のセルを別の文字に置き換える。~~ -> 最短ステップ数が分かれば、(field の'.'の数 - 最短ステップ数 -1)が答えになる。

3-1. 動的計画法：ナップザック DP

参考サイト: https://qiita.com/drken/items/a5e6fe22863b7992efdb

参考サイト: https://qiita.com/drken/items/dc53c683d6de8aeacf5a

3-2. 動的計画法：区間 DP

46 ALDS_10_B - 連鎖行列積

時間切れ、一旦先に進む。添字の意味がややこしい。参考サイト: こちら
47 JOI 2015 本選 2 - ケーキの切り分け 2
48 AOJ 1611 ダルマ落とし

3-3. 動的計画法：bit DP

49 DPL_2_A - 巡回セールスマン問題
50 Square869120Contest #1 G - Revenge of Traveling Salesman Problem
51 JOI 2014 予選 4 - 部活のスケジュール表
52 JOI 2017 予選 4 - ぬいぐるみの整理

3-4. 動的計画法：その他

53 DPL_1_D - 最長増加部分列
54 AtCoder Beginner Contest 006 D - トランプ挿入ソート
55 AtCoder Beginner Contest 134 E - Sequence Decomposing

4-1. 最短経路問題：ダイクストラ法

56 GRL_1_A - 単一始点最短経路
57 JOI 2008 予選 6 - 船旅
58 JOI 2016 予選 5 - ゾンビ島
59 JOI 2014 予選 5 - タクシー

4-2. 最短経路問題：ワーシャルフロイド法

5-1. 最小全域木問題

6-1. 高速な素数判定法

6-2. 高速なべき乗計算

6-3. 逆元を使う問題

6-4. 累積和

6-5. Union-Find

6-6. その他のテクニック

6-7. 実装問題

6-8. 数学的な問題

調べたこと

ios::sync_with_stdio(false);
cin.tie(0);

書かない -> cin を実行した時点で buffering されていた cout が出力(flush)される

書く -> cin を実行しても flush されない

コード例

int main(void)
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

    int n;
    for(int rep = 0; rep < 3; ++rep) {
        std::cout << "Input number: ";
        std::cin >> n;
        std::cout << n << " is given." << std::endl;
    }

    return 0;

}

実行例

100
Input number: 100 is given.
200
Input number: 200 is given.
300
Input number: 300 is given.

────────────────────────────────────────

__builtin_popcount

1 が何本立っているかを返す

__builtin_popcount(7) -> 3
__builtin_popcount(8) -> 1

masafumin1515 / 100_problem Goto Github PK

100_problem's Introduction

目次