AtCoder:square869120Contest #4 B - Buildings are Colorful!で１つだけWAしてしまう

Question

前提・実現したいこと

AtCoder:square869120Contest #4 B - Buildings are Colorful!で１つだけWAしてしまいます。
コードのどこが間違っているのでしょうか？

https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b

発生している問題・エラーメッセージ

一番最後のケース「sub3_in2.txt」がWAです。

該当のソースコード

n,k = map(int, input().split())
A = list(map(int, input().split()))
mlst = []

if n == 1 or k == 1:
  exit(print(0))

for i in range(2**(n-1)):
  lst = [0]*(n-1)
  for j in range(n-1):
    if i>>j & 1:
      lst[j] = 1
  lst = [1] + lst
  if k <= sum(lst):
    B = A[0]
    money = 0
    for l in range(1,n):
      if lst[l] == 1:
        if B - A[l] >= 0:
          money += B - A[l] + 1
          B += 1
        else:
          B = A[l]
    mlst.append(money)
    
print(min(mlst))

試したこと

n==1やk==1のときにrangeの範囲がおかしくなるせいかと思ったのですが、そこを場合分けして除いても、やはりWAのままです。

Answer 1

4 3
1 10000 2 3

落としてるのが1ケースだけなのでエッジケースを想定してるのかもしれませんが、間違った解を出すのはそれほど特殊なケースではありません。
どういう意図でコードを書いてるのかがわからないので、問題の読み間違いなのか解法の間違いかコードの書き間違いなのか判断できませんが上のケースで気付けると思います。

Comments

[nk1]

回答ありがとうございます！
エッジケースでも全然ない、このケースでWAするんですね。
このコードの意図はビット全探索で、「１」のビルのみの色塗りをするというふうにコードを書いていましたが、「0」のビルが、それより右の「１」のビルより高いときに不具合が生じていました。
以下のように「0」のビルも考慮に入れたコードをかくことで解決しました！
ありがとうございます！
n,k = map(int, input().split())
A = list(map(int, input().split()))
mlst = []

for i in range(2**(n-1)):
lst = [0]*(n-1)
for j in range(n-1):
if i>>j & 1:
lst[j] = 1
lst = [1] + lst
if k <= sum(lst):
B = A[0]
money = 0
for l in range(1,n):
if lst[l] == 1:
if B - A[l] >= 0:
money += B - A[l] + 1
B += 1
else:
B = A[l]
#ここ！
else:
B = max(B, A[l])

mlst.append(money)

print(min(mlst))

Answer 2

n,k = map(int, input().split())
A = list(map(int, input().split()))
mlst = []



for i in range(2**(n-1)):
  lst = [0]*(n-1)
  for j in range(n-1):
    if i>>j & 1:
      lst[j] = 1
  lst = [1] + lst
  if k <= sum(lst):
    B = A[0]
    money = 0
    for l in range(1,n):
      if lst[l] == 1:
        if B - A[l] >= 0:
          money += B - A[l] + 1
          B += 1
        else:
          B = A[l]
      #ここ！
      else:
        B = max(B, A[l])
          
    mlst.append(money)
    
print(min(mlst))