問題

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

問題

文字列 $ 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

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