Problem:


				Max Score: 350 Points 

Problem Statement

					There are N buildings along the line. The i-th building from the left is colored in color i, and its height is currently a_i meters. 

					Chokudai is a mayor of the city, and he loves colorful thigs. And now he wants to see at least K buildings from the left. 

					You can increase height of buildings, but it costs 1 yens to increase 1 meters. It means you cannot make building that height is not integer. 

					You cannot decrease height of buildings. 

					Calculate the minimum cost of satisfying Chokudai's objective. 

					Note: "Building i can see from the left" means there are no j exists that (height of building j) ≥ (height of building i) and j < i. 

Input Format

N K
a_1 a_2 a_3 ... a_N

Output Format

						Print the minimum cost in one line. In the end put a line break.

Constraints

1 ≤ K ≤ N ≤ 15

1 ≤ a_i ≤ 10^9

Scoring

						Subtask 1 [120 points] 

N = K

						Subtask 2 [90 points] 

N ≤ 5

a_i ≤ 7

						Subtask 3 [140 points] 

There are no additional constraints.

Sample Input 1

5 5
3949 3774 3598 3469 3424

Sample Output 1

1541

					The optimal solution is (height of buildings from the left) = [3949, 3950, 3951, 3952, 3953].

Sample Input 2

5 3
7 4 2 6 4

Sample Output 2

7

					The optimal solution is (height of buildings from the left) = [7, 8, 2, 9, 4].



Sample input:
5 5
3949 3774 3598 3469 3424


Sample output:
1541

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, k, *a = map(int, open(0).read().split())
ans = 10**18
for i in range(2 << n):
    h = 0
    c = 0
    b = 0
    for j in range(n):
        if a[j] > h:
            b += 1
            h = a[j]
        elif i >> j & 1:
            c += h - a[j] + 1
            h += 1
            b += 1
    if b >= k:
        ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
INF=10**18
a=list(map(int,input().split()))
ans=INF
for i in range(2**(n-1)):
  cst=0
  cnt=0
  b=a[0]
  for j in range(n-1):
    if (i>>j) & 1:
      cst+=max(b+1-a[j+1],0)
      b=max(a[j+1],b+1)
      cnt+=1
    elif a[j+1]>b:
      cst+=a[j+1]-b
      b=a[j+1]
  if cnt==k-1:
    ans=min(ans,cst)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

n,k=map(int,input().split())
lst=list(map(int,input().split()))

work=lst[0]
ini=[x-work for x in lst]
ini_seen=[0]
work=0
for i in range(1,n):
    if ini[i]>work:
        work=ini[i]
        ini_seen.append(i)

mn=None
for x in combinations(range(n-len(ini_seen)),k-len(ini_seen)):
    sm=0
    work=0
    xtoken=0
    count=1
    for i in range(1,n):
        if i in ini_seen:
            count+=1
            if work<ini[i] : work=ini[i]
            else:
                work+=1
                sm+=work-ini[i]
        elif xtoken<len(x) and i==x[xtoken]+count:
            work+=1
            sm+=work-ini[i]
            xtoken+=1
    if not mn : mn=sm
    if mn>sm : mn=sm
print(mn)

Submission status: Accepted

Solution code:
import sys
from itertools import product
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A_init = list(map(int, input().split()))

    res = f_inf
    for pattern in product([0, 1], repeat=n - 1):
        A = deepcopy(A_init)
        cost = 0
        for idx, p in enumerate(pattern):
            if p == 1:
                prev = max([A[i] for i in range(idx + 1)])
                if A[idx + 1] > prev:
                    continue
                cost += prev + 1 - A[idx + 1]
                A[idx + 1] = prev + 1
        cnt = mi = 0
        for a in A:
            if mi < a:
                mi = a
                cnt += 1
        if cnt >= k:
            res = min(res, cost)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from itertools import combinations as comb
