AtCoder アルゴリズムと数学演習問題集「アルゴリズムのための数学の基本知識」「基本的なアルゴリズム」全問題 Python解答例

[Supership](https://supership.jp/)の名畑です。公開されたてほやほやの「[TVアニメ『ヒプノシスマイク-Division Rap Battle-』Rhyme Anima ＋ OPテーマ「RISE FROM DEAD」 MV](https://www.youtube.com/watch?v=k6VU82c9edo)」大好きです。

:::note info
こちらは[競プロ Advent Calendar 2023](https://adventar.org/calendars/8745)の3日目の記事となります。
Twitterでのハッシュタグは[#競プロAdC](https://twitter.com/search?q=%23%E7%AB%B6%E3%83%97%E3%83%ADAdC&src=typed_query)です。
:::

## はじめに

前も触れましたが、[AtCoder](https://atcoder.jp/)では、競技プログラミングの世界で有名な[E869120](https://twitter.com/e869120)さん執筆の書籍「[問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本](https://gihyo.jp/book/2022/978-4-297-12521-9)」の[演習問題集](https://atcoder.jp/contests/math-and-algorithm)が公開されています。

今回の記事ではこのうちの**2章**「**アルゴリズムのための数学の基本知識**」と**3章**「**基本的なアルゴリズム**」の全問題をPythonで解いてみたので、そのコードを残します。数学の復習に良さそうです。一部の問題はプログラミング初心者にも良さそうです。

学習目的のコンテンツのため、基本的にモジュールの**import**は抜きで書きます。1問だけ使っていますが、それも使わない場合の方法を後述します。

## 2章「アルゴリズムのための数学の基本知識」

## 変数と定数の加算

- 問題：[001 - Print 5+N](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_a)

**N**に**5**を足して出力します。

```Python
N = int(input())
print(5 + N)
```

## 3個の変数の加算

- 問題：[002 - Sum of 3 Integers](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_b)

**A1**、**A2**、**A3**の和を出力します。

```Python
A1, A2, A3 = map(int, input().split())
print(A1 + A2 + A3)
```

## N個の変数の加算

- 問題：[003 - Sum of N Integers](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_c)

配列の合計値を出力します。

```Python
N = int(input())
A = list(map(int, input().split()))
print(sum(A))
```

## 3個の変数の乗算

- 問題：[004 - Product of 3 Integers](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_d)

**A1**、**A2**、**A3**の積を出力します。

```Python
A1, A2, A3 = map(int, input().split())
print(A1 * A2 * A3)
```

## 剰余

- 問題：[005 - Modulo 100](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_e)

配列の合計値を**100**で割った余りを出力します。

```Python
N = int(input())
a = list(map(int, input().split()))
print(sum(a) % 100)
```

## 1次式

- 問題：[006 - Print 2N+3](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_f)

**N**を**2**倍して**3**を足した結果を出力します。

```Python
N = int(input())
print(2 * N + 3)
```

## 倍数と最小公倍数

- 問題：[007 - Number of Multiples 1](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_g)

**N**以下の整数の中で**X**あるいは**Y**の倍数がいくつあるかを出力します。

**X**の倍数の個数と**Y**の倍数の個数を足し、そこから**X**と**Y**の公倍数の個数を引きます。

**lcm**は最小公倍数を求める関数です。**lcm**を用いずに最小公倍数を求める方法は後述の「[N個の整数での最小公倍数](#n個の整数での最小公倍数)」で取り上げます。

```Python
import math
N, X, Y = map(int, input().split())
print(N // X + N // Y - N // math.lcm(X, Y))
```

## 全探索

- 問題：[008 - Brute Force 1 ](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_h)

**2枚**のカードにそれぞれ**1以上N以下**の整数を書き、その合計が**S以下**になる組み合わせの数を求めます。

総当たりです。

```Python
N, S = map(int, input().split())
answer = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i + j <= S:
            answer += 1
print(answer)
```

## bit全探索と動的計画法

- 問題：[009 - Brute Force 2](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_i)

**1≦N≦20**について解けると部分点として**500点**となり、**N≦60**までを解けると**1000点**となります。下記は**500点**となるコードと**1000点**となるコードの両方を記載します。[過去記事](https://qiita.com/nabata/items/122d7b2aa78391a8cae6)で解説した内容と同様です。

動的計画法については後述の問題でもいくつも出てきますが、詳しくは過去記事「[動的計画法の基本を理解するためのAtCoder問題5選とPython解答例](https://qiita.com/nabata/items/cfd5495b2ef68711297c)」をご覧いただけますと幸いです。

### bit全探索による500点のコード

たとえば**N**が**3**で、各カードを**A0**、**A1**、**A2**とします。

このときとりうるカードの組み合わせは

- A0
- A1
- A1 + A0
- A2
- A2 + A0
- A2 + A1
- A2 + A1 + A0

の7パターンです。(問題文において**S**は**1以上**のため、カードを選ばないことはない）

2進数で記すなら

- 001
- 010
- 011
- 100
- 101
- 110
- 111

と書けます。左から順にそれぞれの桁が**A2**、**A1**、**A0**の有無を示しているとします。

コードにすると下記です。2進数各桁の取得は右シフトしつつ**1**との論理積をとっています。**1**との論理積をとれば**下1桁**の値になります。

```Python
N, S = map(int, input().split())
A = list(map(int, input().split()))
for i in range(1, 2 ** N):
    total = 0
    for j in range(N):
        total += A[j] * ((i >> j) & 1)  # 2進数にした各桁が1のときだけAを足す
    if total == S:
        print('Yes')
        exit()
print('No')
```

計算量が**Nの2乗**に比例するため、**N**が大きくなると**1000msec**を超えて**TLE**(Time Limit Exceeded)です。

### 動的計画法(DP)による1000点のコード

たとえば**N**が**2**で、各カードを**A0**、**A1**とします。
そして**A0**が**2**、**A1**が**3**だとします。

1枚目のカードとして**A0**を選んだとき、その時点での合計値は**2**です。選ばなければ**0**です。
つまり、**A0**だけしかカードがなかった場合、**0**と**2**がとりうる数です。

さらに、**A1**を選ぶか選ばないかまで考えると

- 0 + 0 = 0
- 0 + 3 = 3
- 2 + 0 = 2
- 2 + 3 = 5

この4パターンです。つまり、**A0**と**A1**の2枚のカードしかなかった場合、**0**、**2**、**3**、**5**の4つがとりうる値となります。
**S**がこの中にあれば**Yes**、なければ**No**という考え方です。

```Python
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [False] * (S + 1)  # 0〜Sまでの値をとりうるかを格納する配列
dp[0] = True  # 0のみTrueにしておく
for i in range(N):  # 0枚目から順番にカードを見ていく
    for j in reversed(range(0, S)):  # dpの値が途中で変わらないようにreversedしている
        if dp[j] and j + A[i] <= S:
            dp[j + A[i]] = True
if dp[S]:  # Sをとりうるか判定する
    print('Yes')
else:
    print('No')
```

## 階乗

- 問題：[010 - Factorial](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_j)

**N**の階乗を求めます。

```Python
N = int(input())
ans = 1
for i in range(1, N + 1):
    ans *= i
print(ans)
```

## 素数の列挙

- 問題：[011 - Print Prime Numbers](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_k)

**N以下**の素数を出力します。
総当たりをしています。

```Python
N = int(input())
answer = []
for i in range(2, N + 1):
    for j in range(2, i):
        if i % j == 0:
            break
    else:
        answer.append(i)
answer.sort()
[print(i, end=' ') for i in answer]
```

## 3章「基本的なアルゴリズム」

ここから3章です。

## 素数判定

- 問題：[012 - Primality Test](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_l)

**N**が素数かの判定を行います。
無駄は多いですが、総当たりでも間に合います。
**2以外**の偶数を省く等をした方がより効率的です。

繰り返しは**√N**まで(**1/2乗**)としています。
**√N**までで割り切れなければ、それより大きい**N以外**の数で割り切れることはないため。

```Python
N = int(input())
if N == 1:
    print('No')
    exit()
for i in range(2, int(N ** 0.5) + 1):
    if N % i == 0:
        print('No')
        exit()
print('Yes')
```

## 約数の列挙

- 問題：[013 - Divisor Enumeration](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_m)

**N**の約数を列挙します。
これもほぼ総当たりですが繰り返しは**√N**までとしています。

たとえば**N**が**6**であれば、約数は**1**、**2**、**3**、**6**です。**√6**は**2.449...**ですので**3以降**が含まれませんが、その代わりに

- 1で割り切れる時は6 / 1の答えである6も約数に加える
- 2で割り切れる時は6 / 2の答えである3も約数に加える

ということをしています。**i**で割り切れるならば、**N**を**i**で割った数も約数となるからです。

```Python
N = int(input())
ans = []
for i in range(1, int(N ** 0.5) + 1):
    if N % i == 0:
        ans.append(i)
        if i != N // i:
            ans.append(N // i)
[print(i) for i in ans]
```

## 素因数分解

- 問題：[014 - Factorization](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_n)

**n**を素因数分解します。
**2**から順番に割っていくだけです。

計算量を減らすため、ループを回す条件を **div <= int(n \*\* 0.5)** として、残った**n**を**answer**に追加します。

これも偶数は**2以外**を見る必要はないですが、時間的には下記のような総当たりでも充分に間に合います。

```Python
n = int(input())
answer = []
div = 2
while div <= int(n ** 0.5):
    if n % div == 0:
        answer.append(div)
        n //= div # 小数にならないように切り捨て
    else:
        div += 1
if n > 1:
    answer.append(n)
[print(i, end=' ') for i in answer]
```

## 2個の整数での最大公約数

- 問題：[015 - Calculate GCD](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_o)

**A**と**B**の最大公約数を求めます。

[ユークリッドの互除法](https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95)を使います。

```Python
A, B = map(int, input().split())
a, b = max([A, B]), min([A, B])
while b > 0:
    a, b = b, a % b
print(a)
```

## N個の整数での最大公約数

- 問題：[016 - Greatest Common Divisor of N Integers](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_p)

**N個**になってもやることは1つ前の問題と同じです。順番に最大公約数を求めていきます。

```Python
N = int(input())
A = list(map(int, input().split()))
a = A[0]
for i in range(1, N):
    a, b = max([a, A[i]]), min([a, A[i]])
    while b > 0:
        a, b = b, a % b
print(a)

```

## N個の整数での最小公倍数

- 問題：[017 - Least Common Multiple of N Integers](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_q)

最小公倍数は**a * b / 最大公約数**で求められます。

```Python
N = int(input())
A = list(map(int, input().split()))
a = A[0]
for i in range(1, N):
    a_temp = a
    a, b = max([a, A[i]]), min([a, A[i]])
    while b > 0:
        a, b = b, a % b
    a = a_temp * A[i] // a
print(a)
```

## 組み合わせ 1

- 問題：[018 - Convenience Store 1](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_r)

**100円**、**200円**、**300円**、**400円**の4種類の商品が合計で**N個**あり、その中から合計で**500円**になる組み合わせの数を求めるというものです。

**100円**と**400円**あるいは**200円**と**300円**の組み合わせのみが**500円**となります。

```Python
N = int(input())
A = list(map(int, input().split()))
print(A.count(100) * A.count(400) + A.count(200) * A.count(300))
```

## 組み合わせ 2

- 問題：[019 - Choose Cards 1](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_s)

**A**という配列に**1**、**2**、**3**のいずれかの値が格納され、同じ数のペアがどれだけ作れるかという問題です。

```Python
N = int(input())
A = list(map(int, input().split()))
red = A.count(1)
yellow = A.count(2)
blue = A.count(3)
answer = 0
if red > 0:
    answer += red * (red - 1) // 2
if yellow > 0:
    answer += yellow * (yellow - 1) // 2
if blue > 0:
    answer += blue * (blue - 1) // 2
print(answer)
```

## 組み合わせと動的計画法

- 問題：[020 - Choose Cards 2](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_t)

整数が書かれたカードが**N**枚あり、これを**5**枚組み合わせて合計が**1000**になる組み合わせがいくつあるかという問題です。

**dp[選んだカードの枚数][合計値]** の配列を用意します。たとえば **dp[3][500]** が**3**であれば「**3枚のカードを選んで500になる組み合わせが3つある**」となります

```Python
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * 1001 for i in range(6)]  # dp[6][1001]
dp[0][0] = 1  # 0枚目で合計が0を1としておく
for i in range(N):
    for j in reversed(range(1001)):  # reversedにして同じカードが複数回選ばれないようにする
        for k in reversed(range(5)):  # reversedにして同じカードが複数回選ばれないようにする
            if dp[k][j] > 0 and j + A[i] < 1001:
                dp[k + 1][j + A[i]] += dp[k][j]
print(dp[5][1000])
```

## 組み合わせ 3

- 問題：[021 - Combination Easy](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_u)

組み合わせを求める問題です。
組み合わせの公式をそのままコードにすると下記です。

```Python
n, r = map(int, input().split())
answer = 1
for i in range(0, r):
    answer *= n - i
for i in range(1, r + 1):
    answer //= i
print(answer)
```

## 組み合わせ 4

- 問題：[022 - Choose Cards 3](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_v)

ペアにすると和が**100000**となるカードの組み合わせの数を求める問題です。

配列**card**を用意します。**card**は要素数が**100001**で、その数字のカードが何枚あるかを格納します。たとえば **card[3000]** の値は、**3000**のカードが何枚あるかです。
カードを選ぶ度に、そのカードと組み合わせて**100000**になるカードがこれまでに何枚あるかを変数**answer**に足しながら、**card**の値を加算していきます。

```Python
N = int(input())
A = list(map(int, input().split()))
card = [0] * 100001
answer = 0
for i in range(N):
    if card[100000 - A[i]] > 0:
        answer += card[100000 - A[i]]
    card[A[i]] += 1
print(answer)
```

## 確率と期待値 1

- 問題：[023 - Dice Expectation](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_w)

**B**と**R**の2つのサイコロの出目の期待値を求める問題です。

すべての目が等確率で出るので、**B**と**R**のそれぞれの合計値を**N**で割れば期待値となります。

```Python
N = int(input())
B = list(map(int, input().split()))
R = list(map(int, input().split()))
print(sum(B) / N + sum(R) / N)
```

## 確率と期待値 2

- 問題：[024 - Answer Exam Randomly](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_x)

**P個**の選択肢で配点が**Q**のテストがある場合の期待値を求める問題です。

正解の確率は**1/P**となります。
当たったときの点数は**Q**のため、各問題での期待値は**Q/P**です。
これを合計します。

```Python
N = int(input())
answer = 0
for i in range(N):
    P, Q = map(int, input().split())
    answer += Q / P
print(answer)
```

## 確率と期待値 3

- 問題：[025 - Jiro's Vacation](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_y)

サイコロで**1**か**2**が出た場合は**A**が適用され、**3〜6**が出た場合は**B**が適用される場合の期待値を求める問題です。

**1**か**2**が出る確率は**1/3**で、**3〜6**が出る確率は**2/3**です。**A**に**1/3**をかけ、**B**に**2/3**をかけていきます。

```Python
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

answer = 0
for i in range(N):
    answer += A[i] / 3 + 2 * B[i] / 3
print(answer)
```

## 確率と期待値 4

- 問題：[026 - Coin Gacha](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_z)

**N種類**のうちの1つがランダムで出るコインを全て揃えるためにかかる試行回数の期待値を求める問題です。

数式的には **1/N**、**1/(N-1)**、**1/(N-2)**...**1/1**の合計値に**N**をかければ求められます。
詳しい証明は検索していただければと思うのですが、つまりは以下のような感じです。

たとえば**4枚**のコインがあった場合、**1枚目**のコインはどれが出ても欲しいコインです。
つまり当たる確率は**4/4**です。
次が当たる確率(まだ出ていないコインである確率)は**3/4**になります。
さらに次は**2/4**で、最後は**1/4**です。

この逆数が必要な試行回数の期待値となるため、**4/4** + **4/3** + **4/2** + **4/1**です。
つまりは **4 * (1/4 + 1/3 + 1/2 + 1/1)** となります。

コードにすると下記です。

```Python
N = int(input())
p = 0
for i in range(1, N + 1):
    p += 1 / i
print(N * p)
```

## 再帰とマージソート

- 問題：[027 - Sorting](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aa)

**sort**を呼び出してしまえば終わりなのでしょうが、それだと学習にならないため、[マージソート](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88)のコードを記載します。
全体を分割し、並べ替えながら結合していくというものです。

```Python
# すでに昇順となっている二つの配列を受け取って昇順に並べる
def merge(left, right):
    il = 0
    ir = 0
    result = []
    while True:
        if left[il] < right[ir]:
            result.append(left[il])
            il += 1
        else:
            result.append(right[ir])
            ir += 1
        if il >= len(left):
            result += right[ir:]
            return result
        elif ir >= len(right):
            result += left[il:]
            return result

# 配列を真ん中で二つに分割し、分割した二つを引数として自らを呼び出し、最後にmergeを呼び出す
def divide(arr):
    len_arr = len(arr)
    if len_arr <= 1:
        return arr
    left = arr[:len_arr // 2]
    right = arr[len_arr // 2:]
    left = divide(left)
    right = divide(right)
    return merge(left, right)


N = int(input())
A = list(map(int, input().split()))
answer = divide(A)
print(*answer)
```

## 動的計画法 部分和問題 1

- 問題：[028 - Frog 1](https://atcoder.jp/contests/math-and-algorithm/tasks/dp_a)

**N個**の足場があり、それぞれの高さは**h**という配列に格納されています。
カエルは一つ先の足場か二つ先の足場にのみ移動でき、その際のコストは今いる足場との高さの差です。
カエルが**N個目**の足場にたどり着くまでのコストの総和の最小値を求めるという問題です。

**1個目**の足場にたどり着くまでのコストの最小値、**2個目**の足場にたどり着くまでのコストの最小値……**N個目**の足場にたどり着くまでのコストの最小値を順番に求めていきます。

下記はコードです。コードを簡潔にしたかったため足場を**0〜N-1**としてあるのでご注意ください。

```Python
N = int(input())
h = list(map(int, input().split()))

# i個目の足場にたどり着くまでのコストの最小値を格納する配列
dp = [float('inf')] * N  # 初期値として無限大を入れておきます
dp[0] = 0  # 最初にいる足場までのコストを0とする

for i in range(0, N - 1):  # 最初の足場から最後の1個前の足場まで
    for dist in [1, 2]:  # 1つ先の足場に移動した時と2つ先の足場に移動した時のコストの最小値を記録する
        if i + dist < N:  # 移動可能である
            diff = abs(h[i + dist] - h[i])  # 高さの差
            if dp[i] + diff < dp[i + dist]:  # 最小値である
                dp[i + dist] = dp[i] + diff
print(dp[N - 1])  # 最後の足場にいるときの最小値を出力する
```

## 動的計画法 部分和数え上げ問題

- 問題：[029 - Climb Stairs](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ab)

階段を同時に**1段**か**2段**だけ上れます。**N段目**にたどり着くまでのパターン数を求める問題です。

**step**という配列にパターン数を記録していきます。
たとえば**step[1]**なら**1段目**までのパターン数を格納します。これは**0段目**から**1段**上がったときの**1パターン**しかありません。

```Python
N = int(input())
step = [0] * (N + 2) # i+2の計算ではみ出たときのために+2としている
step[0] = 1
for i in range(N):
    step[i + 1] += step[i]
    step[i + 2] += step[i]
print(step[N])
```

## 動的計画法 最適化問題

- 問題：[030 - Knapsack 1](https://atcoder.jp/contests/math-and-algorithm/tasks/dp_d)

重さ**w**と価値**v**が割り当てられた**N個**の品物があります。
許容重量が**W**のナップサックに価値が最大化するように品物を入れてくださいという問題です。

いわゆる[ナップサック問題](https://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C)というやつです。

**dp[N+1][W+1]** の配列を用意します。
たとえば **dp[3][2]** ならば**3番目の品物までで許容重量が2までの場合の価値の最大値**を示します。

コードにすると下記です。

```Python
N, W = map(int, input().split())
v = [0] * N
w = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

# 2次元配列を初期値0で用意する
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):  # N個の荷物を順番に見る
    for j in range(W + 1):  # ナップサックの許容重量を0〜Wと仮定する
        if w[i] <= j:  # i番目の品物がナップサックの許容重量以下である
            # ナップサックに入れた方が価値が上がるかどうかを求める
            dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j])
        else:  # ナップサックに入れられないのでi-1番目の品物までの時の価値をそのまま用いる
            dp[i + 1][j] = dp[i][j]

print(dp[N][W])
```

## 動的計画法 部分和問題 2

先述の「[bit全探索と動的計画法](#bit全探索と動的計画法)」と同様です。

## 動的計画法 部分和問題 3

- 問題：[031 - Taro's Vacation](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ac)

**A**という配列から**連続**しないように値を選択した場合の合計の最大値を求める問題です。

**dp[i][0]** は**i番目**を選択しなかったときの最大値、**dp[i][1]** は**i番目**を選択したときの最大値を示すとします。

**dp[i][0]** は **dp[i-1][0]** と **dp[i-1][1]** の大きい方となります。選択をしていないため、前日の **[0]** の要素か **[1]** のいずれかのままとなるからです。
**dp[i][0]** は **dp[i-1][0]** と **A[i]** の和となります。2連続で選択することはできないため、前日の **[0]** の要素との和になります。

```Python
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * 2 for i in range(N + 1)]
for i in range(1, N + 1):
    dp[i][0] = max([dp[i - 1][0], dp[i - 1][1]])
    dp[i][1] = dp[i - 1][0] + A[i - 1]
print(max([dp[N][0], dp[N][1]]))
```

## 二分探索

- 問題：[032 - Binary Search](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ad)

**X**が配列**X**の中に存在するかを求める問題です。

下記のように**in**だけで終わります。

```Python
N, X = map(int, input().split())
A = list(map(int, input().split()))
if X in A:
    print('Yes')
else:
    print('No')
```

ただ、問題としては[二分探索](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2)を使うことを期待しています。

二分探索を使うと下記のコードです。

```Python
N, X = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
n = 1
low = 0
high = N - 1
while n > 0:
    n = (low + high) // 2
    if A[n] == X:
        print('Yes')
        exit()
    if A[n] < X:
        if low == n:
            break
        low = n
    else:
        if high == n:
            break
        high = n
print('No')
```

## 最後に

良い頭の体操になりました。

私は[Supershipグループ Advent Calendar 2023](https://qiita.com/advent-calendar/2023/supership)でも25日目に投稿予定です。盛り上がれー。

## 宣伝

[SupershipのQiita Organization](https://qiita.com/organizations/supership-inc)を合わせてご覧いただけますと嬉しいです。他のメンバーの記事も多数あります。

Supershipではプロダクト開発やサービス開発に関わる方を絶賛募集しております。
興味がある方は[Supership株式会社 採用サイト](https://supership.jp/recruit/)よりご確認ください。