上限値（草の高さ）

問題

$ N $ 個の草が一列に並んでいて、$ 1 $ から $ N $ までの番号がつけられています。

各草の高さは $ 1 $以上の整数値で表され、それについて次の情報 $ S_1,S_2,…, S_{N-2} $ が分かっています。

🔹$ S_i = A $ のとき、草 $ i $ より草 $ i + 1 $ の方が高い。
🔹$ S_i = B $ のとき、草 $ i $ より草 $ i + 1 $ の方が低い。

$ N $ 個の草の高さの合計として考えられる最小値を求めて下さい。

[制約]
🔹$ 2 \leqq N \leqq 3000 $

解き方・ソースコード

この問題は、まず $ 1 $ から $ N $ まで $’A’$ の連続回数を数えます。

次に$ N $ から $ 1 $ まで $’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
#--------- 入力例 -----------
N = 7           # 草の数
S = ['A', 'A', 'B', 'A', 'B', 'B']  # 隣合う草の高低情報
#----------------------------
# 配列の準備
ret1 = [ None ] * N
ret2 = [ None ] * N

# 1からNへ'A'の連続数を数える
sa = 1  # 'A'の連続回数
ret1[0] = 1
for i in range(N - 1):
    if S[i] == 'A':
        sa += 1
    if S[i] == 'B':
        sa = 1
    ret1[i + 1] = sa
print('ret1', ret1)

# Nから1へ'B'の連続数を数える
sa = 1  # 'B'の連続回数
ret2[N - 1] = 1
for i in reversed(range(N - 1)):
    if S[i] == 'A':
        sa = 1
    if S[i] == 'B':
        sa += 1
    ret2[i] = sa
print('ret2', ret2)

# 連続数の多いほうを選ぶ
ret3 = [max(a, b) for a, b in zip(ret1, ret2)]
print('ret3', ret3)

print('解：', sum(ret3))

[実行結果]

ret1 [1, 2, 3, 1, 2, 1, 1]

ret2 [1, 1, 2, 1, 3, 2, 1]

ret3 [1, 2, 3, 1, 3, 2, 1]

解： 13

草の高さの合計値として考えられる最小値は 13 ということが分かりました。