n, k = map(int, input().split())
ns = list(map(int, input().split()))
res = float('inf')
perms = list(range(1,n))
for p in comb(perms, k-1):
    res_tmp = 0
    tmp_max = 0
    p = [0] + list(p)
    for i in range(n):
        if i in p and ns[i] <= tmp_max:
            res_tmp += tmp_max - ns[i] + 1
            tmp_max = tmp_max + 1
        else:
            tmp_max = max(tmp_max, ns[i])
    res = min(res, res_tmp)
print(res)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))

res = float('inf')

for i in range(1<<N):
  a = A[::]
  paint = 0
  cur = 0
  add = 0
  for j in range(N):
    if (i>>j)&1:
      paint += 1
      if a[j] <= cur:
        add += (cur+1) - a[j]
        a[j] = cur+1
      cur = max(cur, a[j])
    else:
      cur = max(cur, a[j])

  if paint == K:
    res = min(res, add)

print(res)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

n, k = map(int, input().split())
arr = np.array(list(map(int, input().split())))

ans = 1 << 60
for x in list(combinations(range(1, n), k - 1)):
    h = 0
    tmp_arr = arr.copy()
    for i in x:
        big = tmp_arr[:i].max() + 1
        if big > tmp_arr[i]:
            h += big - tmp_arr[i]
            tmp_arr[i] = big
    ans = min(ans, h)

print(ans)

Submission status: Accepted

Solution code:
def num_cleared(N, A):
    cleared = 0
    highest_h = 0
    for i in range(N):
        h = A[i]
        if h > highest_h:
            cleared += 1
            highest_h = h
    return cleared

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    cleared = num_cleared(N, A)
    if cleared >= K:
        print(0)
        return

    ans = N * 10**9
    for i in range(1 << N):
        highest_h = A[0]
        cost = 0
        B = [A[0]]
        for j in range(1, N):
            h = A[j]
            if ((i >> j) & 1) == 0:
                highest_h = max(h, highest_h)
                B.append(h)
                continue
            if highest_h >= h:
                cost += (highest_h - h) + 1
                highest_h += 1
                B.append(highest_h)
            else:
                B.append(h)
        cleared = num_cleared(N, B)
        if cleared >= K:
            ans = min(ans, cost)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))

ans=float("inf")
for i in range(2**n):
    num=format(i,"b").zfill(n)
    if num.count("1")!=k:continue
    height,money=0,0
    for j in range(n):
        if num[j]=="1":
            if A[j]<=height:
                money +=height-A[j]+1
                height +=1
            else:height=A[j]
        else:
            if A[j]>height:height=A[j]
    ans=min(ans,money)
print(ans)

Submission status: Accepted

Solution code:
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=copy.copy(A)
ans=[]

for i in range(2**(N-1)):
    L=[0]*(N-1)
    total=0
    count=0
    for j in range(N-1):
        if ((i>>j)&1):
            L[j]=1
            count+=1
    if count>=K-1:
        A=copy.copy(B)
        for m in range(N-1):
            
            if L[m]==1:
                height=max(max(A[:m+1])+1,A[m+1])
                total+=height-A[m+1]
                A[m+1]=height
                
        ans.append(total)
        

print(min(ans))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a_list = list(map(int, input().split()))

ans = float('inf')
for bit in range(2**(N-1)):
    pre_num = a_list[0]
    ans_pre = 0
    count = 1
    index = []
    for i in  range(N-1):
        if bit & (1<<i):
            count+=1
            index.append(i+1)
            if pre_num >= a_list[i+1]:
                ans_pre += pre_num-a_list[i+1]+1
            
                pre_num += 1
                
            else:
                pre_num = a_list[i+1]
                
        else:
            pre_num = max(pre_num, a_list[i+1]+1)
    if count >= K:
        ans = min(ans, ans_pre)
            
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=15*10**10
for i in range(2**(n-1)):#1番目は確定だから
    cnt,s,mh=0,0,a[0]+1
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            x=a[j+1]
            if x>=mh:
                mh=x+1
            else:
                s+=mh-x
                mh+=1
        else:
            mh=max(mh,a[j+1]+1)
    if cnt>=k-1:
        ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n==k:
    suma=sum(a)
    m=a[0]+1
    for i in range(1,n):
        x=a[i]
        if x>=m:
            m=x+1
        else:
            a[i]=m
            m+=1
    print(sum(a)-suma)
    exit()
