問題

小さい順に並べられている要素数 $ N $ の配列 $ A = [A_1, A_2, …, A_N] $ があります。

要素 $ X $ は配列 $ A $ の何番目に存在するかを求めて下さい。

この問題は全探索でも解くことができますが、今回は二分探索を使って実装して下さい。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_1 < A_2 < … < A_N \leqq 10^9 $
🔹探す整数 $ X $ は $ A_1,A_2,…,A_N $ のいずれかである

解き方・ソースコード

二分探索では、探索範囲の左側を $ L $ 番目、右端を $ R $ 番目とするとき、次のような処理によって探索範囲を半分に絞っていきます。

🔹$ M=(L+R)/2 $ とする（割り切れない場合は切り捨てる）
🔹$ X < A_M $ の場合：探索範囲を左半分にする（$ R $ の値を $ M - 1 $ にする）
🔹$ X = A_M $ の場合：答えは $ M $ である
🔹$ X > A_M $ の場合：探索範囲を右半分にする（$ L $ の値を $ M + 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

#--------- 入力例１ ---------
N = 15      # 要素数
X = 47      # 探す要素
A = [8, 13, 17, 19, 24, 27, 33, 37, 41, 43, 47, 53, 59, 61, 68]
#--------- 入力例２ ---------
# N = 10      # 要素数
# X = 80      # 探す要素
# A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
#----------------------------
# 整数 x が何番目に存在するかを返す関数
def search(x, A):
    L = 0
    R = N - 1
    while L <= R:
        M = (L + R) // 2
        if x < A[M]:
            print('求める要素{}は、要素{}({}番目)より小さい'.format(x, A[M], M))
            R = M - 1
        if x == A[M]:
            print('求める要素{}は、要素{}({}番目)と同じ'.format(x, A[M], M))
            return M
        if x > A[M]:
            print('求める要素{}は、要素{}({}番目)より大きい'.format(x, A[M], M))
            L = M + 1
    return - 1 # 整数 x が存在しない（注：この問題の制約で -1 が返されることはない）

# 二分探索を行う
Answer = search(X, A)
print('解：', Answer + 1)  # 配列が 0 番目から始まるので、答えに 1 を足す

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

求める要素47は、要素37(7番目)より大きい

求める要素47は、要素53(11番目)より小さい

求める要素47は、要素43(9番目)より大きい

求める要素47は、要素47(10番目)と同じ

解： 11

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

求める要素80は、要素50(4番目)より大きい

求める要素80は、要素80(7番目)と同じ

解： 8

二分探索では１回の判定で探索範囲が半分になるので、配列の長さを $ N $ とするとき、$ \log_2 N $ の比較を行うことになります。

つまり計算量は $ O(\log N) $ となります。

問題

白・青・赤の３枚のカードがあります。

それぞれのカードに $ 1 $ 以上 $ N $ 以下の整数を書きます。

３枚のカードの合計を $ K $ 以下にするような書き方は何通りあるか求めてください。

[制約]
🔹$ 1 \leqq N \leqq 3000 $
🔹$ 3 \leqq K \leqq 9000 $

解き方・ソースコード

この問題を解く方法として３枚のカードの書き方を全探索することが考えられます。

ただしこの方法だと計算量が $ O(N^3) $ となり制約の上限 $ N=3000 $ の場合、270億通りを調べる必要があり計算にとても時間がかかってしまいます。

そこで計算量を減らすために２枚のカードが決まれば残りの１枚が決まるという方法をとります。

🔹白色のカードに書き込む整数を $ x $ とする。
🔹青色のカードに書き込む整数を $ y $ とする。
🔹赤色のカードに書き込む数字は $ K - x - y $ となる。

この方法ですと３枚全部ではなく２枚の書き方のみを全探索するという解法が成り立ちます。

計算量は $ O(N^2) $ であり、十分に実行が可能です。

[Google Colaboratory]

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

#--------- 入力例1 ---------
N = 3   # カードに記入できる数字の最大値
K = 6   # 合計値
#--------- 入力例2 ---------
# N = 3000   # カードに記入できる数字の最大値
# K = 4000   # 合計値
#---------------------------
Answer = 0
# 全探索
for x in range(1, N + 1):
    for y in range(1, N + 1):
        z = K - x - y
        if z >= 1 and z <= N:
            Answer += 1

# 出力
print('解：', Answer)

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

解： 7

合計を6にする方法は次の7種類あります。

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

解： 6498498

問題

