square869120Contest #4 B - Buildings are Colorful!(精選14）

精選を順番に解いています。
bit全探索も大詰めに来ました。

問題と考察

色の違うビルが直線上に並んでいます。
うしろのビルは，前のビルよりも高くないと見えません。

正面から見てK色以上の色が見えるようにするためにビルの高さを変えるためのコストの最小値を求めます。

B - Buildings are Colorful!

bit全探索の応用範囲の広さを感じさせる問題です。
Nの制約が小さいときはbit全探索ができないかまず考えてみるとよさそうです。

もっとも最初は選んでないビルの高さの影響を考えずにWAしてしまいました。
途中に選んでいない高いビルがあると当然その後ろはより高くしなければなりません。
最終結果に影響がでるパターンは限られていてWAしたのは１ケースだけでした。
なかなかWAの原因がわからなかったです。

WAしたコード

#include <bits/stdc++.h>
using namespace std;
long long height[20];

int main(){
  //入力
  int n,k;
  cin>>n>>k;

  for(int i=0;i<n;i++){
    cin>>height[i];
  }
  //bit全探索
  long long temp=0;
  long long minsum=100000000000;
  long long sum=0;
  
  for(int i=0;i<(1<<n);i++){
    int cnt=0;
    temp=height[0];
    if(i &(1<<0)){
    sum=0;
    for(int j=1;j<n;j++){
      if(i &(1<<j)){
        cnt++;
        if(height[j]<=temp){
          sum+=(temp-height[j]+1);
         temp++;
        }
        else{
          temp=height[j];
        }
      }
    }
    if(cnt>=k-1){
      minsum=min(minsum,sum);
    }
    }
  }
  cout<<minsum<<endl;
  return 0;
}

考察

j番目のビルまでの高さの最高値を配列で持ち参照しながら比較するように改善しました。

ACしたコード

#include <bits/stdc++.h>
using namespace std;
long long height[20];
long long maxheight[20];

int main(){
  //入力
  int n,k;
  cin>>n>>k;

  for(int i=0;i<n;i++){
    cin>>height[i];
    maxheight[i]=max(maxheight[i-1],height[i]);
  }
  //bit全探索
  
  long long minsum=100000000000;
  long long sum=0;
  for(int i=0;i<(1<<n);i++){
    long long temp=height[0];
    int cnt=0;
    if(i &(1<<0)){
    sum=0;
    for(int j=1;j<n;j++){
      if(i &(1<<j)){
        cnt++;
        if(height[j]<=max(temp,maxheight[j-1])){
          sum+=(max(maxheight[j-1],temp)-height[j]+1);
          temp=max(maxheight[j-1],temp)+1;
        }
      }
    }
    if(cnt>=k-1){
      minsum=min(minsum,sum);
    }
    }
  }
  cout<<minsum<<endl;
  return 0;
}