問題

$ H \times W $ の長方形状のグリッドがあり、各マスは白か黒に塗られています。

上から $ i $ 番目、左から $ j $ 番目のマスを $ (i, j) $ と表すことにします。

左上のマス $ (0,0) $ と右下のマス $ (H -1, W - 1) $ は白色です。

このグリッドの入力データは、$ H $ 個の長さ $ W $ の文字列 $ S_0, S_1, …, S_{H-1} $ として与えられます。

文字列 $ S_i $ の $ j $ 番目の文字は、マス $ (i,j) $ が白色の時は ‘,’(カンマ) であり、黒色の時は ‘#’(シャープ) です。

マス $ (0,0) $ からマス $ (H-1, W-1) $ まで白色マスのみを辿って行くことができる状態を保ちつつ、白色マスを黒色マスに塗り替える場合、黒く塗れるマスの最大個数はいくつになるでしょうか。

解法・ソースコード

この問題は、マス(0, 0)からマス(H - 1, W -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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

from queue import Queue
#--------- 入力例 -----------
s = ['.....#',
     '####..',
     '......',
     '#.####',
     '......']
#----------------------------
h = len(s)      # グリッドの高さ
w = len(s[0])   # グリッドの横幅

# マス(x,y)を表すペア
que = Queue()
# dist[x,y]は、マス(x,y)への最短経路長
dist = [[-1] * w for _ in range(h)]

# 幅優先探索の初期条件
que.put((0, 0))  # スタート位置
dist[0][0] = 0

# 幅優先探索
while que.empty() == False:
    # キューから要素を取り出す
    qx, qy = que.get()

    # 上下左右への移動を試す
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        x, y = qx + dx, qy + dy
        # 配列外の参照の場合
        if x < 0 or x >= h or y < 0 or y >= w:
            continue
        # 白マスの場合 かつ マス(x, y)が未探索の場合
        if s[x][y] == '.' and dist[x][y] < 0:
            # マス(x, y)をキューに追加して、最短経路長を更新
            que.put((x, y))
            dist[x][y] = dist[qx][qy] + 1

# 白マスの数をカウント
cnt_white = sum(line.count('.') for line in s)

print('解：', cnt_white - dist[h - 1][w - 1] - 1)

[実行結果]

解： 4

次のように４マスを黒く塗り替えることができ、右上から左下への最短経路はそのまま残すことができます。

(変更前)　　（変更後）
.....#　　　.....#
####..　　　####.#
......　➡　#....#
#.####　　　#.####
......　　　#.....

問題

$ N $ 個の文字列 $ s_0, s_1, …, s_{N-1} $ が与えられます。

これらの文字列を好きな順序で並べた後、連結して１つの文字列を作ります。

作った文字列に“AB”が最大で何個含まれるかを求めて下さい。

[条件]
🔹文字列の数 $ N $ は $ 1 $ 以上 $ 10^4 $ 以下の整数
🔹$ s_i $ は英大文字
🔹$ s_i $ の長さは $ 2 $ 以上 $ 10 $ 以下

解法・ソースコード

この問題は連結部の“AB”の個数を最大化する問題と言えます。

$ N $ 個の文字列 $ s_0, s_1, …, s_{N-1} $ は次の４パターンに分類できます。

🔹パターン１：B***A（左端が”B”で、右端が”A”）
🔹パターン２：****A（左端が”B”ではなく、右端が”A”）
🔹パターン３：B****（左端が”B”で、右端が”A”ではない）
🔹パターン４：*****（左端が”B”ではなく、右端も”A”ではない）

パターン４はほかの文字列と連結して“AB”となることはないので無視します。

パターン１、２、３の個数をそれぞれ $ c_1, c_2, c_3 $ とします。

「理論的にこれより多く作るのは不可能である」という上界を考えます。

“A”の個数は全部で $ c_1 + c_2 $ 個であり、“B”の個数は全部で $ c_1 + c_3 $ 個です。

したがって、$ min(c_1 + c_2, c_1 + c_3) = c_1 + min(c_2, c_3) $ よりも多くの“AB”を作ることは絶対できません。

$ c_2 = c_3 = 0 $ の場合、パターン１同士が連結した部分でしか “AB”をつくれませんので、答えは $ max(c_1 - 1, 0) $ となります。

また、$ c_2 $ と $ c_3 $ のうち少なくとも一方が $ 1 $ 以上である場合には、$ c_1 + min(c_2, c_3) $ 個の“AB”を作ることができます。

上記を踏まえると以下の手順で問題を解くことができます。

🔹各文字列 $ s_0, s_1, …, s_N-1 $ にすでに含まれている“AB”の個数の総和を $ T $ とする。
🔹各文字列を４パターンに分類する。（ $ c_1,c_2,c_3 $ の定義は前述の通り）
🔹$ c_2 = c_3 = 0 $ の場合、$ T + max(c_1 - 1, 0) $ 個の“AB”ができる。
🔹$ c_2 $ と $ c_3 $ いずれかが $ 1 $ 以上の場合、$ T + c_1 + min(c_2, c_3) $ 個の“AB”ができる。

[Google Colaboratory]

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

#--------- 入力例 -----------
n = 3
lst = ['ABCA', 'XBAZ', 'BAD']
#----------------------------
t = 0                   # それぞれの文字列に含まれる"AB"の個数の総和（連結前）
c1, c2, c3 = 0, 0, 0    # パターン１、２，３の個数

for s in lst:
    # 各文字列に含まれる"AB"の個数
    t += s.count("AB")
    if s.startswith('B') and s.endswith('A'):   # パターン１の個数
        c1 += 1
    elif s.endswith('A'):                       # パターン２の個数
        c2 += 1
    elif s.startswith('B'):                     # パターン３の個数
        c3 += 1

# パターン２とパターン３の数に応じて結果を出力
if c2 == 0 and c3 == 0:
    print(t + max(c1 -1, 0))
else:
    print(t + c1 + min(c2, c3)) 

[実行結果]

2

“ABCA”、”BAD”、”XBAZ”の順に結合して、”ABCABADXBAZ”を作ると、“AB”が２つできることが確認できます。

問題

NancyとTomが次のようなゲームをします。

$ k $ 個の数字 $ a_1, a_2, …, a_k $ が決まっています。

最初に $ x $ 枚のコインがあって、NancyとTomが交互にコインを取っていきます。

一度に取るコインの枚数は $ a_1, a_2, …, a_k $ のいずれでないといけません。

最後のコインを取ったほうが勝ちとなります。

最初はNancyの番で、両者とも最善を尽くすとした場合、どちらが勝つでしょうか。

（$ a_1, a_2, …, a_k $ の中には必ず $ 1 $ が含まれています。）

[制約]

🔹$ 1 \leqq x \leqq 10000 $
🔹$ 1 \leqq k \leqq 100 $
🔹$ 1 \leqq a_i \leqq x $

解法・ソースコード

$ j $ 枚のコインがある状態で順番が回ってきたときに勝てるのかどうかを考えます。

🔹最後のコインをとったら勝ちというのは0枚で自分にまわってきたら負けと考えても同じです。
　つまり、$ j=0 $ ならば負けとなります。

🔹ある $ i　(1 \leqq i \leqq k) $ に対し、$ j - a_i $ 枚が負けならば、$ j $ 枚は勝ち
　（ $ j $ 枚で回ってきたら、$ a_i $ 枚とれば相手は負ける ➡ 自分が勝つ）

🔹すべての $ i　(1 \leqq i \leqq k) $ に対し、$ j - a_i $ 枚が勝ちならば、$ j $ 枚は負け
　（どのような取り方をしても、必ず相手が勝つ ➡ 自分はどうやっても負ける）

上記をもとに、動的計画法を使って小さい $ j $ から順に勝ち負けを計算していき、$ x $ 枚が勝ちであるか負けてであるかをみれば問題が解けることになります。

[Google Colaboratory]

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

#--------- 入力例1 ----------
x = 9
coins = [1, 4]
#--------- 入力例2 ----------
# x = 10
# coins = [1, 4]
#----------------------------
k = len(coins)      # 選べるコイン数のパターン数

# 動的計画法用の変数
#   キー：コイン数
#   バリュー：Nancyの勝ち(True)、Tomの勝ち(False)
memo = {}

for j in range(1, x + 1):   # コイン数分ループ
    memo[j] = False
    for coin in coins:      # 選べるコインごとのループ
        res = coin <= j and memo.get(j - coin, False) == False
        memo[j] = memo[j] or res    # 論理和（どちらかがTrueだったらTrue）
print(memo)
print('解：', 'Nancyの勝ち' if memo[x] else 'Tomの勝ち')

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

{1: True, 2: False, 3: True, 4: True, 5: False, 6: True, 7: False, 8: True, 9: True}

解： Nancyの勝ち

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

{1: True, 2: False, 3: True, 4: True, 5: False, 6: True, 7: False, 8: True, 9: True, 10: False}

解： Tomの勝ち

帰りがけの逆順

深さ優先探索は、再帰を使わずにループで実装することもできます。

次のサンプルコードでは、帰りがけの逆順で処理します。

[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:[]}

data = [0]
while len(data):
    pos = data.pop()    # 末尾から取り出し
    print(pos, end=' ')
    for i in tree[pos]:
        data.append(i)

[木構造]

[実行結果]

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

帰りがけ順では、深いノードが出力されたあとにその親ノードが順に出力され、最後にノード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
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

石の山が $ 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ライブラリを使うと、素数を簡単に扱うことができます。

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