Union Find木

Union Find木 は、グループ分けを管理することができるデータ構造です。

次のようなことを効率的に行うことができます。

• 要素aと要素bが同じグループに属しているかどうかをチェックする。
• 要素aと要素bのグループを一つにまとめる。

グループ同士をまとめることはできますが、要素をグループから除いたり、グループを分けたりすることはできません。

Union Find木 を実現するためのクラスは以下のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

from collections import defaultdict

# n個の要素を0 ～ n - 1のインデックスで管理する
class UnionFind():
    def __init__(self, n):
        self.n = n                # 要素の数
        self.parents = [-1] * n   # 各要素の親要素の番号を格納するリスト

    def find(self, x):            # 要素[x]が属するグループの親を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):        # 要素[x]が属するグループと要素yが属するグループとを併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):            # 要素[x]が属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):         # 要素[x],要素[y]が同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):         # 要素[x]が属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):              # すべての親の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):        # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # 全グループの全要素を返す
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):  # printでの表示用。ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

動作確認

実装した Union Find木 の動作を確認してみます。

要素数5個（0,1,2,3,4）のUnion Find木を定義し、[0,1]のグループと[2,3,4]のグループに分けます。

[Google Colaboratory]

1
2
3
4
5
6

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(3, 4)

print(uf)

[実行結果]

0: [0, 1]

2: [2, 3, 4]

２つのグループに分けることができました。

親の要素(一番もとになる要素)がグループのキーとなっていることが確認できます。

次に、要素1と要素3が所属するグループを調べてみます。

[Google Colaboratory]

1
2

print(uf.find(1))
print(uf.find(3))

[実行結果]

0

2

要素1がグループ0に所属し、要素3がグループ2に所属していることが分かりました。

今度は、要素0,要素2が同じグループに属するかどうかと、要素3,要素4が同じグループに属するかどうかを調べます。

[Google Colaboratory]

1
2

print(uf.same(0, 2))
print(uf.same(3, 4))

[実行結果]

False

True

要素0,要素2は違うグループであり、要素3,要素4は同じグループに属することを確認できました。

最後に、要素3が所属するグループの全要素を表示します。

[Google Colaboratory]

1

print(uf.members(3))

[実行結果]

[2, 3, 4]

要素3が所属するグループの全要素は、2,3,4であることが分かりました。

次回は、Union Find木 を使って問題を解いてみます。

線形計画問題

線形計画問題 は、ある条件下での 領域の最大・最小 を求める問題です。

数理最適化ライブラリのPuLP を使うと、線形計画問題 を解くことができます。

[問題]

ある工場では製品 p と製品 q を製造しています。

製品 p と製品 q を製造するには原料 m と原料 n が必要で、次のような条件となっています。

・製品 p を１ｋｇ製造するには原料 m が１ｋｇ、原料 n が２ｋｇ必要。

・製品 q を１ｋｇ製造するには原料 m が３ｋｇ、原料 n が１ｋｇ必要。

・原料 m の在庫は３０ｋｇ、原料 n の在庫は４０ｋｇあります。

・単位量当たりの利益は、製品 p が１万円、製品 q が２万円です。

この条件で利益を最大にするためには、製品 p と製品 q をそれぞれ何ｋｇ製造すればよいでしょうか。

製品 p の製造量を x ｋｇ、と製品 q の製造量を y ｋｇとすると以下のように不等号をつかった式にまとめることができます。

x + 3y ≦ 30
2x + y ≦ 40
x ≧ 0、y ≧ 0

連立方程式との違いは、等号（==） が 不等号（≧、≦） になっている点です。


 ソースコード

上記の条件式をもとにソースコードを作成すると下記のようになります。

[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 製品pを製造する量。変数xをpulp.LpVariable関数を定義。
y = pulp.LpVariable('y')    # 製品qを製造する量。変数yをpulp.LpVariable関数を定義。

# 線形計画問題の条件式
problem += 1 * x + 3 * y <= 30
problem += 2 * x + 1 * y <= 40
problem += x >= 0
problem += y >= 0

problem += x + 2 * y        # 目的関数。最大化する式。

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value(), 'obj =', problem.objective.value()) # xとyの解と利益の関数値


