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:
def nasu(n):
  L = [0] * N
  for i in range(N):
    if n >> i & 1:
      L[i] = 1
  ans = 0
  t = a[0]
  for i in range(1, N):
    if L[i] == 1:
      if t >= a[i]:
        ans += t - a[i] + 1
        t = t + 1
      else:
        t = a[i]
    else:
      t = max(t, a[i])
  return ans

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

ans = 15 * 10 ** 9 

n = (1 << K) - 1
while n < (1 << N):
  ans = min(ans, nasu(n))

  x = n & -n
  y = n + x
  n = ((n & ~y) // x >> 1) | y

print(ans)

Submission status: Accepted

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

ans=float('inf')
for i in range(2**N):
    b=copy.deepcopy(a)
    num=0
    for j in range(N):
        if i>>j&1:
            num+=max(b[:j+1])+1-b[j]
            b[j]=max(b[:j+1])+1
    o=1
    #print(b)
    for y in range(1,N):
        if max(b[:y])<b[y]:
            o+=1
    if o>=K:
        
        ans=min(num,ans)
        #print(ans,b)
print(ans)

Submission status: Accepted

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

ans = 10**18
for bit in range(1<<N):
    highest, cost, cnt = 0, 0, 0
    for i in range(N):
        if bit>>i & 1:
            if A[i] <= highest:
                cost += highest-A[i]+1
                highest += 1
            else:
                highest = max(highest,A[i])
            cnt += 1
        else:
            highest = max(highest,A[i])
    if cnt >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

def main():
    N,K = map(int, input().split())
    a_list = [int(e) for e in input().split()]

    #見えるようにする建物を選ぶ
    #当該の建物まで左から見ていく
    #当該の建物より max((左の最大値+1 - 現状の高さ),0)が各建物に必要なコスト
    #各建物に必要なコストを合計する

    ans = 10**100

    l = [i for i in range(0,N)]

    for v in itertools.combinations(l,K): #最重で6435通り
        copied_a_list = copy.copy(a_list)
        
        v = set(v)
        left_max = copied_a_list[0]-1
        temp_ans = 0
        
        for i in range(N): #15
            if i in v:
                temp_ans += max(0,left_max+1 - copied_a_list[i])
                copied_a_list[i] = max(left_max+1,copied_a_list[i])
            
            if copied_a_list[i] > left_max:
                left_max = copied_a_list[i]
        
        #print(v,copied_a_list,temp_ans)
        
        if temp_ans < ans:
            ans = temp_ans
            
    print(ans)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    a = [int(x) for x in input().split()]

    ans = 10 ** 11
    for bit in range(1 << N):
        can = set()
        for i in range(1, N):
            if bit & (1 << i):
                can.add(i)
        h_max = a[0]
        cost = 0
        cnt = 1
        for i in range(1, N):
            res = h_max - a[i] + 1 if i in can and a[i] <= h_max else 0
            cost += res
            cnt += 1 if a[i] + res > h_max else 0
            h_max = max(h_max, a[i] + res)
        if cnt >= K:
            ans = min(ans, cost)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N, K = map(int, input().split()) # Nは建物の数、K色以上に塗る
A = list(map(int, input().split()))
N_index = list(range(1,N)) # 一番左は固定なので

min_cost = float('inf')
for target_indexes in itertools.combinations(N_index, K-1): # N_indexからK-1個選ぶ方法を全通り試す
    cost = 0
    copy_A = A.copy()
    for i in target_indexes:
        if copy_A[i] <= max(copy_A[:i]):
            diff = max(copy_A[:i]) - copy_A[i] # ターゲットの建物の場合はそれより左側の建物のmaxより1だけ大きくする
            copy_A[i] += diff + 1
            cost += diff + 1

    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:
import itertools

N, K = map(int, input().split()) # Nは建物の数、K色以上に塗る
A = list(map(int, input().split()))
N_index = list(range(1,N))

min_cost = float('inf')
for target_indexes in itertools.combinations(N_index, K-1): # N_indexからK個選ぶ方法を全通り試す
    cost = 0
    copy_A = A.copy()
    for i in range(1, N):
        if i in target_indexes:
            if copy_A[i] <= max(copy_A[:i]):
                diff = max(copy_A[:i]) - copy_A[i] # ターゲットの建物の場合はそれより左側の建物のmaxより1だけ大きくする
                copy_A[i] += diff + 1
                cost += diff + 1

    min_cost = min(min_cost, cost)

print(min_cost)

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:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
A = inpl()

ans = float('inf')
for bi in itertools.product([0,1],repeat=n-1):
    if bi.count(1) < k-1:
        continue

    pre = A[0]
    s = 0
    for i in range(1,n):
        if bi[i-1] == 1:
            pre = max(pre+1,A[i])   
            s += max(0,pre-A[i])
        else:
            pre = max(pre,A[i])
    ans = min(ans,s)

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n,k=MI()
    height=LI()
    ans=inf
    for x in product([0,1],repeat=n):
        if sum(list(x))<k:
            continue
        mx=0
        res=0
        for i in range(n):
            if x[i]==1:
                if height[i]<=mx:
                    res+=mx-height[i]+1
                    #print(mx-height[i]+1)
                    mx+=1
                else:
                    res+=0
                    mx=max(mx,height[i])
            else:
                mx=max(mx,height[i])
        #print(res)
        ans=min(ans,res)
    print(ans)            
                
                
    
        
        
        
        




if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import sys
import itertools


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    a = list(map(int, input().split()))

    return N, K, a


def main(N: int, K: int, a: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 建物の個数(1 <= N <= 15)
        K (int): 色の数(1 <= K <= N)
        a (list): 高さ(1 <= a_i <= 10**9)
    """
    # 求解処理
    ans = sys.maxsize
    for buildings in itertools.combinations(range(N), K):
        cost = 0
        highest = a[0] - 1
        for n in range(N):
            a_n = a[n]
            built = 0
            if n in buildings:
                built = max(highest - a_n + 1, 0)
                cost += built
            highest = max(highest, a_n + built)
        ans = min(ans, cost)

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, K, a = get_input()

    # メイン処理
    main(N, K, a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import sys
import itertools

# 標準入力を取得
N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

# 求解処理
ans = sys.maxsize
for buildings in itertools.combinations(range(N), K):
    cost = 0
    highest = a[0] - 1
    for n in range(N):
        a_n = a[n]
        built = 0
        if n in buildings:
            built = max(highest - a_n + 1, 0)
            cost += built
        highest = max(highest, a_n + built)
    ans = min(ans, cost)

# 結果出力
print(ans)

Submission status: Accepted

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

for i in range(1<<N):
    seen = 1
    pay = 0
    now = a[0]
    for j in range(1, N):
        if (i >> j) & 1:
            if a[j] <= now:
                pay += now - a[j] + 1
                now += 1
                seen += 1
            else:
                break
        else:
            if a[j] > now:
                seen += 1
                now = a[j]
        if seen >= K:
            ans = min(ans, pay)
            break


print(ans)

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):
    kar = a[:]
    b = format(i, 'b').rjust(n,"0")
    if b.count("1") != k:
        continue
    now = 0
    cou = 0
    for j in range(n):
        if b[j] == "1":
            cou += max(0,now - kar[j] + 1)
            kar[j] += max(0,now - kar[j] + 1)
        now = max(now,kar[j])
    ans = min(ans,cou)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
import itertools
import numpy as np
ans_cnt = np.Inf
for now in itertools.combinations(range(1,N), K-1):
    height = A[0]
    cnt = 0
    for i in range(1,len(A)):
        if i in now:
            if A[i] > height:
                height = A[i]
            else:
                height += 1
                cnt += height - A[i]
        else:
            height = max(height, A[i])
    ans_cnt = min(cnt, ans_cnt)
print(ans_cnt)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=float('INF')
for i in range(1<<(N-1)):
  cnt,s,t=0,0,a[0]+1
  for j in range(N-1):
    if i>>j&1:
      cnt+=1
      x=a[j+1]
      if x>=t:
        t=x+1
      else:
        s+=t-x
        t+=1
    else:
      t=max(t,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()))

ans = float("inf")
for i in range(2 ** n):
    can_see_list = list(bin(i)[2:].zfill(n))
    cost = 0
    now_hieght = A[0]
    if can_see_list[0] == '1':
        if can_see_list.count('1') < k:
            continue
    else:
        if can_see_list.count('1') < k - 1:
            continue
    for num, can_see in enumerate(can_see_list):
        if can_see == "1":
            if now_hieght >= A[num]:
                cost += (now_hieght - A[num]) + 1
                now_hieght = now_hieght + 1
            else:
                now_hieght = A[num]
        else:
            now_hieght = max(now_hieght, A[num])
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
ans = 10**11

for i in range(2 ** N):
    B = ""
    lenB = 0
    for j in range(N):
        if (i >> j) & 1:
            B += "1"
            lenB += 1
        else:
            B += "0"
    if lenB == K:
        s = 0
        cur = A[0]
        for k in range(1, N):
            if B[k] == "1" and A[k] <= cur:
                s += cur - A[k] + 1
                cur += 1
            else:
                cur = max(cur, A[k])
        #print(B, s)
        ans = min(ans, s)
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 bit in itertools.product([0,1],repeat=N):
    if bit[0]==1 and bit.count(1)>=K:
        cost=0
        cr=a[0]
        for i in range(1,N):
            if bit[i]==1:
                if cr+1>=a[i]:
                    cost+=(cr+1-a[i])
                    cr=cr+1
                else:
                    cr=a[i]
            else:
                cr=max(cr,a[i])
        ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
import copy
import math
import time
import statistics
import math

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():
    start = time.time()

    n, k = get_int_multi()
    a = get_int_list()
    ans = 10 ** 10 * 15

    for i in range(2 ** n):
        count = 0
        for ii in range(n):
            if (i >> ii) & 1:
                count += 1
        if count != k: #k個の1がない場合はスキップ
            continue

        wk_high = 0
        money = 0
        for ii in range(n):
            if (i >> ii) & 1:
                add_money = max(0, wk_high + 1 - a[ii])
                money += add_money
                wk_high = a[ii] + add_money
            else:
                wk_high = max(wk_high, a[ii])
        ans = min(ans, money)
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools

import numpy as np


# 入力読み込み
n, k = map(int, input().split())
a = list(map(int, input().split()))

min_cost = 15000000001
for i in itertools.product([True, False], repeat=n):
    key = np.array(i, dtype=bool)
    if np.count_nonzero(key) != k:
        continue
    
    # コスト計算
    cost = 0
    max_height = 0
    for is_look, ai in zip(key, a):
        if not is_look:
            max_height = max(max_height, ai)
        elif ai > max_height:
            max_height = ai
        else:
            max_height += 1
            cost += max_height - ai
    
    min_cost = min(min_cost, cost)

print(min_cost)

Submission status: Accepted

Solution code:
import itertools

N,K = map(int,input().split())
A = list(map(int,input().split()))
L = [_ for _ in range(1,N)]
ans = float("inf")
cand = list(itertools.combinations(L,K-1))
#print(cand)
for C in cand:
  C = list(C)
  C.sort()
  temp = 0
  prev = A[0] #最初のビルは必ず見える。
  #print(C)
  Flag = True
  for i in C:
    #print(prev,min(A[:i]))
    if prev < max(A[:i]):
      #print(C)
      Flag = False
      break
    if A[i] <= prev:
      prev += 1
      temp += prev-A[i]
    else:
      prev = A[i]
  if Flag:
    ans = min(ans,temp)
print(ans)

Submission status: Accepted

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

min_cost = float('inf')
for Buildings in itertools.combinations(range(N),K):
    min_height = 0
    cost = 0
    for i in range(N):
        if i in Buildings:
            h = A[i]
            if h>min_height:
                min_height = h
                continue
            cost+=(min_height+1) - h
            min_height += 1
            continue
        min_height = max(min_height,A[i])

    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 = float('inf')

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

  if see == K:
    ans = min(ans, add)

print(ans)

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):
    x=format(i,'015b')
    Max=0
    yen=0
    for j in range(1,n+1):
        if x[-j]=='1':
            if Max<a[j-1]:
                Max=a[j-1]
            else:
                Max+=1
                yen+=Max-a[j-1]
        else:
            Max=max(Max,a[j-1])
    #print(x)
    temp=0
    for j in range(15):
        temp+=int(x[j])
    #print(temp,k)
    if temp>=k:
        ans=min(ans,yen)
print(ans)

Submission status: Accepted

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

# 制約が小さいので、「見えてほしい建物」を全探索できる

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

ans = 10 ** 13
for i in range(2 ** N):
  case = bin(i)[2:].zfill(N)
  if case.count("1") < K:
    continue
  # 前から順に見ていって、それまでで一番大きい建物の高さを記録
  # 選ばれた建物が、それまでで一番大きい建物の高さ + 1の高さになるように金額を計算
  # その最小値を求める
  cost = 0
  high = 0
  for j in range(N):
    # j番目の建物は選ぶ対象か？
    if (i >> j) & 1:
      if high >= A[j]:
        high += 1
        cost += (high - A[j])
    high = max(A[j], high)
  if ans > cost:
    ans = cost
print(ans)

Submission status: Accepted

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

# ライブラリ
def get_bits_pattern(n):
    bits_pattern = []
    for i in range(2**n):
        bits = [False]*n

        for j in range(n):
            if i >> j & 1:
                bits[j] = True
        bits_pattern.append(bits)
    return bits_pattern

# 処理
bits_pattern = get_bits_pattern(n)
new_bits_pattern = []
for bits in bits_pattern:
    counter = 0
    for bit in bits:
        if bit:
            counter += 1
    if counter == k:
        new_bits_pattern.append(bits)

yens = []
for bits in new_bits_pattern:
    max_height = 0
    yen = 0
    for i, bit in enumerate(bits):
        if bit:
            if max_height >= a[i]:
                yen += max_height - a[i] + 1
                max_height = max(max_height, a[i]) + 1
            else:
                max_height = max(max_height, a[i])
        else:
            max_height = max(max_height, a[i])
            
    yens.append(yen)

import numpy as np
print(np.min(yens))

Submission status: Accepted

Solution code:
from itertools import combinations

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

# best_score = float("inf")
# for sel in combinations(range(N), K):
#     cost = 0

#     # 左からコストを見る
#     # 先頭未満の最大高さを超すまで上げる
#     first = sel[0]
#     first_max = A[first]
#     for k in range(first):
#         first_max = max(first_max, A[k])
#     current = first_max
#     if first_max > 0:
#         cost += abs(A[first] - current) 
    
#     for i in range(1, K):
#         if current > A[sel[i]]:
#             cost += abs(A[sel[i]] - current) + 1
#             current += 1
#         else:
#             current = A[sel[i]] + 1
#     # print(sel, cost)
#     best_score = min(best_score, cost)
# print(best_score)

best_score = float("inf")
for sel in combinations(range(N), K):
    sel = sorted(sel)
    cost = 0
    m = -1

    for i in range(N):
        if i not in sel:
            # これ以上の高さにならないといけない
            m = max(m, A[i])
        else:
            if m >= A[i]:
                cost += 1 + m - A[i]
                m += 1
            else:
                m = A[i]
    best_score = min(best_score, cost)
print(best_score)

Submission status: Accepted

Solution code:
import copy

n,m = map(int, input().split())
li = list(map(int, input().split()))

ans = 10**18
for i in range(2**n):
    check = [0]*n
    
    for j in range(n):
        if ((i >> j) & 1):
            check[n - j - 1] = 1

    if sum(check) < m:
        continue
    
    li_copy = copy.copy(li)
    tmp_ans = 0
    
    for x in range(n):
        if x == 0:
            continue
        if check[x] == 0:
            continue
        
        s = max(li_copy[0:x])
        t = li_copy[x]

        if s >= t:
            tmp_ans += s - t + 1
            li_copy[x] = s + 1
    ans = min(ans, tmp_ans)
    
print(ans)

Submission status: Accepted

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

from itertools import combinations as com

folds = com(range(N), K)
ans = float('inf')
for fold in folds:
    B = A[:]
    tmp = 0
    for i in range(1, K):
        if B[fold[i]] <= B[fold[i-1]]:
            diff = B[fold[i-1]] - B[fold[i]] + 1
            tmp += diff
            B[fold[i]] += diff

    k = 1
    border = B[0]
    for i in range(1, N):
        if border < B[i]:
            k += 1
            border = B[i]

    if k >= K:
        ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    buildings = list(map(int, input().split()))

    ans = float('inf')
    for i in range(2 ** n):
        res = 0
        cnt = 1
        prev_build = buildings[0]
        # 高くするビルをbitで管理
        for j in range(1, n):
            if (i >> j) & 1:
                cnt += 1
                if prev_build >= buildings[j]:
                    res += prev_build - buildings[j] + 1
                    prev_build += 1
                else:
                    prev_build = buildings[j]
            else:
                if prev_build < buildings[j]:
                    cnt += 1
                    prev_build = buildings[j]

        if cnt >= k:
            ans = min(ans, res)

    print(ans)       

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = float('inf')
for i in range(2 ** n):
    res = 0
    cnt = 1
    prev_build = buildings[0]
    # 高くするビルをbitで管理
    for j in range(1, n):
        if (i >> j) & 1:
            cnt += 1
            if prev_build >= buildings[j]:
                res += prev_build - buildings[j] + 1
                prev_build += 1
            else:
                prev_build = buildings[j]
        else:
            if prev_build < buildings[j]:
                cnt += 1
                prev_build = buildings[j]

    if cnt >= k:
        ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
ans=10**30
if m==0:
  print(0)
  exit()
for i in itertools.combinations(range(1,n),m-1):
  s=list(i)
  mx=a[0]
  cost=0
  for j in range(1,n):
    if j in s:
      if a[j]>mx:
        mx=a[j]
        continue
      else:
        cost+=mx+1-a[j]
        mx+=1
    mx=max(mx,a[j])
  ans=min(cost,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 10 ** 12
    for p in product((0, 1), repeat=n - 1):
        max_h = a[0]
        visible = 1
        cost = 0
        for i in range(1, n):
            if a[i] > max_h:
                max_h = a[i]
                visible += 1
            elif p[i - 1]:
                cost += max_h + 1 - a[i]
                max_h += 1
                visible += 1
        if visible < k:
            continue
        ans = min(ans, cost)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
from itertools import combinations
ans = float("inf")
for c in combinations(range(n), k):
    c = sorted(c)
    val = 0
    m = -1
    for i in range(n):
        if i in c:
            if m>=a[i]:
                val += (m+1)-a[i]
                m = m + 1
            else:
                m = a[i]
        else:
            m = max(m, a[i])
#     print(val, c)
    ans = min(ans, val)
print(ans)

Submission status: Accepted

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

money = 10**20

for i in range(2**n):
    cnt = 0
    b = a[:]
    max_b = b[0]
    for j in range(1, n):
        max_b = max(max_b, b[j])
        if i >> j & 1:
            cnt += max_b - b[j] + 1
            b[j] = max_b + 1
            max_b = b[j]
    col = 1
    m = b[0]
    for j in range(1, n):
        if b[j] > m:
            col += 1
            m = b[j]
    if col >= k:
        money = min(money, cnt)

print(money)

Submission status: Accepted

Solution code:
N, K = [int(i)for i in input().split()]
A = [int(i) for i in input().split()]

#%%
ans = float("inf")
for b in range(2 ** (N - 1)):
    cnt = 0
    cost = 0
    height = A[0]
    for i in range(N - 1):
        if height - A[i + 1] < 0:
            cnt += 1
            height = A[i + 1]
        elif (b >> i) & 1:
            cnt += 1
            cost += height - A[i + 1] + 1
            height += 1
    if cnt + 1 >= K:
        ans = min(ans, cost)

print(ans)

Submission status: Accepted

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

ans = float("INF")
for i in range(1 << n):
    h = 0
    cost = 0
    count = 0
    for j in range(n):
        if j != 0:
            h = max(h, a[j - 1])
        if i >> j & 1:
            if h < a[j]:
                h = a[j]
                count += 1
            else:
                h += 1
                cost += h - a[j]
                count += 1
    if count >= k:
        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**18
for i in range(1<<N):
    cnt = 0
    tot = 0
    now = 0
    for j in range(N):
        if A[j] > now:
            cnt += 1
            now = A[j]
        elif i&(1<<j):
            cnt += 1
            tot += now-A[j]+1
            now += 1
    if cnt >= K:
        ans = min(ans, tot)
print(ans)

Submission status: Accepted

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

import itertools
l=[i for i in range(1,N)]
Arr=list(itertools.combinations(l,K-1)) #Lの中から2個

#print(Arr)

ans=10**12
for i in Arr:
    cost=0
    hight=L[0]
    for j in range(1,N):
        if j in i:
            if hight<L[j]:
                hight=L[j]
            else:
                cost+=(hight-L[j]+1)
                hight+=1
        else:
            hight=max(hight,L[j])
    if ans>cost:
        ans=cost
print(ans)

Submission status: Accepted

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

ans = float('inf')
for key in range(1 << N):
    if bin(key).count('1') < K:
        continue
    cost = 0
    height = 0
    for i in range(N):
        if not (key & (1 << i)):
            height = max(A[i], height)
            continue
        height = max(A[i], height+1)
        cost += height - A[i]
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, K = getNM()
A = getList()

N_a = K - 1
root = N - 1

def judge(array):
    A_alta = copy.deepcopy(A)
    highest = A_alta[0]
    cnt = 0
    for i in range(1, N):
        if i in array and A_alta[i] <= highest:
            cnt += highest - A_alta[i] + 1
            A_alta[i] = highest + 1
            highest = A_alta[i]
        if A[i] > highest:
            highest = A[i]
    return cnt

ans = float('inf')
def comb_pow_2(i, array):
    global ans
    if i == N_a:
        ans = min(ans, judge(array))
        return
    # ここの4を変えてrootを変更
    last = 0
    if len(array) > 0:
        last = array[-1]

    for j in range(last + 1, root + 1):
        new_array = array + [j]
        comb_pow_2(i + 1, new_array)
comb_pow_2(0, [])
print(ans)