$ N $ 個の品物があり、それぞれ $ 1 $ から $ N $ までの番号が付けれらています。

品物 $ i $ の重さは整数値 $ w_i $ であり、価値は整数値 $ v_i $ です。

いくつかの品物を選んで持ち帰りたいのですが、品物を入れるナップサックには容量制限があり、重さの合計が $ W $ 以下になるようにする必要があります。

価値の合計としてあり得る最大値はいくらになるでしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100 $
🔹$ 1 \leqq W_i \leqq 100000 $
🔹$ 1 \leqq w_i \leqq W $
🔹$ 1 \leqq v_i \leqq 10^9 $

解き方・ソースコード

この問題は次の二次元配列に対して、動的計画法を適用して解くことができます。

🔹$ dp[i][j] $ ：品物１，２，…，$ N $ の中から、重さの合計が $ j $ となるように選ぶ。
　このとき、合計価値としてあり得る最大値はいくつになるか。

まず、$ i = 0 $の場合は、何も選ぶことができませんので重さや価値の合計は必ず $ 0 $ になります。

$ dp[0][0] = 0 $ とし、他の値については十分に大きなマイナスの値 $ -10^{15} $ を設定しておきます。

次に、$ i \geqq 1 $ の場合は、$ dp[i][j] $ の状態になる方法、つまり品物 $ i $ までの中から重さの合計が $ j $ になるように選ぶ方法として以下の２つだけが考えられます。

🔹方法Ａ：品物 $ i - 1 $ の時点で合計が $ j $ であり、品物 $ i $ を選ばない。
　　　➡　$ dp[i-1][j] $
🔹方法Ｂ：品物 $ i - 1 $ の時点で合計が $ j - w_i $ であり、品物 $ i $ を選ぶ。
　　　➡　$ dp[i-1][j-w_i] + v_i $

つまり $ dp[i][j] $ の値は、$ dp[i-1][j] $ と $ dp[i-1][j-w_i] + v_i $ のうち大きい方を選択します。

[Google Colaboratory]

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

