2019-02-24

AtCoder ABC 119 C - Synthetic Kadomatsu (水色, 300 点)

AtCoder AtCoder300点 ABC-C 全探索全探索:ビット全探索最適化テク:操作の流れを単純化する操作最適化テク:解を変形していく(最適性を失わずに) 逆操作もvalid 最小コスト水色diff 指数探索系問題全探索:再帰関数全探索:再帰関数(ビット全探索困難) 典型要素を詰め合わせた教育的問題最適化問題

最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもなのん。。。
でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう！！！！！

大事なことを再認識させてくれる感じ。

問題へのリンク

問題概要

$N$ 個の整数列 $l_1, l_2, \dots, l_N$ が与えられ、以下の操作を繰り返すことで、整数列が 3 個の整数 $A, B, C$ を含むような状態にしたい。それを実現するのに必要な最小コストを求めよ。

整数の中から 1 つ選んで +1 する (コスト 1)
2 以上の整数の中から 1 つ選んで -1 する (コスト 1)
2 つの整数を選んで、消して、それらを合計したもので置き換える (コスト 10)

制約

$3 \le N \le 8$

考えたこと

珍しい！！！！！！！！！

現代の AtCoder では珍しい「全探索」な問題。ただし本当に全探索やるだけじゃなくて、以下のような考察要素もあることが AtCoder らしい:

「+1」や「-1」をする操作をするのは、「合体」を完全にやり切った後からでよい

なぜなら、

合体してから +1 や -1 する
合体前の段階で +1 や -1 する

とは同じ結果を生むからだ¹。

よって、やるべきことは以下の流れに。

合体してとにかく 3 本をまずは作り出すことを考える。その方法を全探索する。
あとはその 3 本の長さが a, b, c となったとき、A, B, C との差分をとって abs(a - A) + abs(b - B) + abc(c - C) が「+1」や「-1」をする総コストになる。

合体して 3 本を作り出す方法については、

再帰
bit 全探索を応用

とがある。それぞれ見てみる。

再帰による方法

$n$ 本の竹それぞれについて

A を作るための合体として採用する
B を作るための合体として採用する
C を作るための合体として採用する
特に合体を作るのに採用しない

という風に 4 種類の選択をすればよいことがわかる。その方法の数は $4^{n}$ 通りある。再帰的に解いていく。再帰関数の大枠としては、i を配列の index として、

int rec(int i, ~~~) {
  // 終端処理
  if (i == n) return ~;

  // i を進めながら、分岐処理
  int res = INF;
  chmin(res, rec(i + 1, 分岐 1));
  chmin(res, rec(i + 1, 分岐 2));
  chmin(res, rec(i + 1, 分岐 3));
  chmin(res, rec(i + 1, 分岐 4));

  return res;
}

という感じの再帰関数を書けば上手くいく感じ。細かいところは問題に応じて頑張る。今回は

rec(int i, int a, int b, int c)

として、

a: その時点での A に採用した竹の長さの総和
b: その時点での B に採用した竹の長さの総和
c: その時点での C に採用した竹の長さの総和

とするといい感じ (最初僕はもう少し複雑なことしていたが evima さんの解説を見ながらかなり整理した)。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
void chmin(int &a, int b) { if (a > b) a = b; }

int N, A, B, C;
vector<int> L;

// 再帰
int rec(int i, int a, int b, int c) {
    if (i == N) {
        if (!a || !b || !c) return INF; // A, B, C いずれも竹は 1 本は必ず使ってないとダメ
        return abs(a - A) + abs(b - B) + abs(c - C); // 合体してできた a, b, c を A, B, C にするコスト
    }

    // 今ある竹を採用しない場合
    int res = rec(i+1, a, b, c);
    
    // A, B, C を使う場合。
    // (a ? 10 : 0) とかは、最初の 1 本目は合体コストなし、2 本目からはコスト 10 かかることを意味する
    chmin(res, rec(i+1, a + L[i], b, c) + (a ? 10 : 0));
    chmin(res, rec(i+1, a, b + L[i], c) + (b ? 10 : 0));
    chmin(res, rec(i+1, a, b, c + L[i]) + (c ? 10 : 0));
    
    return res;
}

int main() {
    // 入力
    cin >> N >> A >> B >> C;
    L.resize(N);
    for (int i = 0; i< N; ++i) cin >> L[i];
    
    // 再帰する
    cout << rec(0, 0, 0, 0) << endl;
}

bit 全探索による方法

まず A に採用する竹を選んで
残りの中から B に採用する竹を選んで
その残りの中から C に採用する竹を選んで...

とすればよい。その実現方法として簡単なのは

for (int bit = 0; bit < (1<<n); ++bit) {
  for (int bit2 = 0; bit2 < (1<<n); ++bit2) {
    if (bit2 & bit) continue; // bit と bit2 が共通要素を持っていたらダメ
    for (int bit3 = 0; bit3 < (1<<n); ++bit3) {
       if (bit3 & bit) continue; // bit3 と bit が共通要素を持っていたらダメ
       if (bit3 & bit2) continue; // bit3 と bit2 が共通要素を持っていたらダメ

    }
  }
}

とする方法ではないかと思う。今回はこれでも十分間に合う。ただしより計算時間が厳しい問題の場合は、無駄なくきっちり $4^{n}$ 通りを列挙する方法の模索が必要になる。

$3^{n}$ な全探索をする方法はこの記事に書いてみた。でも個人的には $2^{n}$ なら bit 全探索でもよいが、それより複雑な処理になったら再帰で書くのが汎用性高くていいかな...という気がする。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int N;
vector<int> L;
vector<int> A; // A, B, C

int main() {
    cin >> N;
    A.resize(3);
    for (int i = 0; i < 3; ++i) cin >> A[i];
    L.resize(N);
    for (int i = 0; i < N; ++i) cin >> L[i];

    int res = 1<<29;
    vector<int> bit(3);
    for (bit[0] = 1; bit[0] < (1<<N); ++bit[0]) { // 0 は含めない
        for (bit[1] = 1; bit[1] < (1<<N); ++bit[1]) { // 0 は含めない
            // 共通要素あったらダメ
            if (bit[1] & bit[0]) continue;
            for (bit[2] = 1; bit[2] < (1<<N); ++bit[2]) { // 0 は含めない
                // 共通要素があったらダメ
                if (bit[2] & bit[0]) continue;
                if (bit[2] & bit[1]) continue;
                
                // sums: A〜C に選んだ竹の長さの合計、nums: A〜C に選んだ竹の本数
                vector<int> sums(3, 0), nums(3, 0);
                for (int i = 0; i < N; ++i) {
                    for (int j = 0; j < 3; ++j) {
                        if (bit[j] & (1<<i)) {
                            sums[j] += L[i];
                            nums[j]++;
                        }
                    }
                }

                // score を求める
                int score = 0;
                for (int i = 0; i < 3; ++i) {
                    score += abs(sums[i] - A[i]); // +1, -1 のコスト
                    score += (nums[i] - 1) * 10; // 合体のコスト
                }
                res = min(res, score);
            }
        }
    }
    cout << res << endl;
}