ans=15*10**10
for i in range(2**(n-1)):#1番目は確定だから
    cnt,s,mh=0,0,a[0]+1
    for j in range(n-1):
        if i>>j&1:
            cnt+=1
            x=a[j+1]
            if x>=mh:
                mh=x+1
            else:
                s+=mh-x
                mh+=1
        else:
            mh=max(mh,a[j+1]+1)
    if cnt>=k-1:
        ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:

import copy
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 10**9*15
for i in range(2**(N-1)):#2番~N番からK-1個選ぶ
    B = copy.copy(A)
    count = 0
    bit = 0
    for j in range(N-1):#A[1]~A[N-1]の内、選ばれるものの数
        bit = bit + (1&(i>>j))
    if(bit == K-1):#K-1個選ぶ
        for k in range(N-1):
            if(i>>k&1):
                if max(B[0:k+1]) >= B[k+1]:#シフト量+2番のビルが1番:B[0]~シフト量+1番:B[k]のビルより高く
                    dif =max(B[0:k+1])-B[k+1]+1
                    B[k+1] += dif#シフト量+2番目のビルを伸ばす
                    count += dif#コストをプラス
        ans = min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
#<14>
#(point)
#全探索によってどの建物が見えるようにするかを決めて必要な費用を計算。
#建物が見える =　それより左にある建物maxより１大きいなので左から線形に
#最大値を更新、計算量は高々n_c_kのcombについてO(N)の操作なのでおｋ
from itertools import combinations
n, k = map(int,input().split())
a = list(map(int,input().split()))
mn = 10 ** 18

for b in combinations(range(1, n),k - 1):#一番左は固定
    mx = a[0] #初期値=一番左の建物
    score = 0
    for j in range(1, n):
        if j in b:#見えなあかん建物なら
            if a[j] <= mx : #低けりゃ高くする
                mx += 1
                score += (mx - a[j])
            else: #高さが十分なら最大値を更新するだけ
                mx = a[j]
        else:
            mx = max(mx, a[j])#別に見えんくてもいい建物なら最大値更新
    mn = min(mn, score)
print(mn)

Submission status: Accepted

Solution code:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
mn = 10**18
for B in combinations(range(1,N),K-1): # 一番左は固定
    mx = A[0] # 初期値は一番左の建物
    score = 0
    for n in range(1,N):
        if n in B: # 見えるようにすべき建物なら
            if A[n] <= mx: # 低ければ高くする
                mx += 1
                score += (mx - A[n])
            else: # 高さが十分なら何もしない。最大値を更新
                mx = A[n]
        else:
            mx = max(mx, A[n]) # 見えなくても良い建物なら、最大値を更新
    mn = min(mn, score)
print (mn)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 10 ** 18
for bit in range(1 << N):
    #check k
    count = 0
    for i in range(N):
        if bit & 1 << i > 0:
            count += 1
    if count < K:
        continue

    cost = 0
    h = -1
    for i in range(N):
        if bit & 1 << i > 0:
            if A[i] <= h:
                cost += h - A[i] + 1
                h += 1
        h = max(h, A[i])
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
MIN = float('inf')
for bit in range(1<<N):
    tmpA = A[:]
    L = []
    for i in range(N):
        if bit & (1<<i):
            L.append(i)
    SUM = 0
    for l in L:
        MAX = max(tmpA[:l]+[0])
        if MAX >= tmpA[l]:
            SUM += MAX+1-tmpA[l]
            tmpA[l] = MAX+1
    count = 0
    MAX = 0
    for i in range(N):
        if tmpA[i] > MAX:
            count += 1
            MAX = tmpA[i]
    if count >= K:
        MIN = min(MIN,SUM)
print(MIN)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=10010010010010010

