深さ優先探索（通りがけ順）

深さ優先探索

目的の方へ進めるだけ進んで、進めなくなったら戻る方法を深さ優先探索といいます。

深さ優先探索は、バックトラックとも呼ばれ、すべての答えを見つけるときによく使われます。

深さ優先探索は、順番によって次の３種類があります。

🔹 行きがけ順
🔹 帰りがけ順
🔹 通りがけ順

ソースコード（通りがけ順）

次のような木構造があるとします。

[木構造]

深さ優先探索は、再帰を使って実装するのが一般的です。

通りがけ順では、２分木の左側の子ノードを先に処理し、次に右側の子ノードを処理します。

[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
# 木構造を表すデータ
#  キー：ノード番号
#  値：ノードにぶら下がっているノード
tree = {0:[1, 2],
        1:[3, 4],
        2:[5, 6],
        3:[7, 8],
        4:[9, 10],
        5:[11, 12],
        6:[13, 14],
        7:[],
        8:[],
        9:[],
        10:[],
        11:[],
        12:[],
        13:[],
        14:[]}

def search(pos):
    if len(tree[pos]) == 2:     # 子ノードが２つある場合
        search(tree[pos][0])
        print(pos, end=' ')     # 左のノードと右のノードの間に出力
        search(tree[pos][1])
    elif len(tree[pos]) == 1:   # 子ノードが１つある場合
        search(tree[pos][0])
        print(pos, end=' ')     # 左のノードを調べた後に出力
    else:                       # 子ノードがない場合
        print(pos, end=' ')

search(0)       # ノード0から通りがけ順で探索

[実行結果]

7 3 8 1 9 4 10 0 11 5 12 2 13 6 14

常に左側のノード番号が優先的に出力されていることを確認できます。

深さ優先探索（帰りがけ順）

深さ優先探索

目的の方へ進めるだけ進んで、進めなくなったら戻る方法を深さ優先探索といいます。

深さ優先探索は、バックトラックとも呼ばれ、すべての答えを見つけるときによく使われます。

深さ優先探索は、順番によって次の３種類があります。

🔹 行きがけ順
🔹 帰りがけ順
🔹 通りがけ順

ソースコード（帰りがけ順）

次のような木構造があるとします。

[木構造]

深さ優先探索は、再帰を使って実装するのが一般的です。

帰りがけ順では、各ノードの子をすべてたどった後でそのノードを処理します。

行きがけ順と比べて、printする位置だけが変わっています。（23行目）

[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
# 木構造を表すデータ
#  キー：ノード番号
#  値：ノードにぶら下がっているノード
tree = {0:[1, 2],
        1:[3, 4],
        2:[5, 6],
        3:[7, 8],
        4:[9, 10],
        5:[11, 12],
        6:[13, 14],
        7:[],
        8:[],
        9:[],
        10:[],
        11:[],
        12:[],
        13:[],
        14:[]}

def search(pos):
    for i in tree[pos]:     # 配下のノードを調べる
        search(i)           # 再帰的に探索
    print(pos, end='　')    # 配下のノードを調べた後に出力

search(0)       # ノード0から帰りがけ順で探索

[実行結果]

7　8　3　9　10　4　1　11　12　5　13　14　6　2　0　

深いノードの番号が出力されたあとにその親ノードが順に出力され、最後にノード0が出力されることを確認できます。

深さ優先探索（行きがけ順）

深さ優先探索

目的の方へ進めるだけ進んで、進めなくなったら戻る方法を深さ優先探索といいます。

深さ優先探索は、バックトラックとも呼ばれ、すべての答えを見つけるときによく使われます。

深さ優先探索は、順番によって次の３種類があります。

🔹 行きがけ順
🔹 帰りがけ順
🔹 通りがけ順

ソースコード（行きがけ順）

次のような木構造があるとします。

[木構造]

深さ優先探索は、再帰を使って実装するのが一般的です。

行きがけ順では、各ノードの子を辿る前にそのノードの一番深くまで探索を行います。

[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
# 木構造を表すデータ
#  キー：ノード番号
#  値：ノードにぶら下がっているノード
tree = {0:[1, 2],
        1:[3, 4],
        2:[5, 6],
        3:[7, 8],
        4:[9, 10],
        5:[11, 12],
        6:[13, 14],
        7:[],
        8:[],
        9:[],
        10:[],
        11:[],
        12:[],
        13:[],
        14:[]}

# 深さ優先探索（行きがけ順）
def search(pos):
    print(pos, end='　')    # 配下のノードを調べる前に出力
    for i in tree[pos]:     # 配下のノードを調べる
        search(i)           # 再帰的に探索

search(0)       # ノード0から行きがけ順で探索

[実行結果]

0　1　3　7　8　4　9　10　2　5　11　12　6　13　14　

幅優先探索とは違って、ノード0から一番深いノードまで行って上に戻り、再度別の深いノードへ進むという順番に探索されていることが確認できます。

幅優先探索（木構造）

幅優先探索

捜索を開始するところから近いものをリストアップし、それぞれを細かく調べていく方法を幅優先探索といいます。

本を読むときに目次を見て全体を把握し、さらにそれぞれの章について概要を読み、さらに内容を読む、というように徐々に深く読んでいくようなイメージです。

ソースコード

次のような木構造があるとします。

[木構造]

この木構造について、ノード0（一番上のノード）から順番に幅優先探索を行います。

探索を開始するところから近いものをリストアップし、さらにそれぞれを細かく調べていきます。

[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
# 木構造を表すデータ
#  キー：ノード番号
#  値：ノードにぶら下がっているノード
tree = {0:[1, 2],
        1:[3, 4],
        2:[5, 6],
        3:[7, 8],
        4:[9, 10],
        5:[11, 12],
        6:[13, 14],
        7:[],
        8:[],
        9:[],
        10:[],
        11:[],
        12:[],
        13:[],
        14:[]}

# 幅優先探索
data = [0]      # 探索を開始するノードを設定
while len(data) > 0:
    pos = data.pop(0)       # 先頭ノードを取り出し
    print(pos, end=' ')
    for i in tree[pos]:     # そのノードにぶら下がっているノードを
        data.append(i)      # リストの後ろに追加

[実行結果]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

リストのインデックスを順番に出力しており、木構造を上から順に出力していることが分かります。

Nim（古典的なゲーム）

Nim

石の山が $ n $ 個あって、それぞれ $ a_i $ 個の石を含んでいます。

Nancy と Tom は交互に空ではない山を１つ選び、そこから１つ以上の石を取ります。

Nancy の番からはじまり、最後の石を取った方が勝ちです。

両者が最善を尽くした場合、どちらが勝つでしょうか？

解法・ソースコード

この問題は Nim と呼ばれる古典的なゲームです。

このゲームの考え方は多くのゲームの基礎となります。

このゲームの勝ち負けの判定には 排他的論理和(XOR) を使います。

　 $ a_1　XOR　a_2　XOR　…　a_n \neq 0 → 勝ちの状態 $
　 $ a_1　XOR　a_2　XOR　…　a_n = 0 → 負けの状態 $

排他的論理和(XOR) を計算し、0でなければNancyの勝ち、0ならばBobの勝ちとなります。

上記を証明します。

  • 負けの状態からは勝ちの状態にしかいけない。
    XORが0の状態から１つ以上石を取ると、XORは必ず0ではなくなります。
  • 勝ちの状態からは常に負けの状態を作れる。
    XORの結果を２進数で見たとき一番上のビットが立っているような山を選びます。
    そこから１番上のビットが0になり、かつ残りのXOR結果が1ビットが反転するように石を取るとXORを0にできます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
#--------- 入力例 1 ---------
n = 3           # 山の数
a = [1, 2, 4]   # 山ごとにある石の数
#--------- 入力例 2 ---------
# n = 3           # 山の数
# a = [1, 2, 3]   # 山ごとにある石の数
#----------------------------
x = 0
for a1 in a:
    x ^= a1
    print(bin(x))

print('解：', 'Tom' if x == 0 else 'Nancy')

[実行結果(入力例1)]

0b1

0b11

0b111

解： Nancy

[実行結果(入力例2)]

0b1

0b11

0b0

解： Tom

素数ライブラリ（SymPy）

SymPy

SymPyライブラリを使うと、素数を簡単に扱うことができます。

Google Colaboratoryでは、SymPy がすでにインストールされていますが、ローカル環境では下記のコマンドでSymPyをインストールする必要があります。

[Google Colaboratory]

1
pip install sympy

素数を求める

一定範囲の素数を求める場合は、sieve.primerangeを使います。

[Google Colaboratory]

1
2
3
from sympy import sieve

print([i for i in sieve.primerange(1, 30)])

[実行結果]

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

素数かどうかを判定する

ある数値が素数かどうかを判定する場合は、isprimeを使います。

[Google Colaboratory]

1
2
3
from sympy import isprime

print(isprime(101))

[実行結果]

True

文字列操作（区間分割・連長圧縮）

問題

文字列 $ S $ が与えられます。

これは、１つ以上の 単語 を連結したものとなっています。

各単語は２文字以上であり、最初の文字と最後の文字が大文字で、残りの文字は小文字となっています。

これらの単語を辞書順に並べて（大文字小文字の違いは無視）、その順に連結して出力して下さい。

解法・ソースコード

この問題は 連長圧縮 と同じ方法で解くことができます。

添え字 $ i $ を先頭から順に動かしながら、下記のように処理していきます。

🔹 大文字 $ s[i] $ に対して、その次の大文字がどこにあるのか探す。
　 その大文字を $ s[j] $ とする。
🔹 $ s[i] $ から $ s[j] $ までの部分文字列を１つの単語として切り出す。
🔹 $ i = j + 1 $ と更新する。
　 $ j $ は単語の終わりを表す添え字なので、その次の $ j + 1 $ に $ i $ を移動する。

上記の処理で取り出した単語のリストをソートして、連結して出力します。　

大文字小文字を無視した状態での辞書順比較は sorted(words, key=str.lower) として行うことができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#--------- 入力例 ----------
s = "FisHDoGCaTAAAaAAbCAC"
#---------------------------
words = []      # 単語のリスト

# 文字列 s を単語ごとに分解する
i = 0
while i < len(s):
    j = i + 1   # s[j] が大文字になる j を見つける
    while j < len(s) and s[j].islower():
        j += 1
    # 単語を切り出してリストに追加
    words.append(s[i:j + 1])

    i = j + 1       # i を j + 1 に移動

# 単語を大文字小文字を無視した状態でソート
words = sorted(words, key=str.lower)

print('解：', ''.join(words))

[実行結果]

解： AAAaAAbCACCaTDoGFisH

問題文で指示された通りの文字列を出力することができました。

区間分割・連長圧縮

区間分割・連長圧縮

$ N $ 個の要素を区分に分割する問題は、比較的よく出題されます。

区分に分割する処理の一例として、連長圧縮 があります。

連長圧縮 は、"AAABBBBBAACDD" といった文字列を ('A', 3), ('B', 5), ('A', 2), ('C', 1), ('D', 2) のようにデータ１つ分と連続した長さとの組で表現します。

ソースコード

連長圧縮 を行うサンプルソースは次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#--------- 入力例 ----------
s = 'AAABBBBBAACDD'
#---------------------------
n = len(s)      # 文字列の長さ
i = 0
while i < n:
    # s[j] != s[i] となる位置を探す
    j = i
    while j < n and s[j] == s[i]:
        j +=  1
    # 文字 s[i] が j - 1 文字連続したことがわかる
    print(s[i], j - i)
    # i を j の位置へ移動
    i = j

[実行結果]

A 3
B 5
A 2
C 1
D 2

文字列を区間ごとに分割することができました。

じゃんけん（全探索）

問題

コンピュータと $ N $ 回じゃんけんをします。

コンピュータの出す手はあらかじめ分かっていて、“G”はグー、“C”はチョキ、“P”はパー を表します。

あなたが、$ N $ 回のじゃんけんで出した 指の本数の合計 がちょうど $ M $ 本になるようにじゃんけんをすると、最高で何回 じゃんけんに勝つことができるでしょうか。

解法・ソースコード

まず今回はじゃんけんの指の合計数を求める問題なので、順番は気にする必要がありません。

次に、じゃんけんで出せる指の合計数が決まっているので、パー（指５本）の回数が決まればチョキ（指２本）の回数が決まり、チョキの回数が決まればグー（指０本）の回数が決まります。

とういうことで、パーの出す回数について全探索を行えば解を導くことができます。

グー、チョキ、パーを自分が g, c, p 回、コンピュータが cnt_g, cnt_c, cnt_p 回出すとき、自分がじゃんけんに勝てる回数は最大で min (g, enemy_c) + min (c, enemy_p) + min (p, enemy_g) 回となります。

ただし次の２点に関して注意が必要です。

🔹 グーを出す回数がマイナスになっていない
🔹 指の本数が $ M $ 本になっている

[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
#--------- 入力例1 ----------
n,m =4, 7       # じゃんけん数、じゃんけんで出す指の数の合計
s = 'CGPC'      # コンピュータの出すじゃんけんの手
#--------- 入力例2 ----------
# n,m =5, 10      # じゃんけん数、じゃんけんで出す指の数の合計
# s = 'GPCPC'     # コンピュータの出すじゃんけんの手
#---------------------------
cnt_g, cnt_p, cnt_c = 0, 0, 0
for s1 in s:
    if s1 == 'G':
        cnt_g += 1
    elif s1 == 'P':
        cnt_p += 1
    else:
        cnt_c += 1

res = 0
for p in range(m // 5 + 1):   # グーを出せる回数分ループ
    c = (m - p * 5) // 2      # チョキの回数を求める
    g = n - p - c             # グーの回数を求める
    if g < 0:                 # グーの回数がマイナスの場合パス
        pass
    elif p * 5 + c * 2 == m:  # 指の合計本数が指定回数と同じ場合
        x = min(cnt_g, p) + min(cnt_p, c) + min(cnt_c, g)
        res = max(res, x)

print('解：', res)

[実行結果(入力例1)]

解：4

パーを１回、チョキを１回、グーを２回だすと、指の本数は全部で７本となり、最大４回 勝つことができます。

[実行結果(入力例2)]

解：3

パーを２回、チョキを０回、グーを３回だすと、指の本数は全部で１０本となり、最大３回 勝つことができます。

最安値を求める（動的計画法）

問題

くだもの屋さんで、ミカンが $ x $ 個 $ a $ 円、 $ y $ 個 $ b $ 円、 $ z $ 個 $ c $ 円で売られています。

ミカンの買い方を工夫したとき、$ n $ 個のミカンを買うために必要な金額の最小値はいくらでしょうか。

（買い方を工夫した結果、買ったミカンが $ n + 1 $ 個以上になってもよいものとします。）

[条件]
🔹 $ x < y < z $
🔹 $ 1 \leqq n,x,y,z,a,b,c \leqq 1000 $

解法・ソースコード

memo[n] をちょうど $ n $ 個のミカンを買うのに必要な金額の最小値とすると、memo[0] ～ memo[k-1] と memo[k] の関係は memo[k] = min(memo[k - x] + a, memo[k - y] + b、memo[k - z] + c) となります。

memo を添字が大きい方から memo[k] = min(memo[k], memo[k + 1]) のように書き換えていけば、memo[n] が $ n $ 個以上のミカンを買うのに必要な金額の最小値となります。

$ n $ 個のミカンを最も安く手に入れたいときに $ n+z $ 個以上のりんごを買うのは無意味なので、memo は memo[n + z - 1] 程度まで計算しておけば大丈夫です。

[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
#--------- 入力例1 ----------
n = 9              # 買いたいミカン数
x, a = 2, 100      # ミカンの個数と金額
y, b = 3, 125      # ミカンの個数と金額
z, c = 5, 200      # ミカンの個数と金額
#--------- 入力例2 ----------
# n = 145            # 買いたいミカン数
# x, a = 12,  752    # ミカンの個数と金額
# y, b = 102, 2483   # ミカンの個数と金額
# z, c = 703, 2810   # ミカンの個数と金額
#---------------------------
# 大きな数値（デフォルト値）
INF = 999999

# メモ化テーブル
memo = {}
memo[0] = 0

for i in range(1, n + z):
    memo[i] = min(memo.get(i, INF), memo.get(i - x, INF) + a)
    memo[i] = min(memo.get(i, INF), memo.get(i - y, INF) + b)
    memo[i] = min(memo.get(i, INF), memo.get(i - z, INF) + c)

print('解：', min(v for k, v in memo.items() if k >= n))

[実行結果(入力例1)]

解： 375

3個125円のミカンを、3回分買うとトータル9個のミカンを 最小金額 375円 で買うことができます。

[実行結果(入力例2)]

解： 2810

703個2810円のミカンを、1回分買うとトータル145個のミカンを 最小金額 2810円 で買うことができます。