[実行結果]
Status: Optimal

x = 18.0 y = 4.0 obj = 26.0


製品 p の製造量を １８ｋｇ、と製品 q の製造量を ４ｋｇとしたときに利益を最大にできることが導きだされました。
obj = 26.0 は最大化しようとした利益の関数値です。（15行目）
x + 2 * y = 26 となることが確認できます。

      
    

数理最適化

数理最適化ライブラリ PuLP を使って、連立一次方程式を解いてみます。

本来の数理最適化ライブラリの使い方とは少々異なりますが、数理モデルを初めて実装するにはとてもよい題材です。

[問題]

１個１２０円のリンゴと１個１５０円のミカンを合わせて１０個買ったら代金の合計が１４４０円でした。

リンゴとミカンをそれぞれ何個買ったでしょうか。

この問題は、リンゴの個数を x、ミカンの個数を y として連立一次方程式を立てることができます。

120x + 150y = 1440
x + y = 10

 ソースコード

まずは 数理最適化ライブラリ PuLP をインストールできます。

[Google Colaboratory]
1
!pip install pulp


連立一次方程式をソースコードにすると下記のようになります。

[Google Colaboratory]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pulp

# 第１引数は任意の名前、第２引数は最大化問題を解く指定（今回は連立一次方程式を解くのでとくに意味はない）
problem = pulp.LpProblem('Test', pulp.LpMaximize)

x = pulp.LpVariable('x')    # 変数xをpulp.LpVariable関数を定義
y = pulp.LpVariable('y')    # 変数yをpulp.LpVariable関数を定義

problem += 120 * x + 150 * y == 1440    # 連立一次方程式を定義
problem += x + y == 10                  # 連立一次方程式を定義

status = problem.solve()    # 数理モデルを解く

print('Status:', pulp.LpStatus[status])   # 結果
print('x =', x.value(), 'y =', y.value()) # xとyの解


[実行結果]
Status: Optimal
x = 2.0 y = 8.0


Optimal は、最適化計算をした結果最適解が得られたという意味です。
リンゴの個数は2、ミカンの個数は8となり、合わせて１０個 であり、代金の合計も １４４０円 で、連立一次方程式の解として正しいことが確認できます。

      
    

部分和問題

深さ優先探索では、一番はじめの状態から遷移を繰り返すことで 全ての状態 を生成します。

したがって、すべての状態に対して操作 を施したり、全状態を列挙 することが可能です。

[問題]

整数が n個 与えられます。

その中からいくつか選び、その和をちょうど k にすることができるか判定してください。

[条件]

・整数の個数 n は、1以上20以下
・各整数の値は、-100000000以上100000000以下
・目標とする数値（部分和） k は、-100000000以上100000000以下

[解き方]
各整数を１つ目から順番に加えるかどうかを決めていき、n個すべてについて決め終わったら、その和が k に等しいかどうかを判定します。

再帰関数を使用します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# ------------ 入力例１ ----------
lst = [1, 2, 4, 7]    # 各要素
k = 13                # 目標とする数値（部分和）
# ------------ 入力例２ ----------
# lst = [1, 2, 4, 7]  # 各要素
# k = 15              # 目標とする数値（部分和）
# --------------------------------
def dfs(i, total):
    print(i,total)
    if i == len(lst):       # 全部決め終わった場合
        return total == k   # 今までの和が[目標とする数値]と等しいかどうかを返す
    
    if dfs(i + 1, total):   # lst[i]を使わない場合
        return True
    
    if dfs(i + 1, total + lst[i]):  # lst[i]を使う場合
        return True

    # lst[i]を使うか使わないかにかかわらず[目標とする数値]がつくれないので False を返す
    return False

if dfs(0, 0):
    print('Yes')
else:
    print('No')

[実行結果（入力例1）]

Yes

2 + 4 + 7 を足し合わせると 13 になるので Yes が解となります。

[実行結果（入力例2）]

No

どんな組み合わせを行っても 15 となることはないので No が解となります。

半分全列挙

