# 鉄則本輪読会第二回目

### 探索
数学の問題と競技プログラミングの問題の大きく違う点としてあげられるのは**探索**という概念。初心者の人はまずは、**全部のパターンを探索すれば答えが出る**という視点を持って問題を解くことに慣れれば、ABCのA,Bは解けるようになるはず。

全探索は、文字通り、「全てのあり得る通り数を探索する」ということ。

そのあと、**計算量**という概念にも気をつかわなくてはいけなくなる。計算量については鉄則の説明がわかりやすいと思います。同じ例で軽く説明。

$1+2+3+\cdots+n$
を計算するときにどう計算するか？

1. $(\cdots (((1+2)+3)+4)\cdots)+n)$
2. $\frac{1}{2}\cdot n(n+1)$

* 一個目の方法
(n-1)回計算しなければいけない
* 二個目の方法
せいぜい三回とか

**明らかに効率が違う**

計算手順のことを**アルゴリズム**といい、より効率のいいアルゴリズムの方がうれしい。問題の制約によって、効率の悪いアルゴリズムでは制限時間内に終わらなかったりするようにできていて、よりよりアルゴリズムを考えなければ解けない。

* 覚えておくこと
軽く見積もって計算量が$10^7$くらいだったら間に合うことが多い。

> たまにそれ以上でも間に合うけどその判断は難しいです。。だれか便利な基準あったら教えてほしい。（足し算だけとか、そういうときは間に合うイメージ）
>

#### 1.2線形探索
リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する
$O(n)$

$n = 10^6$とかのときにあやしい

#### 1.3ペアを見ていく
二つ配列があって、要素のペアを全探索することはよくある。
$O(n^2)$

for(int i=0; i <100; i++){
    for(int j=0; j<100 ; j++){
    \\処理
    }
}

一番外側のforについて、一回分で、中身のforが１００回回るので、
計算量：$10^2 \cdot 10^2 = (10^2)^2$

#### 1.4二進数
二進数は競プロでよく使うので、思い出しておく。

#### 1.5工夫した全探索

大事。この辺から計算量が気になってくる。
愚直
３重forループ
$3000^3 = 3^3\cdot 10^9$
実行制限時間内に終わらない。

**工夫します。**
一枚目には$(x\leq3000)$
二枚目には$(y\leq3000)$
三枚目には$(z\leq3000)$

が書かれているとします。
このとき、$x+y+z=Kであるなら、z = K-x-y$
x,yが確定すれば

count = 0
for x in range(n):
    for y in range(n):
        for z in range(n):
             if x+y+z == k:
                 count += 1

count = 0
for x in range(n):
    for y in range(n):
         if 1<=k-x-y<=n:
             count += 1

$O(N^2)$
に落とせる

x+y+z =　const
z = const-x-y

#### bit全探索

ビット
0,1

ビット演算

めっちゃいい資料
https://qiita.com/e869120/items/25cb52ba47be0fd418d6#2-%E3%81%99%E3%81%B9%E3%81%A6%E3%81%AE%E5%9F%BA%E6%9C%AC%E5%85%A8%E6%8E%A2%E7%B4%A2