for i in range(1<<n-1):
  if bin(i).count("1")!=k-1:
    continue
  cnt=0
  cost=0
  #print("cnt i",i)
  prevh=a[0]
  for j in range(n-1):
    if 1<<j & i:
      if prevh>=a[j+1]:
        cost+=prevh+1-a[j+1]
        prevh+=1
        #print("cost",j,cost)
      else:
        prevh=a[j+1]
    else:
      prevh=max(prevh,a[j+1])
  ans=min(ans,cost)
  #print("ans",ans)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))

ans = 1e+18
for i in range(1<<N):
  if bin(i).count('1') != K:
    continue
  cost = 0
  cur_height = 0
  for j in range(N):
    if i & (1<<j):
      cost += max(0, cur_height-a[j]+1)
      cur_height = max(a[j], cur_height+1)
    else:
      cur_height = max(a[j], cur_height)
  ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**20

# どのビルを見るかをbit全探索
for i in range(1 << n):
    li = []
    for j in range(n):
        if (i >> j)&1:
            li.append(j)
    if len(li) < k:
        continue
    point = 0
    now = a[0]
    for l in range(1,n):
        if l in li and a[l] <= now:
            point += now+1-a[l]
            now += 1
        now = max(now,a[l])
    ans = min(ans,point)
    
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))

ans = float('inf')
for status in range(1<<N):
    cnt = 0
    tmp = 0
    std = 0
    for mask in range(N):
        if (1<<mask)&status:
            cnt += 1
            if std >= A[mask]:
                tmp += std - A[mask] + 1
                std += 1
        
        std = max(std,A[mask])
    if cnt >= K:
        ans = min(ans,tmp)
    
print(ans)

Submission status: Accepted

Solution code:
import copy

def bit_all(n,k,nn):
    ans = float("inf")
    for i in range(2 ** n):
        m = 0
        cnt = 0
        num = copy.deepcopy(nn)
        kind = 0
        for j in range(n):
            # 順に右にシフトさせ最下位bitのチェックを行う
            if ((i >> j) & 1):
                # フラグが立っていた時の処理
                if m >= num[j]:
                    cnt += 1 + m - num[j]
                    num[j] = m+1
                m = max(m,num[j])
                kind += 1
            else:
                #フラグがたっていなかった時の処理
                if num[j] > m:
                    m = num[j]
                    kind += 1
        if kind >= k:
            ans = min(ans,cnt)
            #print(ans,num)
    return ans
n,k = map(int,input().split())
num = list(map(int,input().split()))
print(bit_all(n,k,num))

Submission status: Accepted

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
#n = int(input())
n, k = map(int, sys.stdin.readline().split())
#n = input()
a = list(map(int, sys.stdin.readline().split()))

l = list(itertools.combinations(range(n), k))

ans = 10 ** 18
for i in range(len(l)):
    cost = 0
    m1 = 0
    p = 20
    for j in range(l[i][0]+1):
        if a[j] > m1:
            m1 = a[j]
            p = j

        if j == l[i][0]:
            if m1 == a[j]:
                if p != j:
                    cost += 1
            else:
                cost += (m1 - a[j] + 1)

    
    r = 1
    if len(l[0]) >= 2:
        q = l[i][r]
    else:
        q = 20

    m2 = a[l[i][0]] + cost

    for j in range(l[i][0]+1, n):
        if j == q:
            if a[j] > m2:
                m2 = a[j]
            else:
                m2 += 1
                cost += (m2 - a[j])

            if r != len(l[0])-1:
                r += 1
                q = l[i][r]
            
        else:
            if a[j] > m2:
                cost += a[j] - m2
                m2 = a[j]
                

    if cost < ans:
        ans = cost


