ハノイの塔

January 17, 2023

ハノイの塔

ハノイの塔というパズルを考えます。

ハノイの塔では、次のルールのもとにすべての円盤を移動します。

🔹大きさの異なる複数の円盤があり、小さな円盤の上に大きな円盤を積むことはできない。
🔹円盤を置ける場所は３か所あり、最初は１か所にすべて積まれている。
🔹円盤を１回に１枚ずつ移動し、すべての円盤を別の場所に移動するまでの回数を調べる。

解き方・ソースコード

$ n $ 枚の円盤を移動するの必要な最小の移動回数と、その移動手段を求める方法を考えます。

小さな円盤の上に大きな円盤は積めないので、$ n $ 枚の円盤を移動するには $ n - 1 $ 枚を移動した後に、最大の１枚を移動し、その上に $ n - 1 $ 枚を移動することになります。

円盤を置ける３か所をそれぞれ $ a,b,c $ とし、$ a $ から $ b $ に円盤を移動することを $ a $ -> $ b $ と表現します。

移動に必要なパラメータは、「円盤の残り枚数」「移動元」「移動先」「経由場所」の４つで、これらを引数とする関数を定義し、その中で移動内容を出力します。

処理する枚数は、標準入力としプログラム実行時に変えられるようにしています。

[Google Colaboratory]

# 引数 n 円盤の残り枚数
# 引数 src 移動元
# 引数 dist 移動先
# 引数 via 経由場所
def hanoi(n, src, dist, via):
    global cnt
    cnt += 1
    if n > 1:
        # n - 1枚を移動元から経由場所に移す
        hanoi(n - 1, src, via, dist)
        print(src + ' -> ' + dist)
        # n -1枚を経由場所から移動先に移す
        hanoi(n - 1, via, dist, src)
    else:
        print(src + ' -> ' + dist)

n = int(input())    # 円盤の枚数（標準入力）

cnt = 0             # 移動回数
hanoi(n, 'a', 'b', 'c')
print('解（移動回数）：', cnt)

[実行結果（円盤の枚数が3の場合）]

a -> b

a -> c

b -> c

a -> b

c -> a

c -> b

a -> b

解（移動回数）： 7

[実行結果（円盤の枚数が4の場合）]

a -> c

a -> b

c -> b

a -> c

b -> a

b -> c

a -> c

a -> b

c -> b

c -> a

b -> a

c -> b

a -> c

a -> b

c -> b

解（移動回数）： 15

マージソート

January 16, 2023

マージソート

マージソートは、ソートしたいデータが入ったリストを２つに分割することを繰り返し、すべてがバラバラになった状態から、これらのリストを統合（マージ）する方法です。

この統合する際に、そのリスト内で値が小さい順に並ぶように実装することで、全体が１つのリストになったときには全ての値がソート済みになっています。

ソースコード

マージソートを実装すると下記のようになります。

[Google Colaboratory]

lst = [13, 7, 9, 11, 5, 7, 2, 4, 15, 6]

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2    # 半分の位置を算出
    # 再帰的に分割
    left = merge_sort(lst[:mid])   # 左側を分割
    right = merge_sort(lst[mid:])  # 右側を分割
    # 統合
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0

    while (i < len(left)) and (j < len(right)):
        if left[i] <= right[j]:         # 左 ≦ 右　の場合
            result.append(left[i])      # 左側から１つ取り出して追加
            i += 1
        else:
            result.append(right[i])     # 右側から１つ取り出して追加
            j += 1
    
    # 残りをまとめて追加
    if i < len(left):
        result.extend(left[i:])         # 左側の残りを追加
    if j < len(right):
        result.extend(right[j:])        # 右側の残りを追加
    return result

print('解：', merge_sort(lst))

[実行結果]

解： [2, 5, 6, 6, 7, 6, 9, 9, 13, 15]

マージソートの特徴

マージソートの特徴として、メモリに入りきらないような大容量のデータにも使えることが挙げられます。

分割した領域のそれぞれでソートできるため、複数のディスク装置にあるデータをそれぞれでソートしておき、それを結合しながらソート済みのデータを作成することも可能です。

枝狩り

January 15, 2023

問題

都道府県からいくつかを選んで、その人口の合計が１千万人にもっと近い組み合わせとその人口を求めてください。

各都道府県の人口は、2015年（平成27年）の国勢調査に基づきます。

2015年(平成27年)国勢調査各都道府県人口 - https://www.stat.go.jp/data/kokusei/2015/kekka.html

解き方・ソースコード

