値渡しと参照渡し

問題1

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
x = 10
def calc(x):
x += 20
return x

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

解説1

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

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

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

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

[実行結果1]

10

30

10

問題2

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
a = [10]
def calc(a):
a[0] += 20
return a

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

解説2

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

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

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

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

[実行結果2]

[10]

[30]

[30]

問題3/span>

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
a = [10]
def calc(a):
a = [20]
return a

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

解説3

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

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

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

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

[実行結果3]

[10]

[20]

[10]

連続文字の数え上げ(圧縮)

問題

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

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

(FAXの圧縮などで使われている方法です。)

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

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

解法・ソースコード

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

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

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]

弾性衝突

問題

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

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

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

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

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

この実験の開始後、$ 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 $

解法・ソースコード

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

これはただの物理の問題となり、高さ $ 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
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
#--------- 入力例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

最短経路(幅優先探索)

問題

$ 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

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

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

ペアリング(文字列連結)

問題

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

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

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

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

解法・ソースコード

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

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

🔹パターン1:B***A(左端が”B”で、右端が”A”)
🔹パターン2:****A(左端が”B”ではなく、右端が”A”)
🔹パターン3:B****(左端が”B”で、右端が”A”ではない)
🔹パターン4:*****(左端が”B”ではなく、右端も”A”ではない)

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

パターン1、2、3の個数をそれぞれ $ 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 $ の場合、パターン1同士が連結した部分でしか “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 $ とする。
🔹各文字列を4パターンに分類する。( $ 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 # パターン1、2,3の個数

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

# パターン2とパターン3の数に応じて結果を出力
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”が2つできることが確認できます。

コインゲーム(動的計画法)

問題

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が出力されますが、帰りがけの逆順ではその逆順で出力されていることが確認できます。

深さ優先探索(通りがけ順)

深さ優先探索

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

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

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

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

ソースコード(通りがけ順)

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

[木構造]

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

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

[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: # 子ノードが2つある場合
search(tree[pos][0])
print(pos, end=' ') # 左のノードと右のノードの間に出力
search(tree[pos][1])
elif len(tree[pos]) == 1: # 子ノードが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 

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

深さ優先探索(帰りがけ順)

深さ優先探索

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

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

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

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

ソースコード(帰りがけ順)

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

[木構造]

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

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

行きがけ順と比べて、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が出力されることを確認できます。

深さ優先探索(行きがけ順)

深さ優先探索

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

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

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

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

ソースコード(行きがけ順)

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

[木構造]

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

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

[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から一番深いノードまで行って上に戻り、再度別の深いノードへ進むという順番に探索されていることが確認できます。