print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def slove():
    n, k = map(int,input().split())
    building = list(map(int,input().split()))
    # print(building)
    
    ans = 10 ** 15
    for i in range(1 << n):
        if i & 1 == 1 or bin(i >> 1).count("1") != k-1:
            continue

        # 2020/06/09 first idea
        # this is not completed answer
        """ 
        p_b = [building[0],]
        for j in range(1,n):
            if i >> j & 1 == 1:
                p_b.append(building[j])
        #print(bin(i),p_b) 
        tmp_ans = 0
        max_h = p_b[0]
        for j in range(1,n):
            if max_h < p_b[j]:
                max_h = p_b[j]
                continue
            else:
                tmp_ans += 1 + max_h - p_b[j]
                max_h += 1
        #print(tmp_ans)
        else:
            ans = min(ans,tmp_ans)
        """
        tmp_ans = 0
        highest = 0
        for j in range(n):
            if i >> j & 1 and highest < building[j]:
                highest = building[j]
            elif i >> j & 1 and highest >= building[j]:
                highest += 1
                tmp_ans += highest - building[j]
            else:
                if highest < building[j]:
                    highest = building[j]
        ans = min(ans,tmp_ans)
    print(ans)

if __name__ == "__main__":
    slove()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

cost = 10 ** 18
for i in range(2 ** (n - 1)):
    num = 0
    c = 0
    prev = a[0]
    for j in range(n - 1):
        if i >> j & 1:
            num += 1
            if a[j + 1] <= prev:
                c += prev - a[j + 1] + 1
                prev += 1
        prev = max(prev, a[j + 1])
    if num >= k - 1:
        cost = min(c, cost)
print(cost)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))

ans = pow(10, 18)

for i in range(2 ** N):
    cost = 0
    cnt = 0
    highest = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
            if highest >= a[j]:
                cost += highest - a[j] + 1
                highest += 1

        highest = max(highest, a[j])
    if cnt >= K:
        ans = min(cost, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K,*A= map(int, read().split())
l = [i for i in range(1,N)]
cost = float('inf')
for B in itertools.combinations(l,K-1):
  ans = 0
  pre = A[0]
  j = 0
  for i in range(1,N):
    if j == K-1:
      break
    if B[j]== i:
      j+=1
      if pre < A[i]:
        pre = A[i]
      else:
        ans += pre-A[i]+1
        pre +=1
    else:
      if pre < A[i]:
        pre = A[i]
  cost = min(ans,cost)
print(cost)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
 
a = list(map(int, input().split()))
 
min_cost = float("inf")
for i in range(2**n):
    if bin(i).count("1") != k:
        continue
 
    min_h = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            min_h += 1
            cost += max(0, min_h-a[j])
 
        min_h = max(min_h, a[j])
 
    min_cost = min(min_cost, cost)
 
print(min_cost)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))

ans = pow(10, 18)

for i in range(2 ** N):
    cost = 0
    cnt = 0
    highest = 0
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
            if highest >= a[j]:
                cost += highest - a[j] + 1
                highest += 1

        highest = max(highest, a[j])
    if cnt >= K:
        ans = min(cost, ans)

print(ans)

Submission status: Accepted

Solution code:
import itertools


N, K = map(int, input().split())
a = list(map(int, input().split()))
ans = float('inf') 

for pattern in itertools.combinations(range(1,N),K-1):
    temp_cost = 0
    temp_pattern = [0] + list(pattern)
    max_high = a[0]

    for i in range(1,N):
        if i in temp_pattern:
            diff = a[i]- max_high
            if diff ==  0:
                temp_cost += 1
                max_high = max_high + 1
            elif diff < 0 :
                temp_cost += ( max_high - a[i] ) + 1
                max_high = max_high +1
            else:
                temp_cost += 0
                max_high = a[i]
        else:
            max_high = max (a[i] ,max_high)

    ans = min(ans, temp_cost)

print(ans)

Submission status: Accepted

Solution code:
import copy
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))

def dfs(bitstring):
  if len(bitstring) == N:
    if sum(bitstring) == K:
      cost = 0
      B = copy.deepcopy(A)
      for i in range(1, N):
        if bitstring[i]:
          previousMax = max(B[0:i])
          if previousMax < B[i]:
            continue
          else:
            cost += previousMax - B[i] + 1
            B[i] = previousMax + 1
      return cost
    else:
      return sys.maxsize
  else:
    return min(dfs(bitstring + [False]), dfs(bitstring + [True]))