単純に全ての組み合わせを調べると、各都道府県を「選ぶ」「選ばない」の２通りがあり、４７都道府県で $ 2^{47} $ 通りを調べなければなりません。

これは現実的ではありません。

そこで枝狩りという手法を使います。

枝刈りとは、探索の途中において必要な条件を満たしているかどうかをチェックすることです。

必要な条件を満たしていなければ、そこで処理を中断します。

目的の1000万人を超えた場合、それ以上追加しても近づくことはありません。

また、それまでに調べた値より1000万人とのズレが大きいときも調べる必要はありません。

そこでこれらの条件を踏まえた上で、北海道から順に「選ぶ」「選ばない」のパターンを枝狩りしながら再帰的に探索します。

ズレを求めるには、1000万人との差の絶対値(abs関数)を使います。

[Google Colaboratory]

# 近づける値
goal = 10000000
# 各都道府県の人口（北海道から沖縄まで）
pref = [ 5381733, 1308265, 1279594, 2333899, 1023119, 1123891, 1914039, 2916976,
        1974255, 1973115, 7266534, 6222666, 13515271, 9126214, 2304264, 1066328,
        1154008, 786740, 834930, 2098804, 2031903, 3700305, 7483128, 1815865,
        1412916, 2610353, 8839469, 5534800, 1364316, 963579, 573441, 694352,
        1921525, 2843990, 1404729, 755733, 976263, 1385262, 728276, 5101556,
        832832, 1377187, 1786170, 1166338, 1104069, 1648177, 1433566 ]

min_total = 0
def search(total, pos):
    global min_total
    if pos >= len(pref):    # 人口データ探索終了
        return
    if total < goal:        # 枝狩り① 目標人口数を超えていない場合
        if abs(goal - (total + pref[pos])) < abs(goal - min_total): # 枝狩り② ズレが少ない場合
            min_total = total + pref[pos]                           # 合計値を更新
        search(total + pref[pos], pos + 1)      # 選ぶ場合（その都道府県の人口を足す）
        search(total, pos + 1)                  # 選ばない場合（その都道府県の人口を足さない）

search(0, 0)
print('解：', min_total)

[実行結果]

解： 10000000

青森県、宮城県、福井県、岐阜県、鳥取県、徳島県、佐賀県、長崎県の人口を合計するとちょうど10000000人になります。

値渡しと参照渡し

January 14, 2023

問題１

次のプログラムを実行すると、どのような出力になるでしょうか。

[Google Colaboratory]

x = 10
def calc(x):
    x += 20
    return x

print(x)
print(calc(x))
print(x)

解説１

関数calc内で変数xに加算していますが、グローバル宣言されていないため、ローカル変数として処理されます。

引数としてxが指定されているため、呼び出された時点でのxの値が使われ、その値に20を加算して返します。

最初のxは初期設定された10が出力され、次のcalc(x)では引数の10に20を加算した30が出力されます。

最後のxは関数calcによって変更されることはないため、初期設定された10がそのまま出力されます。

[実行結果１]

問題２

次のプログラムを実行すると、どのような出力になるでしょうか。

[Google Colaboratory]

a = [10]
def calc(a):
    a[0] += 20
    return a

print(a)
print(calc(a))
print(a)

解説２

関数calc内では、引数で渡された変数aのリストにおける先頭の要素の値に20を加算して返しています。

引数としてリストが渡された場合は、参照渡しであるためそのリストの内容を書き換えます。

最初のaは初期設定されたリスト[10]が出力され、次のcalc(a)では引数のリストにおいて先頭の要素に20を加算したリスト[30]が出力されます。

最後のaは関数calcによって変更されているため、変更されたリスト[30]が出力されます。

[実行結果２]

[10]

[30]

[30]

問題３/span>

次のプログラムを実行すると、どのような出力になるでしょうか。

[Google Colaboratory]

a = [10]
def calc(a):
    a = [20]
    return a
     
print(a)
print(calc(a))
print(a)

解説３

関数calc内では、引数で渡された変数aのリストを書き換えて返しています。

引数としてリストが渡された場合は、参照渡しですがその内容を書き換えているだけであり元のリストは上書きされません。

最初のaは初期設定されたリスト[10]が出力され、次のcalc(a)では書き換えられたリスト[20]が出力されます。

最後のaは関数calcによって変更されることはないため、初期設定されたリスト[10]が出力されます。

[実行結果３]

[10]

[20]

[10]

連続文字の数え上げ（圧縮）

January 13, 2023

問題

