square869120Contest#4B - Buildings are Colorful!

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

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

方針

全探索によってどの建物が見えるようにするかを決めて、必要な費用を計算します。ある建物が見える条件は、それより左にある建物の高さの最大値より1大きいことなので、左から線形に最大値を更新していけば良いです。

計算量は高々N_C_Kのパターンについて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 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)

記事情報

• 投稿日：2020年5月29日
• 最終更新日：2020年5月29日