全パターンを列挙することができないようなサイズの問題でも、半分ならば全列挙を行うことができる ような場合があります。

このような場合、それぞれ半分ずつ全列挙されたものを組み合わせるという手法が有効なことがよくあります。

[問題]

要素数nの整数のリストA、B、C、Dがあります。

各リストから１つずつ取り出したとき、その和が０となる ような
組み合わせの個数を求めなさい。

ただし、１つのリストに同じ値が複数個含まれている場合、
それらは異なるものとして数えます。

[条件]

・要素数は、1以上4000以下

・リストの値の絶対値は、2の28乗以下

[解き方]
４つのリストからの取り出し方は全部で nの4乗通り もあるため、全てを調べることはできませんが、リストをABとCDという 半分ずつの組に分けて 考えることにより、効率的に解くことが可能になります。

２つのリストからの取り出し方は nの2乗通り しかないため、これならば全パターン列挙することができます。

リストAとリストBからそれぞれa,bを取り出したときに和を０にするには、リストCとリストDからの取り出し方 nの2乗通り 全てについて、その和を全て算出しておくことにより検索しやすくなります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#--------入力例１----------------
n = 6
a = [-45,-41,-36,-36,26,-32]
b = [-16,30,77,-46,62,45]
c = [42,56,-37,-75,-10,-6]
d = [22,-27,53,30,-38,-54]
#--------------------------------
# リストCとリストDからの取り出し方の組を全部列挙
cd = [c1 + d1 for c1 in c for d1 in d]

cnt = 0
for a1 in a:        # リストAを全部列挙
    for b1 in b:    # リストBを全部列挙
        # リストCとリストDからの和がabとなるように取り出す
        ab = (a1 + b1)*-1
        if ab in cd:
            cnt += 1
print(cnt)

[実行結果]

5

結果としては、組み合わせ数 5 だけが表示していますが、ソースを少し修正すると和が０になるときの組み合わせを表示することができます。

[組み合わせ]

①-45 30 42 -27
②26 -46 -10 30
③-32 30 56 -54
④-32 77 -75 30
⑤-32 -46 56 22

興味がある方は、組み合わせを表示するようにソースコードを修正してみてください。

二分探索

二分探索 は、データ数が増えても 高速に検索 することができるアルゴリズムです。

辞書や電話帳から探すときに似た方法で、目的の値がそれよりも 前か後ろか を判断して探す方法です。

データは昇順に並んでいる必要があります。

ソースコード

二分探索 では、昇順に並んでいるデータの中から目的のデータが、真ん中より右にあるか左にあるかを調べる作業を繰り返します。

実装すると下記のようなソースになります。

リストの左端と右端から、探す位置を半分に絞り込みながら順に検索しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def binary_search(data, value):
    left = 0                      # 検索する範囲の左側を設定
    right = len(data) - 1         # 検索する範囲の右側を設定
    while left <= right:          # 検索する範囲がなくなるまで実行
        mid = (left + right) // 2 # 検索する範囲の中央の値を算出
        if data[mid] == value:    # 中央の値と一致した場合
            return mid            # その位置を返す
        elif data[mid] < value:   # 中央の値より大きい場合
            left = mid + 1        # 検索範囲の左側を移動
        else:                     # 中央の値より小さい場合
            right = mid - 1       # 検索範囲の右側を移動
    return -1                     # 見つからなかったので-1を返す

data = [10,20,30,40,50,60,70,80,90]

print('値が見つかるケース１ =>', binary_search(data,80))
print('値が見つかるケース２ =>', binary_search(data,20))
print('値が見つかるケース３ =>', binary_search(data,60))
print('値が見つからないケース１ =>', binary_search(data,9))
print('値が見つからないケース２ =>', binary_search(data,23))
print('値が見つからないケース３ =>', binary_search(data,91))

[実行結果]

値が見つかるケース１ => 7
値が見つかるケース２ => 1
値が見つかるケース２ => 5
値が見つからないケース１ => -1
値が見つからないケース２ => -1
値が見つからないケース３ => -1

値が見つかった場合はその インデックス を、見つからなかった場合は -1 を返すことを確認できました。

