square869120Contest #4-B：Buildings are Colorful!

問題

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

N つの建物がある。それぞれ i 番目の建物は色 i で塗られており、高さは a_i である。左から見たときに K 色以上の建物が見えるようにしたい。

いくつかの建物の高さを増やすことによって K 色以上見えるようにするとき、建物の高さを増やす最小値を求めよ。

「建物が見える」とは a_j >= a_i (j < i) なる j が存在しないことである。

制約

  • 1 <= K <= N <= 15
  • 1 <= a_i <= 109

考え方

制約から {a_N} について 2N で全探索することができることがわかる。k ビット目が 1 である建物を見えるようにすることとする。

建物 a_i が見えるということは、0 < j < i なる a_j の最大値よりも a_i が大きくなければならない。 k ビット目が 1 である建物について、それまでの最大値よりも大きくなるように高さ a_k を更新していき、増加した高さの最小値を求めれば良い。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), k = in.nextInt();
            long[] a = in.nextLongArray(n);

            long ans = LINF;
            for (int i = 0; i < 1 << n; i++) {
                if (Integer.bitCount(i) < k) continue;

                long[] b = a.clone();
                long max = 0, tmp = 0;

                for (int j = 0; j < n; j++) {
                    if ((i >> j & 1) == 1) {
                        if (max >= b[j]) {
                            tmp += max - b[j] + 1;
                            b[j] = max + 1;
                        }
                    }
                    max = max(max, b[j]);
                }

                ans = min(ans, tmp);

            }
            out.println(ans);
        }

ポイント

  • 最大値を保持しておく

類題