AtCoder Beginner Contest 119 C Synthetic Kadomatsu

制約を見て察するやつ

C Synthetic Kadomatsu

問題

atcoder.jp

問題概要

の竹 を使い、長さ cm の竹を作りたい。
このとき 本の竹に以下の操作(魔法)を括弧内のコスト(単位 MP)を使用することで行える。

• 延長魔法: cm竹を伸ばす。(1 MP)
• 短縮魔法: cm竹を短くする。(1 MP)
• 合成魔法: 本の竹をくっつけて 本にする。(10 MP)

cm の竹を作るときに必要な最小のMPのコストを求めよ。

考察

目標の竹 () をどの竹から作るかを考えます。

例えば のとき、竹 を以下の竹から作ることにします。

この場合のコストは、

(Aは1回合成魔法を使っているので +10, 残りは目標の竹の長さとの絶対値を取ったぶんだけMPを使って延長or短縮する)

になります。

このように目標の竹をどの竹から作るかを全て試せば答えが求められそうです。

しかし、 に竹を2本選んで... には3本竹を使用して... のように全部の状態を列挙するといっても考慮することが多そうです。

とりあえず 本の竹を1列に並べて左から順番に に使用する竹を選んでいきましょう。

前提として目標の竹を生成するためには最低でも 本の竹が必要です。

よって、 つの竹を生成するために 本以上の竹を使用してはいけません。

例えば のとき 本の竹を生成するのに ] の範囲で竹を使用することができます。

下図ではそのうち3本を使用して を作ることにします。

残った竹は 本です。 本のうちから を作る竹を選びます。

のために最低 本の竹を残しておく必要があるので に使えるのは ] の範囲です。

下図では のために2本竹を選びました。

最後に残った竹で を生成します。

このように使用する竹を制約に気をつけながら、左から順に に割り当てていきます。
これは単純な3重ループで実装することができます。

後は 数列 のを並び替えた全てのパターンをこの方法に当てはめるだけです。

C++では全ての順列を生成する std::next_permutation というライブラリを使用することでこれが達成できます。

#include <std/bitsc++.h>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define sorti(x) sort(x.begin(), x.end())

int main() {
  int n,c,b,a;
  cin >> n >> a >> b >> c;

  // 1つの竹を作るのに使用できる最大数
  int use = n - 2;

  vector<ll> l(n);
  rep(i,n) {
    cin >> l[i];
  }

  ll ans = INF;
  
  // next_permutaionを使用するには対象のコンテナを昇順にソートしておく必要がある。
  sorti(l);
  do {
    int limitb, limitc;
    
    // 左からAに割り当てる竹を [1, N-2] の間で選ぶ
    for (int i = 0; i < use; ++i) {
      ll tmpa = 0, tmp = 0;
      ll a1 = l[0];
      
      // 2本以上あるときは合成魔法を使用するので cost += 10
      for (int t = 1; t <= i; ++t) {
        a1 += l[t];
        tmpa += 10;
      }

      // 延長 or 短縮魔法のコスト計算
      tmpa += abs(a - a1);
      
      // Bに使用できる竹の最大値計算
      limitb = (n - (i+1) == 2) ? 1 : (n - (i+1) - 1);
      for (int j = i + 1; j <= i + limitb; ++j) {
        ll b1 = l[i+1], tmpb = 0;
        for (int t = i+2; t <= j; ++t) {
          b1 += l[t];
          tmpb += 10;
        }

        tmpb += abs(b - b1);
        
        // Cに使用できる竹の最大値計算
        limitc = (n - (j + 1) == 1) ? 1 : n - (j + 1);
        for (int k = j+1; k <= j + limitc; ++k) {
          ll c1 = l[j+1], tmpc = 0;
          for (int t = j+2; t <= k; ++t) {
            c1 += l[t];
            tmpc += 10;
          }

          tmpc += abs(c - c1);

          // 小さかったら更新
          ans = min(ans,tmpa + tmpb + tmpc);
        }
      }
    }
  } while (next_permutation(l.begin(), l.end()));

  cout << ans << endl;
}

---

next_permutationの計算量は O(N!) だけど、制約が n <= 8 だから十分に間に合う。
これ難しいね。