ユークリッドの互除法

ユークリッドの互除法 は２つの自然数の 最大公約数 を効率的に求めることができるアルゴリズムです。

ユークリッドの互除法 は、次の定理に基づいており、その名の通り除法つまり 割り算 を繰り返して計算しています。

[定理]

２つの自然数 a, b について、a を b で割ったときの商 q、余りを r とすると、
a と b の最大公約数 は b と r の最大公約数 に等しい。

例として、a=1274、b=975 の場合、次のように 最大公約数 を求めることができます。

(1) 1274 ÷ 975 = 1 余り 299
(2) 975 ÷ 299 = 3 余り 78
(3) 299 ÷ 78 = 3 余り 65
(4) 78 ÷ 65 = 1 余り 13
(5) 65 ÷ 13 = 5 余り 0

ソースコード

上記の例をコードにすると下記のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7

# ユークリッドの互除法
def gcd(a, b):
    while b != 0:         # 余りが0になるまで繰り返す
        a, b = b, a % b   # [割る数]と[割られる数]を入れ替え、[余り]を[割る数]に代入
    return a              # 最大公約数を返す(余りが0になったときの[割る数])

print(gcd(1274, 975))

[実行結果]

13

効率的に 最大公約数 を求めることができました。

エラトステネスの篩（ふるい）

エラトステネスの篩（ふるい）は、効率よく 素数 を求めることができるアルゴリズムです。

指定された範囲の中から２で割り切れる数、３で割り切れる数、・・・・と割り切れる数を順に除外する方法です。

これを繰り返すと最後には 素数 だけが残ることになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import math

def get_prime(n):
    if n <= 1:                  # 1以下の場合
        return []               # 空リストを返す
    prime = [2]                 # 素数リストを 2 だけで作成
    limit = int(math.sqrt(n))   # 検索する上限を設定(nの平方根)

    data = [i for i in range(3, n, 2)]      # 奇数のリストを作成
    while limit >= data[0]:                 # 上限≧奇数の先頭の場合
        prime.append(data[0])               # 素数リストに奇数の先頭を追加
        # 奇数リストのうち、先頭の数で割り切れないものでリストを作成
        data = [j for j in data if j % data[0] != 0]

    return prime + data       # 素数リストと奇数のリストを合わせて返す

print(get_prime(100))         # 100までの素数を求める

[実行結果]

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

高速に素数を求めることができました。

プライオリティキュー

プライオリティキュー を使って、下記の問題を解いてみます。

[問題]

車で 距離L の道を移動します。車にはもともとガソリンが P はいっています。

この車では距離１走るとガソリンが１消費されます。ガソリンが０になると車は停止し移動は失敗します。

途中には N箇所 のガソリンスタンドがあり、各ガソリンスタンドは道のスタート地点からそれぞれ 距離Ai の地点にあり Bi だけガソリンを補給することができます。

車の燃料タンクにはいくらでもガソリンを補給できます。

車は最後まで移動できるでしょうか。最後まで移動できる場合は 最小の補給回数 を、移動できない場合は -1 を出力してください。

[条件]

・ガソリンスタンド数Nは、1以上10000以下です。
・目的とする移動距離Lと初期ガソリン量は、1以上1000000以下です。
・スタート地点から各ガソリンスタンドまでの距離Aiは、1以上目的とする移動距離L以下です。
・各ガソリンスタンドで補給できるガソリン量Biは、1以上100以下です。

[解き方]

車で走るときには、ガソリンスタンドの場所に来た時にしかガソリンを補給できません。

しかし ガソリンスタンドの場所に来た時、それ以降いつでも一度だけガソリンを補給できる権利を手に入れる というように考えることもできます。

後で補給したくなった時に、すでに通過したガソリンスタンドで補給していたことにします。

できるだけ少ない回数の補給にしたいので、燃料が０になるまで走ってから補給をすることにします。

燃料が０になったときに使うべきガソリンスタンド（ガソリン量）は、明らかに最も大きいガソリン量です。

これを効率的に行うために、大きい数字から順に取り出せる プライオリティキュー を使います。