print(dfs([1]))

Submission status: Accepted

Solution code:
import itertools
import copy
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = 10 ** 100
for item in itertools.combinations(range(n), r=k):
    tmp = 0
    b = copy.copy(a)
    for i in item:
        b[i] = a[i] if i==0 else max(max(b[:i]) + 1, a[i])
        tmp += b[i] - a[i]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
height2=height.copy()
ans = 10 ** 100
# if N==K:
#     cost=0
#     for i in range(1,N):
#         tarou=max(height2[:i])
#         if tarou>=height2[i]:
#             cost+=tarou-height2[i]+1
#             height2[i]=tarou+1
#     print(cost)
#     exit()
for i in range(2 ** N):
    cost = 0
    height2 = height.copy()
    if bin(i).count("1")==K:
        for j in range(1,N):
            if i >> j & 1:
                    tarou=max(height2[:j])
                    if height2[j]<=tarou:
                        cost+=tarou-height2[j]+1
                        height2[j]=tarou+1
        # if N==K:
        #     print(cost)
        #     exit()
        if ans > cost:
            ans = cost

print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
height2=height.copy()
ans = 10 ** 10
# if N==K:
#     cost=0
#     for i in range(1,N):
#         tarou=max(height2[:i])
#         if tarou>=height2[i]:
#             cost+=tarou-height2[i]+1
#             height2[i]=tarou+1
#     print(cost)
#     exit()
for i in range(2 ** N):
    cost = 0
    height2 = height.copy()
    if bin(i).count("1")==K:
        for j in range(1,N):
            if i >> j & 1:
                    tarou=max(height2[:j])
                    if height2[j]<=tarou:
                        cost+=tarou-height2[j]+1
                        height2[j]=tarou+1
        if N==K:
            print(cost)
            exit()
        if ans > cost:
            ans = cost

print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
height2=height.copy()
ans = 10 ** 10
if N==K:
    cost=0
    for i in range(1,N):
        tarou=max(height2[:i])
        if tarou>=height2[i]:
            cost+=tarou-height2[i]+1
            height2[i]=tarou+1
    print(cost)
    exit()
for i in range(2 ** N):
    cost = 0
    height2 = height.copy()
    if bin(i).count("1")==K:
        for j in range(1,N):
            if i >> j & 1:
                if N==K:
                    if height2[j-1]>=height2[j]:
                            cost+=height2[j-1]-height2[j]+1
                            height2[j]+=height2[j-1]-height2[j]+1
                else:
                    tarou=max(height2[:j])
                    if height2[j]<=tarou:
                        cost+=tarou-height2[j]+1
                        height2[j]=tarou+1

        if ans > cost:
            ans = cost

print(ans)

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
height = list(map(int, input().split()))
ans = 10 ** 10
if N==K:
    cost=0
    for i in range(1,N):
        if height[i-1]>=height[i]:
            cost+=height[i-1]-height[i]+1
            height[i]+=height[i-1]-height[i]+1
    print(cost)
    exit()
for i in range(2 ** N):
    count=1
    cost = 0
    height2 = height.copy()
    for j in range(N):
        if i >> j & 1:
            if j!=0:
                tarou=max(height2[:j])
                if height2[j]<=tarou:
                    cost+=tarou-height2[j]+1
                    height2[j]+=tarou-height2[j]+1
                    count+=1
                else:count+=1
    # zenkai=0
    # for x in range(1,N):
    #     if height2[zenkai] < height2[x]:
    #         count += 1
    #         zenkai=x
    if ans > cost and count >= K:
        ans = cost

print(ans)

Submission status: Accepted

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

from itertools import combinations

N,K=map(int,input().split())
a=list(map(int,input().split()))

minc=10**12
ai=[i for i in range(N)]
for i in combinations(ai,K):
    ac=a[:]
    cost=0
    i=list(i)
    for j in range(1,K):
        costt=max(max(ac[:i[j]])-ac[i[j]]+1,0)
        ac[i[j]]+=costt
        cost+=costt
    minc=min(cost,minc)
