問題

$ N $ 個の整数があります。

整数は小さい順に $ A_1,A_2,…,A_N $ と並んでいます。

異なる２つの整数のペアを選ぶ方法は全部で $ N(N-1)/2 $ 通りありますが、その中で差が $ K $ 以下であるような選び方は何通りあるでしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq K \leqq 10^9 $
🔹$ 1 \leqq A_1 < A_2 < … < A_N \leqq 10^9 $

解き方・ソースコード

$ A_t \leqq A_i + K $ を満たす最大の $ t $ を $ R_i $ とし、$ R_i $ の値を次のように計算します。

🔹手順１　$ i = 1 $ であれば $ R_i = 1 $ から、そうでなければ $ R_i = R_{i-1} $ からスタートする。
🔹手順２　差分 $ A_{R_{i}} - A_i $ が $ K $ を超えないギリギリまで、$ R_i $ を１増やす操作を繰り返す。

求めるペアの個数は $ (R_i - i) $ 通りで、答えは次式で計算できます。

$$ (R_1 - 1) + (R_2 - 2) + … + (R_{N-1} - (N -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

#--------- 入力例 -----------
N = 7       # 整数の数
K = 10      # 差をK以下にする
A = [9, 10, 14, 20, 25, 26, 29]     # 小さい順に並んだ整数
#----------------------------
# 配列の準備（R は 0 番目から始まる）
R = [ None ] * N

# しゃくとり法
for i in range(0, N - 1):
    # スタート地点を決める
    if i == 0:
        R[i] = 0
    else:
        R[i] = R[i - 1]

    # ギリギリまで増やしていく
    while R[i] < N - 1 and A[R[i] + 1]-A[i] <= K:
        R[i] += 1
    print(R)

# 出力
Answer = 0
for i in range(0, N - 1):
    Answer += (R[i] - i)
print('解：', Answer)

このアルゴリズムは、しゃくとり虫の動きにたとえてしゃくとり法と呼ばれています。

$ R_i $ を増やす操作は合計 $ N - 1 $ しか行われないので、計算量は $ O(N) $ となります。

[実行結果]

[2, None, None, None, None, None, None]

[2, 3, None, None, None, None, None]

[2, 3, 3, None, None, None, None]

[2, 3, 3, 6, None, None, None]

[2, 3, 3, 6, 6, None, None]

[2, 3, 3, 6, 6, 6, None]

解： 11

整数のペアの差が10以下になる組み合わせは、11通りあることを導き出すことができました。

問題

正の整数 $ N $ が与えられます。

$ x^3 + x = N $ を満たす正の実数 $ x $ を求めて下さい。

ただし絶対誤差が $ 0.01 $ 以下であれば正解とします。

解き方・ソースコード

$ f(x) = x^3 + x $ は単調な増加関数です。

$ x $ が増えると $f(x) $ も増えます。

二分探索を使って、$ x $ の範囲を次第にせまくしていくことにより正の整数 $ N $ に答えを近づけていきます。

今回は実行回数を20回としていますが、許容できる誤差の範囲に応じて調整しましょう。

[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

#--------- 入力例 -----------
N = 99      # 正の整数
#----------------------------
def f(x):
    return x * x * x + x

# 二分探索
Left = 0.0
Right = 100.0
for i in range(20):
    Mid = (Left + Right) / 2
    val = f(Mid)
    print(Mid, val)

    # 探索範囲を絞る
    if val > N:
        Right = Mid     # 左半分に絞られる
    else:
        Left = Mid      # 右半分に絞られる

# 出力
print('解：', Mid)
print('x={}のときf(x)は{}'.format(Mid, f(Mid)))

[実行結果]

50.0 125050.0

25.0 15650.0

12.5 1965.625

6.25 250.390625

3.125 33.642578125

4.6875 107.684326171875

3.90625 63.510894775390625

4.296875 83.63065719604492

4.4921875 95.14340162277222

4.58984375 101.28254741430283

4.541015625 98.1804946437478

4.5654296875 99.7233574045822

4.55322265625 98.94989057502244

4.559326171875 99.33611444539565

4.5562744140625 99.1428752093725

4.55474853515625 99.04635107764648

4.553985595703125 98.99811287402898

4.5543670654296875 99.02222998759483

4.554176330566406 99.01017093377199

4.554080963134766 99.0041417796431

解： 4.554080963134766

x=4.554080963134766のときf(x)は99.0041417796431

解は4.554080963134766となりました😊

実際に計算式 $ x^3 + x = N $ に当てはめると結果は99.0041417796431となり、許容誤差の0.01以下となります。

問題

$ N $ 台のプリンターがあり、$ 1 $ から $ N $ までの番号がつけられています。

プリンター $ i $ は $ A_i $ 秒ごとに１枚印刷できます。

つまりスイッチを入れてから $ A_i $ 秒後に１枚、$ 2A_i $ 秒後にもう１枚・・・と印刷可能です。

全てのプリンターのスイッチを同時に入れたとき、$ K $ 枚目が印刷されるのは何秒後でしょうか。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq K \leqq 10^9 $
🔹$ 1 \leqq A_i \leqq 10^9 $
🔹答えは $ 10^9 $ 以下

解き方・ソースコード

この問題では、答えに対して二分探索を行うと効率的に解くことができます。

答えが１秒後から８秒後までのいずれかであると仮定してみます。

答えの候補の中央は４秒後ですので、答えが４秒以下かどうか？を考えます。

下記ソースの入力例を考えると、４秒後までに印刷される枚数は８枚であり $ K=10 $ 枚未満なので質問の答えはNoとなります。

この時点で、答えの候補が５秒後から８秒後までの範囲に絞られます。

この処理を探索範囲の左端(Left)と右端(Right)が同じになるまで繰り返します。

[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 = 4      # プリンターの数
K = 10     # 印刷したい枚数
A = [1, 2, 3, 4]
#----------------------------
# 答えがx以下かを判定し、YesであればTrue、No あればFalseを返す
def check(x, N, K, A):
    sum = 0
    for i in range(N):
        sum += x // A[i] # 「x ÷ A[i]」の小数点以下切り捨て
    print('{}秒後に印刷できる枚数は{}'.format(x, sum))
    if sum >= K:
        return True
    else:
        return False

# Left は探索範囲の左端、Right は探索範囲の右端を表す
Left = 1
Right = 10 ** 3
while Left < Right:
    Mid = (Left + Right) // 2
    Answer = check(Mid, N, K, A)

    if Answer == False:
        Left = Mid + 1  # 答えが Mid+1 以上である
    if Answer == True:
        Right = Mid     # 答えが Mid 以下である

# 出力（このとき Left=Right になっている）
print('解：', Left)

[実行結果]

500秒後に印刷できる枚数は1041

250秒後に印刷できる枚数は520

125秒後に印刷できる枚数は259

63秒後に印刷できる枚数は130

32秒後に印刷できる枚数は66

16秒後に印刷できる枚数は33

8秒後に印刷できる枚数は16

4秒後に印刷できる枚数は8

6秒後に印刷できる枚数は12

5秒後に印刷できる枚数は9

解： 6

この処理を繰り返すと6秒後に印刷される枚数が12枚となり、6秒後が正解となります。

問題

小さい順に並べられている要素数 $ 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という経路であることが確認できました😊