#--------- 入力例 ----------
N = 4                       # 品物の数
W = 7                       # ナップサックに入れられる最大重量
w = [None, 3,  3,  5,  1]   # 各品物の重さ
v = [None, 13, 17, 29, 10]  # 各品物の価値
#---------------------------
# 動的計画法
dp = [[ -10 ** 15 ] * (W + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):       # 品物ごとにループ
    for j in range(0, W + 1):   # 重さごとにループ
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        if j >= w[i]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

# 出力
print('解：', max(dp[N]))

注意が必要なのは、重さの合計がちょうど $ W $ のとき価値が最大になるとは限らないことです。

求める答えは $ dp[N][0], dp[N][1], …, dp[N][W] $ の最大値となります。

[実行結果]

解： 40

品物１、品物２，品物４を選んだ場合、重さの合計は[3 + 3 + 1 = 7]で価値の合計は[13 + 17 + 10 = 40]となりこれが価値の最大値となります。

問題

$ N $ 枚のカードが一列に並べられており、左から $ i $ 番目のカード（カード $ i $ とする）には整数 $ A_i $ が書かれています。

カードの中から何枚かを選んで、書かれた整数の合計が $ S $ となるときのカードの組み合わせを出力してください。

[制約]
🔹$ 1 \leqq N \leqq 60 $
🔹$ 1 \leqq S \leqq 10000 $
🔹$ 1 \leqq A_i \leqq 10000 $

解き方・ソースコード

前回記事では、カードの合計値が $ S $ となるかどうかを判定しました。

今回はカードの合計値 $ S $ になる組み合わせがある場合、そのカードの組み合わせを出力します。

まずは、前回記事と同様に動的計画法を使って合計が $ S $ になるかどうかをチェックします。

この時に作成した $ dp $ を合計値 $ S $ から $ 0 $ にさかのぼって確認すると、選ぶべきカードを復元することができます。

カードを選ぶかどうかは、以下の２条件を確認することで判断します。

　🔹$ dp[x - 1][合計値] = True $ の場合：カード $ x $ を選ばない
　🔹上記以外：カード $ x $ を選ぶ（カードを選んだら、カードの数字を合計値から差し引き、カード $ x $ を保管しておく）

　
[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

#--------- 入力例 ----------
N = 5
S = 7
A = [2, 1, 3, 8, 2]
#---------------------------
# 動的計画法（i=0）
dp = [[ None ] * (S + 1) for i in range(N + 1)]
dp[0][0] = True
for i in range(1, S + 1):
    dp[0][i] = False

# 動的計画法（i=1）
for i in range(1, N + 1):       # カードの枚数分ループ
    for j in range(0, S + 1):   # 0から合計値Sまでループ
        if dp[i - 1][j] or (j - A[i - 1] > -1 and dp[i - 1][j -A[i - 1]]):
            dp[i][j] = True
        else:
            dp[i][j] = False

# 答えの復元
Answer = []
Place = S
for i in reversed(range(1, N + 1)): # 合計値Sから、1までループ（今回の場合:5,4,3,2,1）
    if dp[i - 1][Place]:
        Place = Place - 0           # カード i を選ばない
    else:
        Place = Place - A[i - 1]    # カード i を選ぶ
        Answer.append(i)

# 答えを出力（インデックスよりカードに書かれた数字を出力）
print('解：', ' '.join(str(A[i - 1]) for i in reversed(Answer)))

[実行結果

解： 2 3 2

[2, 3, 2]という数字の書かれたカードの組み合わせを選ぶと、合計が7になることが分かりました😊

問題

$ N $ 枚のカードが一列に並べられており、左から $ i $ 番目のカード（カード $ i $ とする）には整数 $ A_i $ が書かれています。

カードの中から何枚かを選んで、書かれた整数の合計が $ S $ となるようにする方法があるかどうかを判定してください。

[制約]
🔹$ 1 \leqq N \leqq 60 $
🔹$ 1 \leqq S \leqq 10000 $
🔹$ 1 \leqq A_i \leqq 10000 $

解き方・ソースコード

動的計画法を使うにあたり、以下のような２次元配列を用意します、

🔹$ dp[i][j]$：カード１、カード２、…、カード $ i $の中から何枚かを選び、選んだカードに書かれた整数の合計を $ j $ にすることが可能かどうか。

まず、$ i=0 $の場合は選んだカードの合計値が必ず$ 0 $になるので、$ dp[0][0] $を $ True $ に設定し、$ dp[0][1] $以降を $ False $ に設定します。

$ i \geqq 1 $の場合、$ dp[i][j] $の状態になる方法つまりカード $ i $ までの中から合計が $ j $ になるように選ぶ方法としては次の２つの方法が考えられます。

🔹方法A：カード$ i - 1 $ の時点で合計が $ j $ であり、カード $ i $ を選ばない。
🔹方法B；カード$ i - 1 $ の時点で合計が $ j - A_i $ であり、カード $ i $ を選ぶ。

方法A・方法Bのうちどちらかが可能であれば、$ dp[i][j] $ の状態にすることができます。

[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 = 3
S = 7
A = [2, 2, 3]
#--------- 入力例2 ---------
# N = 3
# S = 6
# A = [2, 2, 3]
#---------------------------
# 動的計画法（i=0）
dp = [[ None ] * (S + 1) for i in range(N + 1)]
dp[0][0] = True
for i in range(1, S + 1):
    dp[0][i] = False

# 動的計画法（i=1）
for i in range(1, N + 1):       # カードの枚数分ループ
    for j in range(0, S + 1):   # 0から合計値Sまでループ
        if dp[i - 1][j] or (j - A[i - 1] > -1 and dp[i - 1][j - A[i - 1]]):
            dp[i][j] = True
        else:
            dp[i][j] = False

print('解：', 'Yes' if dp[N][S] else 'No')

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

解： Yes

すべてのカードを選択すると[2 + 2 + 3 = 7]となり、正解はYesとなります。

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

解： No

３枚のカードをどう組み合わせても6にはならないので、正解はNoとなります。

問題

$ N $ 個の足場があり、左から $ i $ 番目の足場（足場 $ i $ とする）の高さは $ h_i $ です。

ウサギは以下の２種類の行動を繰り返すことで、足場１から足場 $ N $ に移動します。

　🔹足場 $ i - 2 $ から足場 $ i $ に、コスト $ | h_{i-2} - h_i | $ かけて移動する。
　🔹足場 $ i - 1 $ から足場 $ i $ に、コスト $ | h_{i-1} - h_i | $ かけて移動する。

足場 $ 1 $ から足場 $ N $ に移動するのに、最短コストのルートを１つ出力して下さい。

解き方・ソースコード

前々回の記事では同じ問題の最短コストを求めましたが、今回は最短コストで移動する際のルート（経路）を求める問題となります。

この問題ではゴールから順番にスタートへの経路を考えることで解くことができます。

まずは、前々回記事と同様に動的計画法を使って最短コストを求めます。

この時に作成した $ dp $ を確認すると次のように最適解(最短コストとなるルート)を復元することができます。

　🔹$ dp[x] = dp[x - 1] + | H[x - 1] - H[x] | $ の場合：方法Aを選ぶ
　🔹$ dp[x] = dp[x - 2] + | H[x - 2] - H[x] | $ の場合：方法Bを選ぶ

なお、上の２つの条件両方を満たす場合は、方法A・方法Bどちらを選んでも構いません。

[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

#--------- 入力例 ----------
N = 6
H = [30, 10, 60, 10, 60, 50]
#---------------------------
# 配列の準備
dp = [ None ] * N

# 動的計画法
dp[0] = 0
#print('足場1までの最小コスト', dp)

dp[1] = abs(H[0] - H[1])
# print('足場2までの最小コスト', dp)

for i in range(2, N):   # 足場3以降の最小コスト
    dp[i] = min(dp[i - 1] + abs(H[i - 1] - H[i]), dp[i - 2] + abs(H[i - 2] - H[i]))
    # print('足場{}までの最小コスト'.format(i + 1), dp)

# 答えの復元
# 変数 Place は現在位置（ゴールからスタート地点へ向かう）
Answer = []
Place = N - 1
while True:
    Answer.append(Place)
    print(Answer)
    if Place == 0:
        break

    # どこから足場 Place に向かうのが最適かを求める
    if dp[Place - 1] + abs(H[Place - 1] - H[Place]) == dp[Place]:
        Place = Place - 1   # １つ前の足場に移動
    else:
        Place = Place - 2   # ２つ前の足場足場に移動

# 答えを出力(Answer[0]が足場１に対応)
print('解：', ' → '.join(str(i + 1) for i in reversed(Answer)))

[実行結果]

[5]

[5, 4]

[5, 4, 2]

[5, 4, 2, 0]

解： 1 → 3 → 5 → 6

最短コストにするためには1 → 3 → 5 → 6というルート（経路）であることが確認できました😊

問題

$ N $ 個の部屋があり、$ 1 $ から $ N $ までの番号が付けられています。

この部屋はすべて一方通行であり、通路を介して１つ先または２つ先の部屋に移動できます。

各通路における移動時間は以下の通りです。

🔹部屋 $ i - 1 $ から部屋 $ i $ に向かう通路を通るのに $ A_i $ 分 $ (2 \leqq i \leqq N) $ かかる
🔹部屋 $ i - 2 $ から部屋 $ i $ に向かう通路を通るのに $ B_i $ 分 $ (3 \leqq i \leqq N) $ かかる

部屋 $ 1 $ から部屋 $ N $ に移動するのに、最短時間のルートを１つ出力して下さい。

[制約]
🔹$ 3 \leqq n \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 100 (2 \leqq i \leqq N) $
🔹$ 1 \leqq B_i \leqq 100 (3 \leqq i \leqq N) $

解き方・ソースコード

前々回の記事では同じ問題の最短時間を求めましたが、今回は最短時間で移動する際のルート（経路）を求める問題となります。

この問題ではゴールから順番にスタートへの経路を考えることで解くことができます。

まずは、前々回記事と同様に動的計画法を使って最短時間を求めます。

この時に作成した $ dp $ を確認すると次のように最適解(最短時間となるルート)を求めることができます。

　🔹$ dp[x] = dp[x-1] + A_x $ の場合：方法Aを選ぶ
　🔹$ dp[x] = dp[x-2] + B_x $ の場合：方法Bを選ぶ

なお、上の２つの条件両方を満たす場合は、方法A・方法Bどちらを選んでも構いません。

最後に、復元した経路を逆順に並べ替えることにより、最短ルートを求めます。

[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

#--------- 入力例 ----------
N = 5
A = [2, 4, 1, 3]
B = [5, 3, 7]
#---------------------------
# 動的計画法
dp = [None] * (N + 1)
dp[1] = 0
dp[2] = A[0]
for i in range(3, N + 1):
    dp[i] = min(dp[i - 1] + A[i - 2], dp[i - 2] + B[i - 3])

# 答えの復元
# 変数 Place は現在位置（ゴールからスタート地点へ向かう）
Answer = []
Place = N
while True:
    Answer.append(Place)
    print(Answer)
    if Place == 1:
        break

    # どこから部屋 Place に向かうのが最適かを求める
    if dp[Place - 1] + A[Place - 2] == dp[Place]:
        Place = Place - 1   # １つ前の部屋に移動
    else:
        Place = Place - 2   # ２つ前の部屋に移動

# 答えを出力
print('解：', ' → '.join(str(i) for i in reversed(Answer)))

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

[5]

[5, 4]

[5, 4, 2]

[5, 4, 2, 1]

解： 1 → 2 → 4 → 5

最短時間にするためには1 → 2 → 4 → 5という経路であることが確認できました😊

問題

$ N $ 個の足場があり、左から $ i $ 番目の足場（足場 $ i $ とする）の高さは $ h_i $ です。

ウサギは以下の２種類の行動を繰り返すことで、足場１から足場 $ N $ に移動します。

　🔹足場 $ i - 2 $ から足場 $ i $ に、コスト $ | h_{i-2} - h_i | $ かけて移動する。
　🔹足場 $ i - 1 $ から足場 $ i $ に、コスト $ | h_{i-1} - h_i | $ かけて移動する。

移動にかかる合計コストの最小値を出力して下さい。

解き方・ソースコード

この問題は、足場１から足場 $ i $ までの最小コストを $ dp[i-1] $ とし、$ dp[0] → dp[1] → ･･･ → dp[N-1] $ の順に１つずつ計算すると、答えを出すことができます。

配列 $ dp $ の計算方法としては、まず足場１から足場１までは移動する必要がないので、$ dp[0] = 0 $ となります。

次に足場１から足場２まで行くには直接移動するしかないので、$ dp[1] = h_0 - h_1 $ となります。

$ dp[2] $ 以降は最後の行動で場合分けをして考えます。足場 $ i $ まで移動するには、次の２つが考えられます。

　（方法１）足場 $ i - 1 $ まで移動した後、１つ隣りの足場 $ i $ に行く。
　（方法２）足場 $ i - 2 $ まで移動した後、２つ隣りの足場 $ i $ に行く。

ここで、方法１を選んだ時の合計コストは $ dp[i - 1] + abs(H[i - 1] - H[i]) $ であり、方法２を選んだ時の合計コストは $ dp[i - 2] + abs(H[i - 2] - H[i]) $ です。

コストの少ないほうを求める問題なので、$ dp[i] $ の値は次式のように表すことができます。

$$ dp[i] = min(dp[i-1] + abs(H[i - 1] - H[i]), dp[i-2] + abs(H[i - 2] - H[i])) $$

上記の内容を踏まえてコーディングすると下記のようなソースコードになります。

[Google Colaboratory]

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

#--------- 入力例 ----------
N = 6
H = [30, 10, 60, 10, 60, 50]
#---------------------------
# 配列の準備
dp = [ None ] * N

# 動的計画法
dp[0] = 0
print('足場1までの最小コスト', dp)

dp[1] = abs(H[0] - H[1])
print('足場2までの最小コスト', dp)

for i in range(2, N):   # 足場3以降の最小コスト
    dp[i] = min(dp[i - 1] + abs(H[i - 1] - H[i]), dp[i - 2] + abs(H[i - 2] - H[i]))
    print('足場{}までの最小コスト'.format(i + 1), dp)

# 出力
print('解：', dp[N - 1])

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

足場1までの最小コスト [0, None, None, None, None, None]

足場2までの最小コスト [0, 20, None, None, None, None]

足場3までの最小コスト [0, 20, 30, None, None, None]

足場4までの最小コスト [0, 20, 30, 20, None, None]

足場5までの最小コスト [0, 20, 30, 20, 30, None]

足場6までの最小コスト [0, 20, 30, 20, 30, 40]

解： 40

足場１→足場３→足場５→足場６と移動すると最小コスト40で移動することができます。

問題

$ N $ 個の部屋があり、$ 1 $ から $ N $ までの番号が付けられています。

この部屋はすべて一方通行であり、通路を介して１つ先または２つ先の部屋に移動できます。

各通路における移動時間は以下の通りです。

🔹部屋 $ i - 1 $ から部屋 $ i $ に向かう通路を通るのに $ A_i $ 分 $ (2 \leqq i \leqq N) $ かかる
🔹部屋 $ i - 2 $ から部屋 $ i $ に向かう通路を通るのに $ B_i $ 分 $ (3 \leqq i \leqq N) $ かかる

部屋 $ 1 $ から部屋 $ N $ に移動するのに、最短何分かかるでしょうか。

[制約]
🔹$ 3 \leqq n \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 100　 (2 \leqq i \leqq N) $
🔹$ 1 \leqq B_i \leqq 100　 (3 \leqq i \leqq N) $

解き方・ソースコード

この問題は、部屋１から部屋 $ i $ までの最短時間を $ dp[i] $ とし、$ dp[1] → dp[2] → ･･･ → dp[N] $ の順に１つずつ計算すると、答えを出すことができます。

配列 $ dp $ の計算方法としては、まず部屋１から部屋１までは移動する必要がないので、$ dp[1] = 0 $ となります。

次に部屋１から部屋２まで行くには直接移動するしかないので、$ dp[2] = A_2 $ となります。

$ dp[3] $ 以降は最後の行動で場合分けをして考えます。部屋 $ i $ まで移動するには、次の２つが考えられます。

　（方法１）部屋 $ i - 1 $ まで移動した後、１本の通路を通って部屋 $ i $ に行く。
　（方法２）部屋 $ i - 2 $ まで移動した後、１本の通路を通って部屋 $ i $ に行く。

ここで、方法１を選んだ時の合計時間は $ dp[i - 1] $ 分であり、方法２を選んだ時の合計時間は $ dp[i - 2] $ 分です。

時間の短いほうを求める問題なので、$ dp[i] $ の値は次式のように表すことができます。

$$ dp[i] = min(dp[i-1] + A_i, dp[i-2] + B_i) $$

上記の内容を踏まえてコーディングすると下記のようなソースコードになります。

A, B が 0 番目から始まっていることに注意して下さい。

[Google Colaboratory]

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

#--------- 入力例 ----------
N = 5
A = [2, 4, 1, 3]
B = [5, 3, 7]
#---------------------------
# 動的計画法
dp = [ None ] * (N + 1)

dp[1] = 0       # 部屋1までの最短時間
print('部屋1番目までの最短時間', dp)

dp[2] = A[0]    # 部屋2までの最短時間
print('部屋2番目までの最短時間', dp)

for i in range(3, N + 1):
    dp[i] = min(dp[i - 1] + A[i - 2], dp[i - 2] + B[i - 3])
    print('部屋{}番目までの最短時間'.format(i), dp)
# 出力
print('解：', dp[N])

[実行結果]

部屋1番目までの最短時間 [None, 0, None, None, None, None]

部屋2番目までの最短時間 [None, 0, 2, None, None, None]

部屋3番目までの最短時間 [None, 0, 2, 5, None, None]

部屋4番目までの最短時間 [None, 0, 2, 5, 5, None]

部屋5番目までの最短時間 [None, 0, 2, 5, 5, 8]

解： 8

部屋1から部屋5までの最短時間が8分であることを導き出すことができました😊

問題

黒板に0という整数が書かれています。

その整数に対して $ N $ 回の操作を行います。

$ i $回目の操作は文字$ T_i $と整数$ A_i $で表され、その操作内容は次の３種類です。

🔹$ T_i = + $ のとき：$ A_i $ を足す。
🔹$ T_i = - $ のとき：$ A_i $ を引く。
🔹$ T_i = * $ のとき：$ A_i $ を掛ける。

各操作が終わった後について、黒板に書かれた整数を10000で割った余りを出力するプログラムを作成して下さい。

[制約]
🔹$ 1 \leqq n \leqq 100000 $
🔹$ 1 \leqq A_i \leqq 100 $
🔹黒板に書かれる整数は常に0以上

解き方・ソースコード

この問題はオーバーフローを防ぐために操作が行われるたびに余りをとるということがポイントとなります。

ただし引き算を行う場合、計算結果がマイナスになってしまう可能性がるため、計算の途中で0を下回った場合10000を足す必要があります。

[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

#--------- 入力例1 ----------
N = 4
A = ['+ 59',
     '+ 41',
     '* 100',
     '- 1']
#----------------------------
# 現在の黒板の数
Answer = 0
for a in A:
    ss = a.split()
    if ss[0] == '+':
        Answer += int(ss[1])
    elif ss[0] == '-':
        Answer -= int(ss[1])
    elif ss[0] == '*':
        Answer *= int(ss[1])

    # 引き算で答えが 0 未満になった場合
    if Answer < 0:
        Answer += 10000

    # 余りをとる
    Answer %= 10000
    print(Answer)

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

59
100
0
9999

解が非常に大きくなる問題では、余りを出力するということがよくあるので上記の手法を覚えておくことはとても有益です。