print(minc)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())

a = list(map(int, input().split()))

min_cost = float("inf")
for i in range(2**n):
    if bin(i).count("1") != k or not i & 1:
        continue

    min_h = a[0]
    cost = 0
    for j in range(1, n):
        if i >> j & 1:
            min_h += 1
            cost += max(0, min_h-a[j])

        min_h = max(min_h, a[j])

    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))

#左からi個、k種類選んだ場合
#dp[i][k]=cost



result=10**100
for i in range(2**(n-1)):
    #print(bin(i))
    if str(bin(i)).count("1")>=k-1:
        #print(">>>>>>",bin(i))
        bk=a[0]
        cost=0
        for j in range(n-1):
            if i>>j&1:
                if bk<a[j+1]:
                    bk=a[j+1]
                else:
                    bk+=1
                    cost+=(bk-a[j+1])
            else:
                bk=max(bk,a[j+1])
                #print(bk,a[j+1],bk-a[j+1])
        result=min(cost,result)
print(result)

Submission status: Accepted

Solution code:
import itertools

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

for li in itertools.product([0,1], repeat=n-1):
  if li.count(1) < k-1:
    continue
  cost,height=0,A[0]
  for i in range(1,n):
    if height < A[i]:
      height=A[i]
      continue
    if li[i-1]:
      cost += (height-A[i]+1)
      height += 1 
  ans.append(cost)
  
print(min(ans))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
def main():
    N, K = map(int, input().split())
    a = [int(i) for i in input().split()]
    ans = 10 ** 11
    for i in range(1 << N):
        now = a[0]
        count = 0
        copy_a = copy.copy(a)
        for j in range(1, N):
            if i >> j & 1:
                count += max(now + 1 - a[j], 0)
                copy_a[j] = max(now + 1, a[j])
            now = max(now, copy_a[j])
        now = 0
        color = 0
        for j in range(N):
            if now < copy_a[j]:
                color += 1
                now = copy_a[j]
        if color >= K:
            ans = min(ans, count)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
mn = 10**18
for B in combinations(range(1,N),K-1):
    mx = A[0]
    score = 0
    for n in range(1,N):
        if n in B:
            if A[n] <= mx:
                mx += 1
                score += (mx - A[n])
            else:
                mx = A[n]
        else:
            mx = max(mx, A[n])
    mn = min(mn, score)
print (mn)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))

ans=10**100
for i in range(2**(N-1)):
  bit=format(i,'0'+str(N)+'b')
  bit=list(map(int,bit))
  maxh=A[0]
  price=0
  color=1
  for n in range(N):
    if n==0:continue
    elif bit[n]==0:
      if A[n]>maxh:
        color+=1
        maxh=A[n]
    else:
      if A[n]<=maxh:
        maxh+=1
        price+=maxh-A[n]
        color+=1
      else:
        color+=1
        maxh=A[n]
  if color>=K and price<=ans:
    ans=price
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N, K = map(int, input().split())

a = list(map(int, input().split()))
sub_a = {0}
a_first = a[0]

res = 10**11 # min(res, ) を取る場合はresを大きい数に取る

for j in range(N):
    if a_first < a[j]:
        sub_a.add(j)
        a_first = a[j]

colors = len(sub_a) # 最初に見えている色の種類
not_sub_a = {i for i in range(N)} - sub_a


for k in combinations(not_sub_a, K - colors):
    cost = 0
    test_a = []
    for i in range(N):
        if i in sub_a or i in k:
            test_a.append(a[i]) # test_a には左から写る予定のK個のビルの高さが入っている
    for i in range(len(test_a)-1):
        if test_a[i] >= test_a[i+1]:
            cost += test_a[i] - test_a[i+1] +1
            test_a[i+1] = test_a[i] + 1
    res = min(res, cost)

print(res)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = set(comb)
        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if i in included:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = [False] * N
        for i in comb:
            included[i] = True

        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if included[i]:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)

    return


if __name__ == '__main__':
    main()