【けんちょん本 to Python】-第３章-「問題解決力を鍛える！ アルゴリズムとデータ構造」掲載コードをPythonに書き直してみた！

はじめに

この記事は、競技プログラミングの解説を多数書かれているけんちょんさんの書籍、問題解決力を鍛える！ アルゴリズムとデータ構造（けんちょんさん本）について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。

このページでは、第３章掲載分について紹介します！
バグ等ありましたらご容赦ください。

他の章へのリンクは以下のページをご覧ください。
【目次ページ】
https://qiita.com/KevinST/items/002676619a583754bf76

code3.1　線形探索法

「前から順番に調べよう」のやつですね！

code3-1.py

#入力を受け取る
N, v = map(int, input().split())
a = list(map(int, input().split()))

#線形探索
exist = False
for i in range(N):
    if a[i] == v:
        exist = True

#結果出力
if exist:
    print("Yes")
else:
    print("No")

【入力例】
5 1
2 3 4 1 11
【出力例】
Yes

code3.2　特定の要素の存在する「添字」も取得する

今度はindexの取得です。

code3-2.py

#入力を受け取る
N, v = map(int, input().split())
a = list(map(int, input().split()))


##線形探索##
found_id = -1
for i in range(N):
    if a[i] == v:
        found_id = i
        break
print(found_id)

【入力例】
4 2
0 2 -1 11
【出力例】
1

数「2」に対して
a[0]: 0
a[1]: 2
...
と探していきます。
今回はa[1] = 2で、ここで探していた数とa[i]が一致するため、
ここでbreakして出力。

code3.3　最小値を求める

code3-3.py

#入力を受け取る
N = int(input())
a = list(map(int, input().split()))


##線形探索##
#最小値の初期値を「無限大」にセット
min_value = float("inf")
for i in range(N):
    if a[i] < min_value:
        min_value = a[i]
print(min_value)

【入力例】
4
0 2 -1 11
【出力例】
-1

一番小さい値「-1」を探すことができました。
計算量は$O(N)$です。

code3.4　ペア和の最小値を求める（K以上の範囲）

配列aから1つ、配列bから1つ要素を選んで足し、数を作ります。
それらのうち、K以上のもので、最も小さいものを選びます。

code3-4.py

#入力を受け取る
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

#線形探索
min_value = float("inf")
for i in range(N):
    for j in range(N):
        #和がK未満の場合は捨てる
        if a[i] + b[j] < K:
            continue
        #最小値を更新
        if a[i] + b[j] < min_value:
            min_value = a[i] + b[j]
print(min_value)

【入力例】
4 10
1 2 5 6
7 12 16 22
【出力例】
12

code3.5　整数bitの表す部分集合にi番目の要素が含まれるかどうかを判定する

いわゆるbit全探索の下準備です。
動作確認のため、入出力もつけてみました。

code3-5.py

#入力を受け取る
i = int(input())
bit = int(input(), 2)

#bitの表す部分集合にi番目の要素が含まれるかどうかチェック
if bit & (1 << i):
    print("Yes")
else:
    print("No")

【入力例】
1
1010
【出力例】
Yes

bit全探索というのは、全探索手法の一つで、ON・OFFのパターンを全通り列挙できるものです。
詳しくはけんちょんさん本やネットでの解説をご覧ください。

なお、「び、ビット…いやー難しいぜ><」という方は、Pythonの機能を使って、bitについて考えず全探索できます
（「3.6補足」参照）

code3.6　部分和問題に対するビットを用いる全探索手法

bit全探索です。

code3-6.py

#入力を受け取る
N, W = map(int, input().split())
a = list(map(int, input().split()))

#bitが2^n通りの部分集合全体を動きます
exist = False
for bit in range(2**N):
    #部分集合に含まれる要素の和
    sum_val = 0
    for i in range(N):
        #i番目の要素a[i]が部分集合に含まれるかどうか
        if bit & (1 << i):
            sum_val += a[i]

    #sum_valがWに一致するかどうか
    if sum_val == W:
        exist = True

if exist:
    print("Yes")
else:
    pritn("No")

【入力例】
4 10
1 9 100 200
【出力例】
Yes

(1,9)という部分集合を考えます。
その和が10なので、Wと一致します。
ですので答えは「Yes」ですね。

code3.6補足　itertools.combinationsを使用した全列挙

bitむずいぜ！という方のために、別verも用意しました。
手順としては
　１．配列の中から何個取り出すか決める（0個～N個）
　２．要素N個の配列の中から１で決めた個数を取り出すと考える
　　　取り出す全パターンについて列挙
　　　0個: []
　　　1個: [a0], [a1], [a2]...
　　　2個: [a0, a1], [a0, a2], ... ,[aN-1, aN]
　　※Pythonの便利ライブラリitertools内の、combinations関数を使用

Pythonはいいぞ！（宣伝）

code3-6-another_ver.py

from itertools import combinations
N, W = map(int, input().split())
a = list(map(int, input().split()))

exist = False

# 取り出す要素の数を決める（num_of_a）：　0個～N個
for num_of_a in range(N+1):
    #aの中から、すべでのnum_of_a個の取り出し方で要素を取り出し、それぞれ変数patternに格納
    for pattern in combinations(a, num_of_a):
        #合計を計算
        sum_val = sum(list(pattern))
        #sum_valがWに一致するかどうか
        if sum_val == W:
            exist = True

if exist:
    print("Yes")
else:
    pritn("No")

【入力例】
4 10
1 9 100 200
【出力例】
Yes

itertoolsについて詳しく知りたい方は、以下のページが参考になるかと思います。
読めばPython標準ライブラリの便利さに感動するかと！
すごいぞitertoolsくん

第４章はこちら
https://qiita.com/KevinST/items/f846d57e56242c6e1293