# アルゴリズム基礎講習会 全探索
:::info
この記事は 東京工業大学デジタル創作同好会traP が2023年に開催したアルゴリズム基礎講習会で使用された資料を一部改変したものです。
:::
[toc]
## 0. 講師紹介
- noya2 (22B)
- 情報理工学院 数理・計算科学系
- 競技プログラミングをしています
- AtCoder 初参加は 2020/02/22
## 1. 全探索とは
### 今回扱う全探索
全探索とは... 厳密な定義はわからないです。
- そもそも世の中の多くのアルゴリズムが全探索？
- めちゃくちゃ賢い全探索から、あまり賢くない全探索まで、いろいろある。
- 問題特有の考察を除けば、要求される「全探索のアルゴリズム」の種類はそんなに多くない？
今回は、「力任せ探索」とか呼ばれる探索手法、考察対象の状態を全て**列挙**することに焦点を当てます。 :muscle: :muscle: :muscle: :punch: :punch: :punch:
### 全探索のモチベーション
数学の試験で次のような問題が出たとしましょう。
> $100$ 以下の正整数であって $2$ で割り切れずに $3$ で割り切れるものはいくつあるでしょうか。
:sunglasses: 賢いおともだちの例
> $(3$ で割り切れるものの個数 $) - (6$ で割り切れるものの個数 $)$ が答え！
> $\left\lfloor\dfrac{100}{3}\right\rfloor - \left\lfloor\dfrac{100}{6}\right\rfloor =33 - 16 = 17$ 個あるよ！
:face_with_raised_eyebrow: 地道なおともだちの例
> $n=1,2,\dots ,100$ の順に $n$ が条件に合うかを調べて数え上げるよ！
> $1\not\equiv 0\pmod 2, 1\not\equiv 0\pmod 3$ だから $1$ は条件に合わない。 $2$ は...
> 数え終わったよ！ $17$ 個あったよ！
:triumph: ずるいおともだちの例
> ｶﾀｶﾀｶﾀｶﾀ
> ```cpp
> #include<bits/stdc++.h>
> using namespace std;
> int main(){
> int ans = 0;
> for (int n = 1; n <= 100; n++){
> if (n % 2 != 0 && n % 3 == 0){
> ans++;
> }
> }
> cout << ans << endl;
> }
> ```
> :computer: < $17$
> なんか $17$ 個らしいよ！
今回目指すのは :triumph: になることです。
コンピュータの力を借りれば、**何も考えずに** 言われた条件をそのままコードに書き写すだけで答えが出てきますね。
- $n=1,2,\dots ,100$ を全て調べる
- $n$ が条件 $(n\not\equiv 0\pmod 2 \land n\equiv 0\pmod 3)$ を満たしていたら答えが $1$ 増える
:face_with_raised_eyebrow: のように膨大な時間を費やせば人力でできるような計算を、**コンピュータの力を借りて爆速で実行してもらおう** :triumph: というのがモチベーションです。
競技プログラミングの難しい問題では
- そもそも :triumph: な方法ではコンピュータでも時間がかかりすぎる
- :sunglasses: な方法で問題を簡単にする
- :face_with_raised_eyebrow: な方法で愚直に調べる方法を思いつく
- :triumph: な方法でｶﾀｶﾀして答えを得る
という流れを踏むことが多いです。
少なくとも競技プログラミングをする上では、ｶﾀｶﾀしないことには始まりませんから、まずは :triumph: になることを目指しましょう！
### 全探索がしたくなるお話 0
> 太古の昔に登録したSNSにふと気になってログインしようとしたあなたは、**3桁**のパスワードを要求されました。もちろんあなたはそのパスワードを覚えていません。しかし、そのパスワードは**0~9の数字のみ**で構成されているようです。どうしたものでしょうか。
:sunglasses: 困ったなぁ
:face_with_raised_eyebrow: $1000$ 通りしかないし、全部調べちゃおうよ！
:triumph: 任せろ！ｶﾀｶﾀｶﾀｶﾀ
何をしたら”全探索した”ことになるでしょうか。
> パスワードの候補を全て出力したらいいよ。
らしいです。今回はそれでいきましょう。おそらく、
```cpp
bool f(string s){
bool is_correct;
// 謎の処理
// 多分正しいパスワード t があって if (s == t) とかやってる
return is_correct;
}
```
みたいな判定関数があって、`f(s) == true` になったら :ok: ということでしょう。全部試すのでどれかで必ず `true` になるはずです。
実装方法を $2$ 通り紹介しましょう。
- $n=0,1,\dots ,999$ まで試す。$n$ の十進表記に先頭に0をつけて3桁にする。
```cpp
for (int n = 0; n <= 999; n++){
printf("%03d\n",n);
}
```
- $10^0,10^1,10^2$ の位それぞれについて $0,1,\dots 9$ の組み合わせを全て試す。
```cpp
for (int i0 = 0; i0 <= 9; i0++){
for (int i1 = 0; i1 <= 9; i1++){
for (int i2 = 0; i2 <= 9; i2++){
cout << i2 << i1 << i0 << endl;
}
}
}
```
前者は出力方法が :sunglasses: ですね。`printf` のフォーマット指定は便利です。しかし、それを知らなくても、後者のように `for` を $3$ 回ネストすれば :ok: です。
:::info
やったことまとめ
- あり得るものを全部調べたい
- あり得るものを全列挙
- （条件がある場合は）条件に合うかどうかひとつずつ調べる
- `for` 文はよく使うよ
:::
### 全探索がしたくなるお話 1(いろいろな for 文)
ここからは競技プログラミングっぽい問題設定にしていきます。
- 問題文が現実的ではないことが多い :sweat_smile:
- 数式がたくさん出てくることがある :exploding_head:
- ~~なんでそんなことがしたいのか分からないことが多い~~ :scream:
> 正整数 $N$ が与えられます。$3$ つの整数組 $(a_1,a_2,a_3)$ であって、
> $$0\le a_1\le a_2\le a_3\le N$$
> を満たすものを全て出力してください。順番はなんでもよいです。
> - $1\le N\le 100$
> #### 入力形式
> > $N$
>
> #### 入力例
>
> ```
> 2
> ```
>
> #### 出力例
>
> ```
> 0 0 0
> 0 0 1
> 0 0 2
> 0 1 1
> 0 1 2
> 0 2 2
> 1 1 1
> 1 1 2
> 1 2 2
> 2 2 2
> ```
:triumph: $N\le 100$ :eyes: 全探索できそう！
:innocent: 今回は全部調べざるを得ないんだけどね
- $N$ が高々 $100$ なので、列挙する組の個数はそれほど多くはなさそう？
- :thinking_face: どのくらいあるでしょうか？
- 手動でもギリギリやる気が起きなくもない。
- けどやりたくはない
:::spoiler これを解くC++のコード
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
for (int A1 = 0; A1 <= N; A1++){
for (int A2 = A1; A2 <= N; A2++){
for (int A3 = A2; A3 <= N; A3++){
cout << A1 << " " << A2 << " " << A3 << endl;
}
}
}
}
```
:::
### 全探索がしたくなるお話 2(再帰 for 文)
> 正整数 $N$ と $N$ 個の正整数 $A_1,A_2,\dots ,A_N$ が与えられます。
> 非負整数の $N$ 個組 $(a_1,a_2,\dots ,a_N)$ であって、
>
> $$0\le a_i\lt A_i\ (i = 1,2,\dots N)$$
>
> を満たすものを全て出力してください。順番はなんでもよいです。
>
> - $1\le N\le 10$
> - $1\le A_i\ (i=1,2,\dots ,N)$
> - $\displaystyle\prod_{i=1}^{N}A_i \le 10^5$
> #### 入力形式
> > $N$
> > $A_1$ $A_2$ $\dots$ $A_N$
>
> #### 入力例
>
> ```
> 2
> 2 3
> ```
>
> #### 出力例
>
> ```
> 0 0
> 0 1
> 0 2
> 1 0
> 1 1
> 1 2
> ```
- さっきと違うのは、組の大きさも与えられる点
- `for` 文の $N$ 重にする必要がある...?
:::spoiler これを解くC++のコード
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) cin >> A[i];
vector<int> a(N);
auto dfs = [&](auto dfs, int i) -> void {
if (i == N){
for (int j = 0; j < N; j++){
cout << a[j];
if (j == N-1) cout << endl;
else cout << " ";
}
return ;
}
for (int ai = 0; ai < A[i]; ai++){
a[i] = ai;
dfs(dfs,i+1);
}
};
dfs(dfs,0);
}
```
:::
### 全探索がしたくなるお話 3(bit 全探索)
> 正整数 $N,K$ と $N$ 個の正整数 $A_1,A_2,\dots ,A_N$ が与えられます。
> $A_1,A_2,\dots ,A_N$ のうちからいくつか選んで総和を $K$ にすることができるか判定してください。
>
> - $1\le N\le 20$
> - $1\le K\le 10^5$
> - $0\le A_i\le 10^5\ (i=1,2,\dots ,N)$
> #### 入力形式
> > $N$ $K$
> > $A_1$ $A_2$ $\dots$ $A_N$
>
> #### 入力例
>
> ```
> 3 5
> 1 3 4
> ```
>
> #### 出力例
>
> ```
> Yes
> ```
:triumph: $N\le 20$ :eyes: 全探索できそう！
- $N$ が高々 $20$ なので、選ぶ方法はそれほど多くはなさそう？
- :thinking_face: どのくらいあるでしょうか？
- 手動でやるのはかなり無理。
- 選び方が与えられれば、総和が $K$ かを確かめるのは簡単！
:::spoiler これを解くC++のコード
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, k; cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
bool ans = false;
for (int s = 0; s < 1<<n; s++){
int sum = 0;
for (int i = 0; i < n; i++){
if (s >> i & 1) sum += a[i];
}
if (sum == k) ans = true;
}
cout << (ans ? "Yes" : "No") << endl;
}
:::
### 全探索がしたくなるお話 4(順列全探索)
> 長さ $N$ の整数列 $A=(A_1,A_2,\dots ,A_N)$ が与えられます。$A$ の要素を自由に並べ替えて得られる任意の数列 $B$ に対する $\displaystyle\sum_{k=1}^{N} kB_k$ の最大値を求めてください。
>
> - $1\le N\le 9$
> - $-10^5\le A_i\le 10^5$
>
> #### 入力形式
> > $N$
> > $A_1$ $A_2$ $\dots$ $A_N$
>
> #### 入力例
>
> ```
> 5
> 0 4 2 1 5
> ```
>
> #### 出力例
>
> ```
> 49
> ```
- ~~並べ替え不等式 :sunglasses: とか言ってるそこのあなた！しーっ！~~
- $N$ が高々 $9$ なので、$A$ の順列を全て試しても良さそう？
- 手動でやるのはかなり無理2。
- 順列が与えられたときに $\sum$ を計算するのは簡単！
:::spoiler これを解くC++のコード
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n;
vector<int> a(n), p(n);
for (int i = 0; i < n; i++){
cin >> a[i];
p[i] = i+1;
}
int ans = -1'000'000'000;
do {
int sum = 0;
for (int i = 0; i < n; i++) sum += p[i] * a[i];
ans = max(ans,sum);
}while(next_permutation(p.begin(),p.end()));
cout << ans << endl;
}
```
:::
## 2. 手動全探索
アルゴリズムをコードに起こすには、そのアルゴリズムを実際に手で実行して見せることができることが望ましいです。先述した彼 :face_with_raised_eyebrow: のように、具体的にどんな計算をしてどんな場合わけをして...ということを分かっていないと、それをコードに起こすのは難しいですよね。まずは手を動かしてやってみましょうか。
### 問 1 (いろいろな for 文)
> 正整数 $N$ が与えられます。$3$ つの整数組 $(a_1,a_2,a_3)$ であって、
> $$0\le a_1\le a_2\le a_3\le N$$
> を満たすものを全て出力してください。順番はなんでもよいです。
#### まずは $N=1$ でやってみましょうか。
```
0 1 1
0 0 1
0 0 0
1 1 1
0 0 1
```
- どうやって重複なく列挙するか
- `0 0 1` が被ってますよ :thinking_face:
#### つぎは $N=2$ でやってみましょうか。
```
0 0 0
0 0 1
0 0 2
0 1 1
0 1 2
1 1 1
1 1 2
1 2 2
2 2 2
```
- どうやって不足なく列挙するか
- `0 2 2` が足りませんよ :thinking_face:
#### つぎは $N=5$ でやってみましょうか。
```
0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 1 1
0 1 2
0 1 3
0 1 4
0 2 2
0 2 3
0 2 4
0 3 3
0 3 4
0 4 4
1 1 1
1 1 2
1 1 3
1 1 4
1 2 2
1 2 3
1 2 4
1 3 3
1 3 4
1 4 4
2 2 2
2 2 3
2 2 4
2 3 3
2 3 4
2 4 4
3 3 3
3 3 4
3 4 4
4 4 4
```
- 列挙する個数が多すぎませんか
- 最大で $176851$ 個らしいです :thinking_face:
:::info
- 過不足なく列挙するアルゴリズムが欲しい
- うまく列挙するには対象に**順番**をつけたい
- なるべく簡潔なアルゴリズムが欲しい
- **単純なルールの組み合わせ**でアルゴリズムを表現したい
:::
### 問 2 (再帰 for 文)
> 正整数 $N$ と $N$ 個の正整数 $A_1,A_2,\dots ,A_N$ が与えられます。
> 非負整数の $N$ 個組 $(a_1,a_2,\dots ,a_N)$ であって、
>
> $$0\le a_i\lt A_i\ (i = 1,2,\dots N)$$
>
> を満たすものを全て出力してください。順番はなんでもよいです。
問 1 と同じようにすればできそうですよね。頭の中で処理すればいいことは何も変わっていなさそうに見えます。しかし、思い浮かべたアルゴリズムを**単純なルール**に分解しようとすると、問 1 にはなかった難しさが見えてくるかもしれません。:eyes:
:::info
> for 文を $N$ 回ネストするコードを書いてください。
は難しいです。その代わり、これならどうでしょうか。
> for 文を $N$ 回ネストするコードを出力するようなコードを書いてください。
:::
### 問 3 (bit 全探索)
> 正整数 $N,K$ と $N$ 個の正整数 $A_1,A_2,\dots ,A_N$ が与えられます。
> $A_1,A_2,\dots ,A_N$ のうちからいくつか選んで総和を $K$ にすることができるか判定してください。
手でできそうな例が与えられたら、ついつい眼力で :face_with_raised_eyebrow: 「 $K$ が作れないかな〜 」とか考えたくなりますよね。
- 答えが `Yes` であることが分かっている
- 合計が $K$ になるような選び方をひとつ見つけてね
という設定なら、十分な時間をかければ眼力でもいつか見つかるかもしれません。しかし、雑な探索をしていては答えが `No` になることの証明をすることは難しいです。
最も単純に答えが `No` であることを言いたい場合は、全ての場合を調べたけど総和が $K$ にならなかった、ということを言えばよさそうですね。そのためには文字通り全ての場合を調べる必要があります。つまり、与えられた多重集合 $\lbrace A_1,A_2,\dots ,A_N\rbrace$ の全ての部分集合を調べなければなりません！
#### $N=4$ でやってみましょうか。
$\lbrace 0,1,2,3\rbrace$ の全ての部分集合を列挙してみましょう。
過不足なく列挙するにはどうすればいいでしょうか。
:white_check_mark: 部分集合の大きさで場合わけ
```
size = 0 : {}
size = 1 : {0},{1},{2},{3}
size = 2 : {0,1},{0,2},{0,3},{1,2},{1,3},{2,3}
size = 3 : {0,1,2},{0,1,3},{0,2,3},{1,2,3}
size = 4 : {0,1,2,3}
```
全部で $16$ 個、過不足なし :thumbsup:
:white_check_mark: 特定の要素を含むかどうかで場合わけ
場合わけが3個以上ネストされると :exploding_head: $\rightarrow$ $0,1$ をそれぞれ含むかどうかで場合わけ
```
0 in S :
1 in S :
{0,1},{0,1,2},{0,1,3},{0,1,2,3}
not :
{0},{0,2},{0,3},{0,2,3}
not :
1 in S :
{1},{1,2},{1,3},{1,2,3}
not :
{},{2},{3},{2,3}
```
全部で $16$ 個、過不足なし :thumbsup:
- いずれにしても $N$ が大きくなると難しそう
- 場合わけの種類が多すぎる :thinking_face:
- 場合わけの深さが深すぎる :thinking_face:
- $N=20$ のときの部分集合の個数は $1048576$ 個
- 多すぎ :exploding_head:
:::info
- 小さい場合なら”なんかうまくできる”では、アルゴリズムにならない
- どんなケースにでも適応できる普遍的なルールが必要
:::
### 問 4 (順列全探索)
> 長さ $N$ の正整数列 $A=(A_1,A_2,\dots ,A_N)$ が与えられます。$A$ の要素を自由に並べ替えて得られる任意の数列 $B$ に対する $\displaystyle\sum_{k=1}^{N} kB_k$ の最大値を求めてください。
順列を列挙することができたら、$\sum$ を計算するのは簡単ですよね。ここでは順列をどうやって全て列挙するかに注目していきましょう。
#### $N=4$ でやってみましょうか。
```
4
1 2 3 4
```
$A=(1,2,3,4)$ の並べ替えを列挙してみよう。
過不足なく列挙するにはどうすればいいでしょうか。
- 数列の「辞書順」に
$24$ 通りあるはずですね。
**樹形図** でも書いてみましょうか。
```
1 - 2 - 3 - 4
4 - 3
3 - 2 - 4
4 - 2
4 - 2 - 3
3 - 2
2 - 1 - 3 - 4
4 - 3
3 - 1 - 4
4 - 1
4 - 1 - 3
3 - 1
3 - 1 - 2 - 4
4 - 2
2 - 1 - 4
4 - 1
4 - 1 - 2
2 - 1
4 - 1 - 2 - 3
3 - 2
2 - 1 - 3
3 - 1
3 - 1 - 2
2 - 1
```
- $N$ が大きくなっても原理的には全てを列挙できる
- 樹の深いところへは**今まで登場していない数**を**小さい順に**並べる
- 深さが $N$ になったらそれ以上は深くしない
- $N=9$ のときの順列の個数は $362880$ 個
- 手でやるにはやはり多すぎ :exploding_head:
- ここまで言語化すればあとは :computer: に任せれば一瞬で終わる
:::info
- 何をすればいいかを細かく**言語化**
- 入力サイズが大きくなっても適応できる
:::
## 3. 計算量
どんなアルゴリズムを実行するにしろ、それがいつかは終了することを望みたいですし、できるなら速く終了することが望ましい気がします。競技プログラミングをするなら、実行時間制限が設定されていることも多いですから、それに間に合うようなアルゴリズムを設計したいところです。手で実行するにしても速いに越したことはなさそうですよね。
では、アルゴリズムの実行時間を見積もるにはどうすればいいでしょうか。まずは誰がそれを実行するかは重要そうですよね。:computer: にやらせるのか彼 :face_with_raised_eyebrow: がやるのかでは、実行時間に大きな違いがありそうです。他には、基本的な計算が何回行われるか、覚えておく変数が何個あるか、など、アルゴリズムの実行に要求されるさまざまな要素がどのくらい必要かを知る必要がありそうです。
### 計算回数を見積もろう
#### さっきまでやったこと
- あり得る「状態」を全て列挙しよう
- 「なにかの順番で」「場合わけして」「樹形図を描いて」列挙できそう？
- 列挙しないといけない個数が何個あるか
- あれ、もしかして途方もなく多いですか？
入力の大きさを表すパラメータを用いて、どのくらいの「状態」があり得るのか、表してみましょうか。
#### 問 1
列挙する組は $\dfrac{(N+3)(N+2)(N+1)}{6}$ 個あります。
#### 問 2
列挙する組は $\displaystyle\prod_{i=1}^{N}A_i$ 個あります。
#### 問 3
列挙する部分集合は $2^N$ 個あります。
#### 問 4
列挙する順列は $N!$ 個あります。
### 計算の詳細な内容
列挙してください、と言ったら列挙してくれるわけではないので、もっと具体的に計算内容や手順を :computer: や :face_with_raised_eyebrow: に教えないといけません。とりあえずは :computer: にやらせることを前提にしましょう。競技プログラミングをしたいですからね。
#### そもそも、どんな計算をして状態を列挙するんですか？
問1の例でやっていることを「アルゴリズム」的にもう少し詳細に説明してみましょう。
- 変数の設定
- 変数の変更（加減剰余、代入）
- 条件分岐
- etc...
> 1. `a1 = 0` とする。
> 2. `a1 = N+1` のとき 11 に進む。
> 3. `a2 = a1` とする。
> 4. `a2 = N+1` のとき 10 に進む。
> 5. `a3 = a2` とする。
> 6. `a3 = N+1` のとき 9 に進む。
> 7. `a1 a2 a3` を出力する。
> 8. `a3 += 1` として 6 に進む。
> 9. `a2 += 1` として 4 に進む。
> 10. `a1 += 1` として 2 に進む。
> 11. アルゴリズムを終了する。
アルゴリズムはどのように動作するでしょうか。
$N=1$ のとき、操作列を求めてみましょう。
`1 2 3 4 5 6 7 8 6 7 8 6 9 4 5 6 7 8 6 9 4 10 2 3 4 5 6 7 8 6 9 4 10 2 11`
操作回数は
`1 x1, 2 x3, 3 x2, 4 x5, 5 x3, 6 x7, 7 x4, 8 x4, 9 x3, 10 x2, 11 x1`
`Total x35`
一般の $N$ だと操作回数の合計はどうなるでしょう？ :thinking_face:
> 7. が行われる回数は $(N+3)(N+2)(N+1)/6$ 回でしたね
実は、操作回数の合計は $N^3/2+5N^2+31N/2+14$ と計算できます。
ここで疑問に思ったことはないでしょうか。
- アルゴリズムの各操作の「コスト」は同じとみなして良いのか？
- 操作1と操作2で1回行うコスト（時間・メモリ）は同じなのか
- プログラムが動作する過程はそれだけではないですよね？
- `int main()` とか書くんだから `main` を呼ぶ操作があるはず
- 入力を受け取る操作があるはず
- etc...
回数だけを考慮していては実行時間を見積もるのは難しいかもしれません。そこで、計算量という概念を紹介しましょう！
### 計算量の概念
計算量ってなんだろな :thinking_face:
#### ざっくり説明
- アルゴリズムの性能評価の基準として「計算量」という量が定められる
- どんな「計算」を基本単位として、それぞれどんな「コスト」で達成できるか
計算量 : **アルゴリズムを計算の基本単位の組み合わせに分解したときのコストの総和**
#### 計算の基本単位と達成コスト
- 世の中にはさまざまな計算モデルが存在する
- wordRAM などの有名なやつ
- 機械で計算することを想定しなくてもOK
アルゴリズムを実行する環境を想定して、何を計算の基本単位としたら良いか、それらがどんなコストで達成できるかをあらかじめ決めておきます。
- 整数や実数の情報をどうやって保持する？
- 紙に書く (紙の大きさは？足りなくなったら？)
- ビット列でメモリ上に管理（メモリって何？無限長は扱えない？）
- 整数同士の足し算はどう扱う？
- 筆算する
- 簡単そうだし、ノーコストで正確に計算できるものとする
- 条件分岐はどう行う？
- フローチャートを書いて眼力でなんとかする
- （以前扱ったように）アルゴリズムに番号をつけて、各番号へはノーコストで移動できるものとする
- 変数へのアクセスや関数呼び出しはどう行う？
- 情報を保持する領域を全て調べて、同じ名前を持つものを見つける
- どの変数や関数へもノーコストでアクセス可能とする
いろいろな計算モデルが考えられそうですね :eyes: :eyes:
さて、今知りたいのは :computer: にアルゴリズムを実行させたときの実行時間ですから、それに比例しそうな計算量が導かれるような計算モデルを考えたいところです。一般的な競技プログラミングで用いられる :computer: の性能や扱われる問題の規模の大きさや性質から、次のようなモデルが妥当そうです（筆者の体感）。
#### 競技プログラミングの文脈で一般に仮定される計算のコスト
> （競技プログラミングの文脈での実行環境では、）
> コンピュータは $1$ 秒間に $10^8\sim 10^9$ 回の計算ができます。
:thinking_face: どんな計算を $1$ 回と数えているのか？
- `int` 型どうしの四則演算・大小比較は $1$ 回 **くらい**
- 長さ $N$ の文字列の代入は $N$ 回 **くらい**
- `for (int i = 0; i < n; i++)` は $n$ 回 **くらい**
- `vector<int>` への `push_back()` は $1$ 回 **くらい**
- 変数へのアクセスは $1$ 回**くらい**
ソースコード全体でどのような計算が何回起こるかを調べてその総和を取ったとすると、それを $1$ 秒当たり $10^8$ 回くらいの速さで処理しますよ〜、ということ。
(膨大な例外を含むため、実質嘘ですが、体感はこのくらい、ということです。)
:::info
この $10^8\sim 10^9$ 回という数字の規模感は覚えておいた方が良いです。こんな計算量で実行時間制限に間に合うんだろうか、と考えるときの指標になります。
:::
### アルゴリズムの計算量
> このアルゴリズムの計算量は $f(N)$ である。
とか言うことがあります。
問1の例だと
- 入力全体は $\mathbb{Z}_{\ge 1}$
- 制約は $1\le N\le 10$ だが、アルゴリズムは $1\le N$ で動作する
- 操作7以外はコスト1、それ以外はコスト0で行えるとする
- 入力 $1$ に対する計算量は $4$
- 入力 $2$ に対する計算量は $10$
一般の入力 $N$ に対する計算量は $(N+3)(N+2)(N+1)/6$ ですね。
> 問 1 のアルゴリズムの計算量は $f(N)=(N+3)(N+2)(N+1)/6$ である。
計算量を**入力を表す変数を使って表示**している。:eyes: :eyes:
問1の例で、別の解法を提案してくれたおともだちの例（計算モデルは同じ）
> $g(N)=(N+3)(N+2)(N+1)N/24$ になったよ！
:thinking_face: どちらのアルゴリズムの方が「良い」でしょうか？
### アルゴリズムの「良さ」について
- 競技プログラミングの文脈では **実行時間** が速い方が良い（ことが多い）
- 実行時間制限: 2sec とか書いてある
- 計算のコストを計算にかかる時間に比例する量にすると適切な評価に
- 実行時に使う **メモリ** の大きさが小さい方が重要なこともある
- メモリ制限:1024MB とか書いてある
これらの評価を区別するために、「**時間計算量**」や「**空間計算量**」などと呼ぶことがある。単に「計算量」とだけ言った場合には実行時間に関する計算量を指していることが多い。
今回は「時間計算量」に注目していく。
#### どちらの方が良い計算量でしょうか？
- $f(N)=(N+3)(N+2)(N+1)/6$
- $g(N)=(N+3)(N+2)(N+1)N/24$
> $N=100$ を代入すれば $f(100)<g(100)$ だし $f$ の方が良い？
> $N=1$ なら $f(1)>g(1)$ だから $g$ の方がいいこともあるよ？
> $N\ge 5$ なら $f(N)\lt g(N)$ だよ。$f$ の方がいいに決まってるよ！
#### 関数のオーダー
$f(N),g(N)$ の「大小」を比較したい
- 極端な違いがないなら、どちらも同じ、と言ってしまっても問題ないことが多い
- 入力サイズの大きさに対する「大雑把な」値の大きさが知りたいことが多い
そんなあなたに :white_check_mark: 関数の**オーダー**に関する記法を導入！
### 計算量のオーダーの概念
一変数関数のオーダーについて紹介しましょう。ここでは計算量のオーダーについて注目していますが、関数のオーダーは計算量とは独立した概念です。
#### 関数のオーダー記法いろいろ
- $\Theta$ 記法（シータ・Theta）
- ちょうどこのくらい :eyes: :eyes:
- $O$ 記法（ビッグオー・big-O）
- 高々このくらい :eyes: :eyes:
- $\Omega$ 記法（ビッグオメガ・big-Omega）
- 少なくともこのくらい
- $o$ 記法（リトルオー・little-o）
- これより真に小さい
- $\omega$ 記法（リトルオメガ・little-omega）
- これより真に大きい
#### $\Theta$ 記法
$f(n)$ のオーダーが $g(n)$ であるとは :
$$
\exists n_0, c_L>0, c_U>0\ \mathrm{s.t.}\
\forall n\ge n_0, 0\le c_L\cdot g(n) \le f(n) \le c_U\cdot g(n)
$$
- 十分大きな $n$ に対して $f(n)$ は常に $g(n)$ の同じ定数倍で挟める
- $n_0,c_L,c_R$ はどれだけ大きくてもOK
- $f(n)$ のオーダーが $g(n)$ であることを指して $f(n)\in \Theta(g(n))$ と書くことも
- $\Theta(g(n))$ はオーダーが $g(n)$ であるような関数の集合を表す
#### $\Theta$ 記法の例
> $n^3/6\in\Theta(n^3)$ である。$n^3/6$ のオーダーは $n^3$ である。
そうですね。
> $10^{100}n^2\in\Theta(n^2)$ である。
そうです。$\Theta(n^2)$ が $n^2$ の小さな定数倍くらい、ということでは必ずしもないですね。
> $n\log_2 n\not\in\Theta(n^2)$ である。
そうですね。定義に登場した $c_L$ が存在しません。
:::info
- $\Theta$ 記法は関数を定数倍でサンドイッチするときに使える
:::
#### $O$ 記法
$\Theta$ 記法のほぼコピペです。:white_check_mark: 下から抑える必要がない :eyes:
$f(n)$ のオーダーが高々 $g(n)$ であるとは :
$$
\exists n_0, c_U>0\ \mathrm{s.t.}\
\forall n\ge n_0, 0\le f(n) \le c_U\cdot g(n)
$$
- 十分大きな $n$ に対して $f(n)$ は常に $g(n)$ の同じ定数倍で上から抑えられる
- $n_0,c_R$ はどれだけ大きくてもOK
- $f(n)$ のオーダーが高々 $g(n)$ であることを指して $f(n)\in O(g(n))$ と書くことも
- $O(g(n))$ はオーダーが $g(n)$ であるような関数の集合を表す
#### $O$ 記法の例
> $n^3/6\in O(n^3)$ である。$n^3/6$ のオーダーは高々 $n^3$ である。
そうですね。上からも下からも抑えられるので、当然、上から抑えられます。
> $3n^2+4n+5\in O(3n^2+4n+5)$ である。
そうです。$O$ の中身は複雑でもOK。もちろん $\in O(n^2)$ で良いわけですが。
> $n\log_2 n\in O(n^2)$ である。
そうですね。もちろん、$n(\log_2 n)^{100}\in O(n^2)$ です。
:::info
- $O$ 記法は関数を定数倍で上から抑えるときに使える
:::
:::warning
オーダー記法の注意点
> $f(n)\in\Theta(n^2)$ なので $n=100$ のとき $f(n)$ は $10000$ くらいですよね〜
- $f(n)=10^{100}n^2+(\log n)^{100}+2^{2^{100}}$ かもしれません。具体的な数値の大きさを保証するものではありません。
> $\Theta(\log _2 n)=\Theta(\log_e n)$ だから、当然 $\Theta(2^n)=\Theta(e^n)$ ですよね〜
- 前者は正しいですが、後者は正しくないですね。対数の底はオーダーに影響を与えないがちですが、指数の底は影響を与えがちです。
> $n\le 10^3$ の制約で $O(n^2)$ の計算量で解けたので、2sec に間に合いますね〜
- 当然、実行時間を上から抑えるためのものではないです。
:::
:::warning
記法に関してです。$\Theta$ のことを指して $O$ と書いてある文章が競技プログラミングの解説記事などにもあります。注意してください。
また、上から抑えるぶんにはどちらでも伝わりますが、これらを区別する文脈では正しい書き分けが必要です。例えば
> 少なくとも $O(n)$ なので...
など、下から抑えるのには $O$ 記法は不適切です。（上の文章は明らかに不自然です。「早くとも 1 時までに着く」と同じ違和感があります。）
> $\Omega (n)$ なので...
と言いたげに見えます。
:::
#### オーダー記法と計算量の評価
$2$ つの同じ問題を解くアルゴリズム $F,G$ が入力 $n$ に対してそれぞれ $f(n),g(n)$ の時間計算量で解くとします。どちらの方が効率の良いアルゴリズムと言えるでしょうか。
:thinking_face: $f(n)\in \Theta(g(n))$ なら同じと言えそう?
:thinking_face: $f(n)\in O(g(n))$ なら $F$ は $G$ より悪くはないと言えそう?
:thinking_face: $g(n)\in O(f(n))$ なら $G$ は $F$ より悪くはないと言えそう?
:upside_down_face: 見方によってはそう（それは、そう）
計算量のオーダーが良い方が効率的です、という文脈なら、それはそう。
- $f(N)=(N+3)(N+2)(N+1)/6$
- $g(N)=(N+3)(N+2)(N+1)N/24$
なら、$f$ の方が $g$ より良さそうですよね。$f(n)\in o(g(n))$ とか書けます。
### 計算量のオーダーと実行時間は関係ないよ
計算量の定数倍や主要でない（ $n^2$ に対する $n$ や $2^n$ に対する $n^{100}$ など）項を気にせずに評価できるのが嬉しい。
- 入力を受け取るために $n$ の計算量が必要だが、他に $n^2$ 回のループが回る。だから、計算量は大体 $n^2$ に比例しそうだし、実際に計算量は $\Theta(n^2)$ と評価できる。
しかし、それによって計算量の正確な情報を大きく捨てていることも多い。
- 本当はループが回るたびに $100$ 回くらい四則演算をするけど、ループは $n$ 回しか回らなくて計算量は $100n$ くらいだから、$\Theta(n)$ だと評価できる。
- 場合わけをして、一方は $\Theta(n)$ の計算量が必要だと分かった。他方は $\Theta(1)$ で計算できる。場合わけは $n$ 回起こるから $O(n^2)$ と評価したが、実際は前者の場合は $1$ 回までしか起こらないので $\Theta(n)$ と評価できた。
- 計算量が $\Theta(n)$ と評価できたとしても、実際は $10^{100}n$ の計算量が必要なら、実行時間制限に全く間に合わないということもあり得る。
- 計算量が $O(n^2)$ と評価できて、入力サイズの制約から実行時間制限に間に合わないかもしれないと思ったとしても、実際には爆速で動くこともあり得る。
:point_right: 実行制限時間を見積もるために必要なのは計算量のオーダーではなくて、計算量 :eyes:</span>
### (競プロの文脈では)やっぱり関係があるよ
- $\Theta(n^2)$ の計算量と評価してあるものの計算量は文字通り $n^2$ かもしれない。（体感、$1$ 桁倍くらいで評価できていることが多い）
- 主要項ではないために捨ててある部分は実際本当に主要でないことが多い。（ $O(n)$ と評価してあるものの計算量は $n+3$ であるなど）
雑な計算量見積もりをして計算量の主要項以外を捨て定数倍も捨てたとしても、まあそこそこ実行時間をよく表していることが多い :eyes: :eyes:
そもそも AC が正義なので、計算量とかオーダーとか、どうでもいい（過激）という説もあります。
### 実行時間の見積もりは知識と経験でなんとかなる!
- 主要項の定数倍はちゃんと見る
- 一番処理の重たそうな部分が実行される回数に注目する
- このアルゴリズムの定数倍は重い・軽いなどの経験を積む
TLE (実行時間制限超過)したら、アルゴリズムの計算量について考えてみましょうね。
> よくある流れ :
> TLE -> :thinking_face: -> 計算量解析 -> 原因特定 -> 改善 -> AC :raised_hands:
はじめのうちは計算量を意識するのはとても難しいです。TLE も経験のうちです！
:::info
- アルゴリズムの計算量について意識しておくと、実行時間の見積もりにつながる
- 正確に見積もることは困難でも、オーダーを意識しておくと :thumbsup:
:::
計算量のはなしはここで終わりです。お疲れ様でした。:tada: :tada: :tada: :tada: :tada: :tada:
もっと計算量について知りたい場合は、[えびちゃんさんの記事](https://rsk0315.hatenablog.com/entry/2021/10/13/235627)がとても参考になります。
次は全探索のさまざまな手法を紹介します。 :raised_hands: :raised_hands: :raised_hands: :raised_hands: :raised_hands: :raised_hands: :raised_hands: :raised_hands: :raised_hands: :raised_hands:
## 4. 全探索の手法
問題文が次のようなかたちをしているとします。
> - oo を全て調べよ
> - oo であって xx なものを全て調べよ
> - oo であって xx なもの全てに対する hoge(max/sum/...) を求めよ
今回扱うもの：
- oo を全て列挙し、それぞれ xx を満たすかどうか調べるなどする
扱わないもの：
- oo かつ xx なものを列挙する
- hoge を求めるのに必要な部分だけ列挙
:sunglasses: な方法は考えないことにして、初手から :triumph: 全開で行きます。
### いろいろなfor文
for 文は探索の基礎です。これひとつでかなり多くのことができます。いろいろな for 文の書き方を見ていきましょう。
#### いつもの
```cpp
for (int i = 0; i < n; i++) { ... }
```
#### ネストできるよ
```cpp
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
...
}
}
```
#### <= もできるよ
```cpp
for (int i = 0; i <= n; i++) { ... }
```
#### 初期値はなんでもいいよ
```cpp
for (int i = m; i <= n; i++) { ... }
```
#### 逆順もできるよ
```cpp
for (int i = n-1; i >= 0; i--) { ... }
```
#### 2つ飛ばしもできるよ
```cpp
for (int i = 0; i < n; i += 2) { ... }
```
#### 条件式は複雑でもいいよ
```cpp
for (int i = 0; i < n && i*i <= m; i++) { ... }
```
### for 文の動き方
```cpp
for (<init> ; <cond> ; <loop> ) { <state> }
```
1. `<init>` を実行
2. `<cond>` が `true` なら 3. に、 `false` なら 5. に進む
3. `<state>` を実行
4. `<loop>` を実行して 2. に進む
5. `for` 文の実行を終了
:white_check_mark: もっと詳しく挙動や構文の内容を知りたい人は自分で調べてみよう！
ちょっと見た目が奇抜なやつもあります。
#### 複数の変数を初期化できるよ
```cpp
for (int w = 1; w <= n; w++){
for (int l = 0, r = w; r <= n; l++, r++){
// 区間 DP で dp[l,r) を処理
}
}
```
#### いろいろ省略できるよ
```cpp
for (int s = 1; s < (1 << n); s++){
for (int t = s; --t &= s; ){
// bitDP で s の 空でない真部分集合 t を全列挙
}
}
```
#### つぎの for 文はどのように動くかな。想像してみよう。
```cpp
int n = 5;
for ( ; n > 0; ){
cout << n << endl;
n -= 2;
}
```
```cpp
int n = 6;
for (int d = 1; d * d <= n; d++){
if (n % d == 0){
cout << d << endl;
if (d * d != n){
cout << n/d << endl;
}
}
}
```
#### こたえ
```cpp
int n = 5;
for ( ; n > 0; ){ // n > 0 なら実行
cout << n << endl;
n -= 2; // n を 2 減らす
}
```
出力結果
```
5
3
1
```
for 文の省略を派手に使っていますが、みなさんはもう読むことができるはずです。
#### こたえ
```cpp
int n = 6;
for (int d = 1; d * d <= n; d++){
if (n % d == 0){ // n が d で割り切れるなら...
cout << d << endl; // d は n の約数なので出力
if (d * d != n){
cout << n/d << endl; // n/d も n の約数
}
}
}
```
出力結果
```
1
6
2
3
```
`d * d <= n` の間、つまり $s = \lfloor\sqrt n\rfloor$ として `d <= s` の間 for 文が回ります。
:::info
- for 文の書き方はいろいろある
:::
### 再帰for文
愚直に for 文を書こうとするとネストする回数が入力によって変わるような問題も考えることができます。そのような問題の例を見てみましょう。
> 正整数 $n$ に対して $n$ 以下の正整数からなる $n$ 個組を全て出力してください。
> $n=1$ のとき
> ```
> 1
> ```
> $n=2$ のとき
> ```
> 1 1
> 1 2
> 2 1
> 2 2
> ```
> $n=3$ のとき
> ```
> 1 1 1
> 1 1 2
> 1 1 3
> 1 2 1
> 1 2 2
> 1 2 3
> 1 3 1
> 1 3 2
> 1 3 3
> 2 1 1
> 2 1 2
> 2 1 3
> 2 2 1
> 2 2 2
> 2 2 3
> 2 3 1
> 2 3 2
> 2 3 3
> 3 1 1
> 3 1 2
> 3 1 3
> 3 2 1
> 3 2 2
> 3 2 3
> 3 3 1
> 3 3 2
> 3 3 3
> ```
#### for 文のネスト回数が入力に依存するので困った :thinking_face:
```cpp
for (int a1 = 1; a1 <= n; a1++){
for (int a2 = 1; a2 <= n; a2++){
...
for (int an = 1; an <= n; an++){
cout << ...
}
}
}
```
そんなときは... :white_check_mark: 再帰を使って for 文を書こう
```cpp
int main(){
int n; cin >> n;
vector<int> ans(n);
// for 文の i 回目のネスト(i は 0_indexed)
auto dfs = [&](auto dfs, int i) -> void {
if (i == n){ // 答えを出力して再帰を終了
for (int j = 0; j < n; j++){
cout << ans[j];
if (j == n-1) cout << endl;
else cout << " ";
}
}
else {
for (int a = 1; a <= n; a++){
ans[i] = a;
dfs(dfs,i+1); // for 文をもう一段階深く潜る
}
}
};
dfs(dfs,0); // 0 回目の for 文に潜る
}
```
C++のラムダ再帰の書き方はこれに限りませんが、詳細が気になる方は調べてね。
まずはこういう書き方ができることを知ろう！
```cpp
auto dfs = [&](auto dfs, ...) -> void {
dfs(dfs, ...); // 再帰呼び出し
};
dfs(dfs, ...); // 再帰を開始
```
- `void` の部分は `int` `string` `vector<int>` などでも良い
- `[&]` はその時点で見ることができる変数を参照する書き方
- `...` の部分は `型名` `変数名` を `,` 区切りで並べるいつもの書き方
:white_check_mark: 再帰が終了する条件をちゃんと書く
:white_check_mark: 再帰が終了するように次の再帰に潜る
```cpp
if (i == n){
// 出力
}
else {
// なんやかんやした後で...
dfs(dfs,i+1); // i が 1 ずつ増えていき, いずれは終了条件 i == n に辿り着く
}
```
普通の再帰と同じように書いても良い(`ans` をグローバル変数に置くか引数を増やすか、みたいな煩わしさがあるが...)です。見てみましょう。
#### `ans` を参照渡しで再帰関数の引数に投げる方法
```cpp
void saiki(int n, vector<int> &ans){
if (ans.size() == n){
// ans を出力
return ;
}
for (int a = 1; a <= n; a++){
ans.push_back(a);
saiki(n,ans);
ans.pop_back();
}
}
int main(){
int n; cin >> n;
vector<int> ans;
saiki(n,ans);
}
```
#### `ans` をグローバル変数に置く方法
```cpp
int n;
vector<int> ans;
void saiki(int i){
if (i == n){
// ans を出力
return ;
}
for (int a = 1; a <= n; a++){
ans[i] = a;
saiki(i+1);
}
}
int main(){
cin >> n;
ans.resize(n);
saiki(0);
}
```
#### つぎの再帰 for 文はどのように動くかな。想像してみよう。
```cpp
int n = 3;
int ans = 0;
auto inc = [&](auto inc, int i, int pre) -> void {
if (i == n){
ans++;
return ;
}
for (int a = pre; a <= n; a++){
inc(inc,i+1,a);
}
};
inc(inc,0,1);
cout << ans << endl;
```
#### こたえ
```
10
```
- `ans : 全ての要素が n 以下の正整数である長さ n の広義単調増加列の個数`
- 再帰では `i : 今何番目の要素を決めているか` `pre : 直前の要素は何か` を持っている
- 終了条件は全ての要素を作り終わったことを表す `i == n`
- 終了したとき、条件を満たす数列を見つけたことを `ans++` として報告
:::info
- ラムダ再帰を用いて for 文を $N$ 重にネストすることができる
- 今どの深さの for 文を回しているかを引数に持って再帰に潜ると :thumbsup:
:::
### bit 全探索
集合の部分集合をビット列とみなすことで、再帰 for 文よりも簡潔に部分集合を列挙する方法を紹介します。次のような問題にこの方法は有効です。
> 正整数 $n$ が与えられるので、集合 $S = \lbrace 0,1,\dots ,n-1\rbrace$ の部分集合を全て列挙してください。
> $n=1$ のとき
> ```
>
> 0
> ```
> $n=2$ のとき
> ```
>
> 0
> 1
> 0 1
> ```
さっきの再帰 for 文のように $2$ 択の for 文を $n$ 回ネストすればいい？
:white_check_mark: 2択がたくさんあるときは bit 全探索！
```cpp
for (int s = 0; s < (1<<n); s++){
vector<int> ans;
for (int i = 0; i < n; i++){
if (s >> i & 1){
ans.push_back(i);
}
}
// ans を出力(略)
}
```
#### ビット ってなんのこと？
`5` の二進表記 `101` 、`8` の二進表記 `1000` のように（非負）整数を二進表記で考えてみる。
- `5` の $2^0$ の位はいくらでしょう？ ... `1`
- `5` の $2^1$ の位はいくらでしょう？ ... `0`
- `5` の $2^2$ の位はいくらでしょう？ ... `1`
- `5` の $2^3$ の位はいくらでしょう？ ... `0`
- ... `000...`
:white_check_mark: 非負整数の $2^d(d\ge 0)$ の位を考える！
#### $2^n$ 未満の非負整数と $\lbrace 0,1,\dots ,n-1\rbrace$ の部分集合を一対一対応させる
$n=3$ の例
```
2^n 未満の非負整数 | 長さ n のビット列 | 対応する部分集合
0 | 000 | {}
1 | 001 | {0}
2 | 010 | {1}
3 | 011 | {0, 1}
4 | 100 | {2}
5 | 101 | {0, 2}
6 | 110 | {1, 2}
7 | 111 | {0, 1, 2}
```
（左から） $i$ 番目のビットが `1` であることと $i$ が含まれることが対応している。:eyes: :eyes: :eyes:
:::info
- $2^n$ 未満の非負整数で部分集合を列挙
- ビットが `1` であることと要素が部分集合に含まれていることが対応する
:::
#### 非負整数で表された集合が特定の要素を含むか判定してみよう
こんどは $n=4$ でやってみましょう。$\lbrace 0,1,2,3\rbrace$ の部分集合を考えます。
1. $15$ が表す部分集合に $0$ は含まれるかな？
2. $13$ が表す部分集合に $1$ は含まれるかな？
3. $\ 9$ が表す部分集合に $2$ は含まれるかな？
4. $\ 0$ が表す部分集合に $3$ は含まれるかな？
#### 困ったときは ... :thinking_face:
:white_check_mark: 与えられた非負整数を長さ $4$ のビット列（二進表記）で表してみよう
:white_check_mark: ビット列が表す部分集合は何でしょうか
:white_check_mark: `1` になっているビットの番号は部分集合に含まれているはず
#### こたえ
1. $15$ が表す部分集合に $0$ は含まれるかな？ `Yes`
`15 | 1111 | {0,1,2,3}`
2. $13$ が表す部分集合に $1$ は含まれるかな？ `No`
`13 | 1101 | {0,2,3}`
3. $\ 9$ が表す部分集合に $2$ は含まれるかな？ `No`
` 9 | 1001 | {0,3}`
4. $\ 0$ が表す部分集合に $3$ は含まれるかな？ `No`
` 0 | 0000 | {}`
#### ビットごとの論理積を使って $d$ ビット目が立っているかどうかを調べる
ある非負整数 $N$ の $2^d$ の位が $1$ であることを「 $N$ の $d$ ビット目が立っている」と言うことがあります。
部分集合がある要素を含むことと非負整数のあるビットが `1` であることが対応しているのでした。そこで次のような問題を考えたくなります。
> 非負整数 $n(0\le n\lt 2^3), d(0\le d\lt 3)$ が与えられます。 $n$ の $2^d$ の位を求めてください。
```cpp
int main(){
int n, d; cin >> n >> d;
cout << (n >> d & 1) << endl;
}
```
見慣れない記法が多数登場していますね！
- `>>` はビット列として見たときの右シフト
- `5` の `0` 回右シフト `5 >> 0` は `5` (`101 -> 101`)
- `5` の `1` 回右シフト `5 >> 1` は `2` (`101 -> 010`)
- `5` の `2` 回右シフト `5 >> 2` は `1` (`101 -> 001`)
- `5` の `3` 回右シフト `5 >> 3` は `0` (`101 -> 000`)
- `&` は ビットごとの論理積をとる演算子
#### ビットごとの論理積とは？
- $1$ ビットどうしの積をそのまま並べたもの
- `0 & 0 := 0` `0 & 1 := 0` `1 & 0 := 0` `1 & 1 := 1` （掛け算みたい :eyes: ）
- `0 : false, 1 : true, & : and` と読み替えると直感的
#### 例
- `5 & 3` を考える
- 長さ $3$ のビット列として見ると `(101) & (011)`
- $1$ ビットずつ積を計算して並べると `(101) & (011) := (001)`
:white_check_mark: ビットごとの論理積 `&`
#### $1$ とビットごとの論理積をとるとどうなるでしょう？
> $1$ はビット列で `...0001` なので、$2^0$ の位だけが残るよ
```
01101 00110 00011 00001 00000
& 00001 & 00001 & 00001 & 00001 & 00001
------- ------- ------- ------- -------
00001 00000 00001 00001 00000
= = = = =
13 & 1 6 & 1 3 & 1 1 & 1 0 & 1
```
> $0$ ビット目が `1` なら `1` に、`0` なら `0` になるね
:white_check_mark: $1$ とのビットごとの論理積 `& 1` の結果
#### $d$ ビットだけ右シフトしたらどうなるでしょう？
> $d$ ビット目が $0$ ビット目に来るよ
```
13 : 01101
13 >> 0 : 01101
13 >> 1 : 00110
13 >> 2 : 00011
13 >> 3 : 00001
13 >> 4 : 00000
13 >> 5 : 00000
: :
```
:white_check_mark: 右ビットシフト
> さっきの $0$ ビット目が $1$ かどうかを判定する方法と組み合わせたらどうなるかな
#### $N$ を $d$ ビットだけ右シフトして $1$ とのビットごとの論理積をとると...
> $N$ の $2^d$ の位が計算できる！ :tada: :tada: :tada:
#### $N$ の $d$ ビット目が立っているなら... を if 文で表現したい
```cpp
if (N >> d & 1){
// N の d ビット目が立っているなら...
}
```
> `if` の中に整数が入っているよ！ `true` なの？ `false` なの？
> `N >> d & 1` は `1` か `0` のどちらかだけど...
:::warning
実は、一般に整数の場合、 `0` は `false` に、それ以外は `true` として解釈されます。
:::
#### もう一度コードを眺めてみよう
```cpp
for (int s = 0; s < 1<<n; s++){ // 1<<n は 2^n のこと。<< は左シフト
vector<int> ans; // s の要素を入れる配列
for (int i = 0; i < n; i++){ // 0,1,...,n-1 が s に含まれているかな？
if (s >> i & 1){ // s の i ビット目が 1 だったら...
ans.push_back(i); // ans に i を追加
}
}
// ans を出力(略)
}
```
:face_with_monocle: 今まで登場してきた書き方を復習しましょう。
:hushed: 外側の for 文は $2^n$ 回、内側は $n$ 回まわる。`ans` を宣言したり `push_back` したりしている部分は $O(1)$ の時間計算量、つまりで定数時間で動くから、合計の時間計算量は $O(n2^n)$ と見積もれるね。
:::warning
**ビットまわりの実装で注意したいこと**
- $2^n-1$ のことを `1<<n-1` と書くと壊れる
- $2^{n-1}$ と解釈される
- `(1<<n)-1` だとOK
- `cout << n & 1 << endl;` は壊れる
- `<<` の方が優先順位が高いので、`(cout << n) & (1 << endl);` になってしまう
- `1 << endl` ってなんですか？
- `cout << (n & 1) << endl;` だとOK
- 「 `s` に `i` が含まれていない」を `if (s >> i & 1 == 0)` と書くと壊れる
- `>>` とか `&` とか `==` とかの評価順は直感に反することも割とある
- `if ((s >> i & 1) == 0)` だとOK
- `(int型) >> (32以上の整数)` は壊れる
- `int` 型が表す範囲は $-2^{31}$ 以上 $2^{31}$ 未満
- $2^d$ の位なんだから $d\ge 32$ のときは $0$ を返してほしい？ダメ〜
- `(int型) >> (負の整数)` も壊れる
- `a >> (-2)` は `a << 2` のことですよね！？ダメ〜
- `(int型) << (32以上の整数)` は壊れる
- $32 \le d < 63$ に対して $2^d$ が欲しいとき、`1 << d` と書くと `1` は int型なので壊れる
- `1` を long long 型にして `1LL << d` と書くと OK
:::
#### つぎのbit 全探索を行うコードはどのように動くかな。想像してみよう。
```cpp
int n = 4;
vector<int> ans(n+1,0);
for (int s = 0; s < (1<<n); s++){
int cnt = 0;
for (int i = 0; i < n; i++){
if (s >> i & 1) cnt++;
}
ans[cnt]++;
}
for (int i = 0; i <= n; i++){
cout << ans[i] << endl;
}
```
#### こたえ
```
1
4
6
4
1
```
- `ans[i] : {0,1,2,3} のすべての部分集合のうち、大きさが i であるものの個数`
- `cnt` は `s` の大きさを数えている
- `if (s >> i & 1) cnt++;` は「 `s` に `i` が含まれていれば大きさを $1$ 増やす 」
- 二項係数が並んでいる :eyes:
:::info
- $\lbrace 0,1,\dots ,n-1\rbrace$ の部分集合は $0,1,\dots ,2^n-1$ に対応する
- `s` が表す部分集合に `i` が含まれるかどうか判定するには `if (s >> i & 1)`
:::
### 順列全探索
列の要素の並べ替えを全て列挙する方法を紹介します。やはりこれも再帰 for 文と同じ方法で列挙することができますが、`next_permutation` という関数を使って簡潔に実装することができます。
> 正整数 $n$ が与えられるので、列 $A = (0,1,\dots ,n-1)$ の並べ替えとしてあり得るものを全て列挙してください。
> $n=2$ のとき
> ```
> 0 1
> 1 0
> ```
> $n=3$ のとき
> ```
> 0 1 2
> 0 2 1
> 1 0 2
> 1 2 0
> 2 0 1
> 2 1 0
> ```
:white_check_mark: 順列を全て調べるには `next_permutation`
```cpp
int main(){
int n; cin >> n;
vector<int> ans(n);
for (int i = 0; i < n; i++) ans[i] = i;
do {
// ans を出力(略)
}while(nextpermutation(ans.begin(),ans.end()));
}
```
:::spoiler （ちなみに）再帰 for 文と同じように書くと...
```cpp
int main(){
int n; cin >> n;
vector<bool> done(n,false);
vector<int> ans(n);
auto dfs = [&](auto dfs, int i) -> void {
if (i == n){
// ans を出力
return ;
}
for (int j = 0; j < n; j++){
if (done[j]) continue;
ans[i] = j;
done[j] = true;
dfs(dfs,i+1);
done[j] = false;
}
};
dfs(dfs,0);
}
```
:::
#### `next_permutation` ってなに
[std::next_permutationの日本語リファレンス](https://cpprefjp.github.io/reference/algorithm/next_permutation.html)
- 列の要素の大小関係によって、ふたつの列の**辞書式順序**が定められる。
- 与えた範囲(`[first,last)`)が成す列の並べ替えのうち、辞書式順序で**次に大きい**ものに `[first,last)` が書き換えられる
- 次に大きいものが存在した場合は `true` が、そうでない場合は `false` が返される。
- 範囲の長さを $n$ とすると $O(n)$ の時間計算量で行う。
:::warning
ちょっと難しい話：**イテレータ**
`next_permutation` は $2$ つのイテレータ `first,last` を引数に取りイテレータ範囲 `[first,last)` に対して操作を行います。イテレータは値の”場所”のように捉えることができます。例えば `[ans.begin(),ans.end())` というのは、 `ans` の最初から最後まで、と捉えることができます。
:::
#### 辞書式順序とは
長さの等しい $2$ つの異なる列 $A=(A_1,A_2,\dots ,A_n), B=(B_1,B_2,\dots ,B_n)$ の辞書式順序による大小関係は次のように定められます。
- $A_i\neq B_i$ となる最小の $i$ を $k$ とする
- $A_k$ と $B_k$ の大小関係が $A$ と $B$ の大小関係と一致するように定める
先頭から要素が同じかどうかを調べ、初めて異なった要素の大小を列の大小とする、ということですね。
#### 辞書式順序の練習
1. $A=(1,2,3,4),B=(1,2,4,4)$ のうち辞書式順序で小さい方はどちらでしょうか？
2. $C=(3,2,1),D=(1,1,1)$ のうち辞書式順序で小さい方はどちらでしょうか？
3. $S=$ `abxd` $,T=$ `abxc` のうち辞書式順序で小さい方はどちらでしょうか？（文字列は文字の列と捉える・文字の大小は通常の辞書順）
#### こたえ
1. $A_3,B_3$ を比較して、$A$ の方が小さい
2. $C_1,D_1$ を比較して、$D$ の方が小さい
3. $S_4,\ T_4$ を比較して、$T$ の方が小さい
#### do-while 文ってなに
```cpp
do {
<state>
}while(<cond>);
```
do-while 文は次のように動きます。
1. `<state>` を実行
2. `<cond>` が `true` なら 1. に、`false` なら 3. に進む
3. do-while 文を終了
名前が似ている while 文を思い出してください。
```cpp
while (<cond>){
<state>
}
```
while 文では `<cond>` がはじめから `false` だった場合は `<state>` は一度も実行されないのでした。これと比較して、do-while 文は中身（`<state>`）が一度以上実行されるのが特徴です。この特徴が
- `next_permutation` は次の順列が存在するとき `true` を、そうでないとき `false` を返す
という仕様と相性が良いため、`next_permutation` と do-while 文はしばしば一緒に使われます。（ ~~どちらか一方だけが使われている例を見たことは、いまだかつてありません :cry:~~ ）
そういえば、ちょうど昨日(2023/05/28)の [ARC(AtCoder Regular Contest)161 E - Not Dyed by Majority (Cubic Graph) ](https://atcoder.jp/contests/arc161/tasks/arc161_e) で使いました [(提出結果)](https://atcoder.jp/contests/arc161/submissions/41817141)。
#### 辞書式順序に従って順列を生成する
実は、辞書式順序によって順列を小さい方から大きい方へ一列に並べることができます。（難しい話：辞書式順序は全順序なので）
これによって、ある順列の次に来る順列を一意に決めることができます。与えられた順列をその次の順列に書き換えてくれるのが `next_permutation` というわけです。
さて、辞書式順序で最も大きい順列には次にくる順列が存在しません。このとき `next_permutation` は `false` を返します。（存在したときは `true` を返します。）そうなれば `while` 文の継続条件が `false` になるため、`do while` のループから抜けることになります。これでめでたしめでたし、というわけです。
:::warning
**順列全探索の際に気をつけたいこと**
全ての順列を列挙したい場合は、**辞書式順序で最小のものからスタート**しなければなりません。並べ替えのうち辞書式順序で最小のものを得るには `sort` を用いると良いです。与えられた長さ $n$ の整数列 $a$ の並べ替えを全て列挙するには、次のように書くと良いです。
```cpp
int main(){
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
sort(a.begin(),a.end());
do {
// a を出力
}while(next_permutation(a.begin(),a.end()));
}
```
このアルゴリズムは $O(n\cdot n!)$ の時間計算量で動作します。
:::
#### つぎの順列全探索を行うコードはどのように動くかな。想像してみよう。
```cpp
vector<int> a = {1,3,4,7};
do {
if (a[0] < a[1] && a[1] > a[2] && a[2] < a[3]){
cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << endl;
}
}while(next_permutation(a.begin(),a.end()));
```
#### こたえ
```
1 4 3 7
1 7 3 4
3 4 1 7
3 7 1 4
4 7 1 3
```
- `a` の全ての並べ替えを辞書式順序の小さい順に試している。
- $a_0\lt a_1 \gt a_2\lt a_3$ を満たしていたら出力している。
:::info
- 順列全探索は `do while` と `next_permutation` で簡潔に書ける
:::
## 5.練習問題
再帰 for 文は難しいので、練習問題としては扱いません :cry: 。
今後の講習会でDFS（深さ優先探索）を学ぶと、理解が深まるはずです。
### いろいろな for 文の練習問題
[ABC293 A - Swap Odd and Even](https://atcoder.jp/contests/abc293/tasks/abc293_a)
### bit 全探索の練習問題
[ABC289 C - Coverage](https://atcoder.jp/contests/abc289/tasks/abc289_c)
### 順列全探索の練習問題
[ABC302 C - Almost Equal](https://atcoder.jp/contests/abc302/tasks/abc302_c)
Sign in with Wallet
Connect another wallet