通常のリスト型から max関数 で一番補給量の多いものを取得し、取得したら remove関数 でその要素を削除することで プライオリティキュー の機能を実現します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#------------入力例１-----------------
L = 25  # 距離[L]
P = 10  # 初期ガソリン量[P]
# 各ガソリンスタンド（４か所）までの 距離[Ai] と ガソリン補給量[Bi]
stands = [{'A':10,'B':10}, {'A':14,'B':5}, {'A':20,'B':2}, {'A':21,'B':4}]
#-------------------------------------
cnt = 0   # 補給回数
pos = 0   # 現在の位置（スタート地点からの距離）
tank = P  # 現在の保有ガソリン量
lst = []  # ガソリンを補給できる権利（通り過ぎたガソリンスタンドで補給できたはずのガソリン量）

# 目的とする移動距離をガソリンスタンド管理データ[stands]に追加（補給はしないのでガソリン量は0）
stands.append({'A':L,'B':0})

for stand in stands:    # 移動箇所（各スタンド＋目的移動距離）分ループでまわす
  d = stand['A'] - pos  # このポイントまでの距離

  while tank - d < 0:   # 現在のガソリン量でスタンドまでたどり着けるかどうか
    # ガソリンが足りない場合
    if len(lst) > 0:    # ガソリン補給の権利があるかどうか
      x = max(lst)      # 一番補給量の多いものを取得（プライオリティキー機能として）
      lst.remove(x)     # 一番補給量の多いものを削除（プライオリティキー機能として）
      tank += x         # ガソリンを補給
      cnt += 1          # ガソリン補給回数をカウントアップ
    else:               # ガソリン補給ができない
      cnt = -1          # 移動失敗
      break

  if cnt < 0:           # 移動失敗したので終了
    break
  else:                 # 移動成功
    tank -= d           # タンクのガソリンを移動距離分減らす
    pos = stand['A']    # 現在位置をガソリン位置まで移動 
    lst.append(stand['B'])  # 到達したガソリンスタンドのガソリン補給可能量を権利としてリストに追加

print(cnt)

[実行結果]

2

１つめのと２つ目のガソリンスタンドでガソリンを補充すると目的の距離まで走ることができ、かつ最小の補給回数なので 2 が解となります。

しゃくとり法

しゃくとり法 というアルゴリズムを使って、下記の問題を解いてみます。

[問題]

1
2
3

長さ<b>n</b>の数列 <b>a1,a2,..</b> と整数<b>S</b>が与えられます。
連続する部分列で、その合計が<b>S</b>以上となるもののうち、<b>最小の長さ</b> を求めなさい。
解が存在しない場合は<b>0</b>を出力しなさい。

[条件]

1
2
3

・長さ<b>n</b>は <b>5以上 100000未満</b>
・数列の各要素は、<b>0より大きく10000以下</b>
・整数Sは <b>100000000未満</b>

この問題は、区間の先頭と末尾を 交互 に進めながら条件を満たす 最小の区間 を調べることで解くことができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

a = [5,1,3,5,10,7,4,9,2,8]
S = 15

n = len(a)        # 配列数
res = n + 1       # 最小区間の初期値（配列数＋１）
s = 0             # 集計開始位置
t = 0             # 集計最終位置
total = 0         # 合計値

while True:
    while t < n and total < S:  # 集計最終位置が配列内かどうか、合計値がSより小さいかどうか
        total += a[t]           # 合計値を算出
        t += 1                  # 集計最終位置を１つうしろにずらす
    if total < S:
        break                   # 合計値が条件(整数S以上)に達していないので終了（集計最終位置が配列を超えた）
    res = min(res, t - s)       # 合計値が条件を満たしている部分列の長さが、より短い場合は更新
    total -= a[s]               # 合計値から先頭の要素をひく
    s -= 1                      # 集計開始位置を１つうしろにずらす

if res > n:       # 配列数より大きいので解がなかった
    res = 0       # 解がなかったため0を設定
print(res)        # 解を出力

[実行結果]

1

2

配列の４番目から５番目の２要素(5,10)を足すと15を超えますので、出力結果の2は正解ということになります。