同じ文字が連続する場合、その文字列の出現回数を数えて圧縮するアルゴリズムを考えます。

0と1の2つの文字だけで構成される文字列を、回数だけで表現します。

（ＦＡＸの圧縮などで使われている方法です。）

たとえば、「000001111110111000000001111」を[5, 6, 1, 3, 8, 4]というリストに変換するプログラムを作成してください。

文字列は必ず「0」から始まるものとし、「1」で始まる場合はリストの先頭を0にします。

解法・ソースコード

処理中の値は0か1のためフラグで管理し、異なる値が現れたときにフラグを反転させます。

同じ値が続いている場合はカウントし、異なる値が現れた時はこれまでのカウント数をリストに追加し、新たにカウントをリセット、フラグを反転します。

[Google Colaboratory]

data = '000000111111100111000000001111'

flg = 0
count = 0
result = []
for i in data:
    if int(i) == flg:
        count += 1
    else:
        result.append(count)
        count = 1
        flg = 1 - flg

result.append(count)
print(result)

[実行結果]

[5, 6, 1, 3, 8, 4]

弾性衝突

January 12, 2023

問題

$ N $ 個の半径 $ R $ センチメートルのボールを使った次のような実験を行います。

上空 $ H $ メートルのところに筒を設置し、ボールを縦にいれます。

（下から $ i $ 番目のボールはその下端が $ H + 2Ri $ にあります。）

実験開始と同時に一番下のボールを落下させ、以後一秒ごとに１つずつボールを落下させます。

空気抵抗などはなく、床やほかのボールとは弾性衝突をします。

この実験の開始後、$ T $ 秒経過時点での各ボールの下端の高さを求めてください。

ただし、重加速度は $ g = 10m/s^2 $ とします。

[条件]

🔹$ 1 \leqq n \leqq 100 $
🔹$ 1 \leqq h \leqq 10000 $
🔹$ 1 \leqq r \leqq 100 $
🔹$ 1 \leqq t \leqq 10000 $

解法・ソースコード

まずは、ボールが１つだけの場合を考えます。

これはただの物理の問題となり、高さ $ H $ から落下するのにかかる時間は下記の通りです。

$$ t = \sqrt{\frac{2H}{g}} $$

したがって、時刻 $ T $ での位置は $ kt \leqq T $ となる最大の $ k $ に対して次のようになります。

🔹kが偶数の場合：　$ y = H - {\frac{1}{2}}g(T - kt)^2 $

🔹kが奇数の場合：　$ y = H - {\frac{1}{2}}g(kt + t - T)^2 $

次にボールが複数の場合を考えます。

半径 $ R $ が0と仮定します。全てのボールを同一視すると、ボール同士の衝突を無視して全てすり抜けたと見なすことができます。

衝突によってボールの順序関係は変化しないので、衝突を無視して計算した後で座標をソートすることにより、各ボールの最終的な位置を求めることができます。

また半径 $ R $ が0より大きい場合は、最終的な座標に $ 2Ri $ を足すだけとなります。

[Google Colaboratory]

#--------- 入力例1 ----------
n = 1       # ボールの個数
h = 10      # ボールの高さ（メートル）
r = 10      # 半径（メートル）
t = 100     # 経過時間（秒）
#--------- 入力例2 ----------
# n = 2       # ボールの個数
# h = 10      # ボールの高さ（メートル）
# r = 10      # 半径（メートル）
# t = 100     # 経過時間（秒）
#----------------------------
import math
g = 10.0    # 重加速度

# 時刻 T でのボールの位置
def calc(t):
    if t < 0:
        return h
    t1 = math.sqrt(2 * h / g)
    k = int(t / t1)
    if k % 2 == 0:
        d = t - k * t1
        return h - g * d * d / 2
    else:
        d = k * t1 + t1 - t
        return h - g * d * d / 2

# 各ボールごとの最終位置を算出する
lst = [calc(t - i) for i in range(n)]

for x in sorted(lst):
    print('{:.2f}'.format(x), end=' ')
print()

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

4.95

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

4.95 10.00

最短経路（幅優先探索）

January 11, 2023

問題

$ 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]

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

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

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

ペアリング（文字列連結）

January 10, 2023

問題

$ 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]

#--------- 入力例 -----------
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))

[実行結果]

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

コインゲーム（動的計画法）

January 9, 2023

問題

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 ----------
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の勝ち

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

January 8, 2023

帰りがけの逆順

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

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

[Google Colaboratory]

# 木構造を表すデータ
#  キー：ノード番号
#  値：ノードにぶら下がっているノード
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)