Synthetic Kadomatsu

- [Synthetic Kadomatsu](https://atcoder.jp/contests/abc119/tasks/abc119_c)

## コンテスト中の考察

- Nの最大値が8。全探索か？でもパッと全探索する方法が思いつかない
- 逆手順を考えるやつかなー？A, B, Cからスタートして魔法を使い、与えられたN本の竹を生成するって感じに。でもめんどくさすぎるしよくわからない。N本の竹からA, B, Cを生成するのと労力は変わらなそう。
- DPかな？`dp[iまで見た][j本使った]`みたいな感じで。でも違うっぽい
- 結局は最大8本の竹を3本にする作業。なので、「Aに使う竹、Bに使う竹、Cに使う竹」の3つを列挙すれば良さそう。そして、それぞれの集合についてその竹を使うか使わないかを選ぶ。これでいけそう。
- 実装するコードがパッと思いついたので実装していく。「Aに使う竹、Bに使う竹、Cに使う竹」の列挙はDFSでできそう。それぞれの集合についてその竹を使うか使わないかは、ビット全探索で実装するのが楽そう。
- 実装していくわけなんだが、めちゃくちゃバグってしまい60分かけてACした。悲しい

### バグった箇所

#### 1.受け取った入力のNが8になってしまう

- プログラムにミスはない。入力するだけだし。なのにNが8になる。
- 原因がよくわからず、新しいファイルにソースコードをコピペしてコンパイルして実行したらNが正確に受け取れた。
- まじでなんなんだこれ。わけわからん

#### 2.DFSを普通に書き間違えた

- DFSは受け取った引数の状態から1手先がどうなるかを列挙すれば良い。あるidxをみたとき、それをAで使うかBで使うかCで使うかの3通りがある。なのでその3通りを列挙すればよかったんだけど、なんかidx~Nまで列挙する実装をしていた。
- 頭おかしいなこいつ。

```cpp
// 間違った実装
rec(int idx, vector<int> a, vector<int> b, vector<int> c) {
  for (int i = idx; i < N; i++) {
    a.push_back(l[i]);
    chmin(ret, rec(idx + 1, a, b, c));
    a.pop_back();
    
    b.push_back(l[i]);
    chmin(ret, rec(idx + 1, a, b, c));
    b.pop_back();
    
    c.push_back(l[i]);
    chmin(ret, rec(idx + 1, a, b, c));
    c.pop_back();
  }
}


// 正しい実装
rec(int idx, vector<int> a, vector<int> b, vector<int> c) {
  a.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  a.pop_back();

  b.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  b.pop_back();

  c.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  c.pop_back();
}
```

#### 3. ビット全探索の範囲を間違えた

- `for (int mask = 0; mask < (1 << n); mask++)`とするのが正しい
- 僕は`for (int mask = 0; mask < n; mask++)`としてしまっていた。これじゃ探索しきれない

#### 4. 「&」と「&&」を間違えた

- お前まじか。ありえん。アホなのかこいつ。悔い改めろ

#### 5. 合成コストを1にしてた

- 問題文を読め。こいつまじでなんなんだ。



## 解法

1. 「Aに使う可能性のある竹の集合」「Bに使う可能性のある竹の集合」「Cに使う可能性のある竹の集合」を列挙する。これはDFSで実装した。
2. 列挙したそれぞれの集合について、使うか使わないかを列挙して計算する。これはビット全探索で実装した

- 集合列挙のDFSは$O(3^N)$。使うか使わないかの列挙は$O(2^NN)$。よって全体の計算量は$O(3^N2^NN)$。N=8の時計算ステップは約$10^7$回なので間に合う。



## [コード](https://atcoder.jp/contests/abc119/submissions/4381782)

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

const int INF = 1e18;

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

// 「使用する可能性のある竹の集合」と「目標の長さ」を渡すと、目標の長さにするための最小コストを返してくれる
int calc2(vector<int> v, int val) {
  int ret = INF;
  int n = v.size();

  // 竹の集合の使い方を全列挙
  for (int mask = 0; mask < (1LL << n); mask++) {
    int cnt = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
      if (mask & (1LL << i)) {
        sum += v[i];
        cnt++;
      }
    }
    if (cnt == 0) continue;
    chmin(ret, (cnt-1)*10 + abs(sum - val));
  }

  return ret;
}

// Aに使う竹、Bに使う竹、Cに使う竹の集合を渡すと、それぞれの目標の高さにするまでの最小コストを返してくれる
int calc(vector<int> a, vector<int> b, vector<int> c) {
  return calc2(a, A) + calc2(b, B) + calc2(c, C);
}

// 「Aに使う可能性のある竹の集合」「Bに使う可能性のある竹の集合」「Bに使う可能性のある竹の集合」を全列挙
int rec(int idx, vector<int> a, vector<int> b, vector<int> c) {
  if (idx >= N) {
    if (a.size() == 0 || b.size() == 0 || c.size() == 0) return INF;
    return calc(a, b, c);
  }

  int ret = INF;

  // idx番目の竹ををAに使う
  a.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  a.pop_back();

  // idx番目の竹ををBに使う
  b.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  b.pop_back();

  // idx番目の竹ををCに使う
  c.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  c.pop_back();

  return ret;
}

signed main() {
  cin >> N >> A >> B >> C;
  l.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> l[i];
  }

  vector<int> a;
  vector<int> b;
  vector<int> c;
  int ans = rec(0, a, b, c);

  cout << ans << endl;

  return 0;
}
```





## もっと簡単に実装する

- 僕は「Aに使う可能性がある竹」、「Bに使う可能性がある竹」、「Cに使う可能性がある竹」を列挙した。そして、それぞれの集合について使うか使わないかを列挙した。
- 僕の考え方では実装がだるくなる。けど、ちょっと考え方を変えるだけで実装が楽になる。

### 考え方

- 「Aに使う竹」、「Bに使う竹」、「Cに使う竹」、「使わない竹」を列挙する。
- これをすると、「Aに使う可能性がある竹」を列挙した後にその集合のどの竹を使うか？という処理を書かなくて済む。
- 天才
- 計算量は$O(4^N)$。N=8のとき計算ステップは65536回なので余裕で間に合う。

### [コード](https://atcoder.jp/contests/abc119/submissions/4381966)

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

const int INF = 1e18;

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

int rec(int idx, int a, int b, int c) {
  if (idx >= N) {
    if (a == 0 || b == 0 || c == 0) return INF;
    return abs(a - A) + abs(b - B) + abs(c - C);
  }

  int ret = INF;
  // A
  chmin(ret, rec(idx+1, a+l[idx], b, c) + (a > 0 ? 10 : 0));
  // B
  chmin(ret, rec(idx+1, a, b+l[idx], c) + (b > 0 ? 10 : 0));
  // C
  chmin(ret, rec(idx+1, a, b, c+l[idx]) + (c > 0 ? 10 : 0));
  // 使わない
  chmin(ret, rec(idx+1, a, b, c));

  return ret;
}

signed main() {
  cin >> N >> A >> B >> C;
  l.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> l[i];
  }

  int ans = rec(0, 0, 0, 0);

  cout << ans << endl;

  return 0;
}
```

## 自分が本番で書くとしたらこんなコード（追記）

- 「もっと簡単に実装する」で実装したコード、本番では多分かけない。あれ結構頭のいい再帰なので
- 自分が本番で書くとしたらこんな感じになると思う
- 再帰にvector渡すのやばそう（速度とかスタックオーバーフローとか）。参照にして提出したら早くなった（このコードは参照にしてないけど）

### [コード](https://atcoder.jp/contests/abc119/submissions/4390573)

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

const int INF = 1e18;

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

// Aに使う竹の集合、Bに使う竹の集合、Cに使う竹の集合を渡すと、作りたい竹にするのにかかるコストを返してくれる
int calc(vector<int> a, vector<int> b, vector<int> c) {
  int aRes = abs(accumulate(all(a), 0LL) - A) + ((a.size()-1) * 10);
  int bRes = abs(accumulate(all(b), 0LL) - B) + ((b.size()-1) * 10);
  int cRes = abs(accumulate(all(c), 0LL) - C) + ((c.size()-1) * 10);

  return aRes + bRes + cRes;
}

int rec(int idx, vector<int> a, vector<int> b, vector<int> c) {
  if (idx >=  N) {
    if (a.size() == 0 or b.size() == 0 or c.size() == 0) return INF;
    return calc(a, b, c);
  }

  int ret = INF;

  // idx番目の竹をAに使う
  a.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  a.pop_back();

  // idx番目の竹をBに使う
  b.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  b.pop_back();

  // idx番目の竹をCに使う
  c.push_back(l[idx]);
  chmin(ret, rec(idx+1, a, b, c));
  c.pop_back();

  // idx番目の竹を使わない
  chmin(ret, rec(idx+1, a, b, c));

  return ret;
}

signed main() {
  cin >> N >> A >> B >> C;
  l.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> l[i];
  }

  vector<int> a;
  vector<int> b;
  vector<int> c;
  cout << rec(0, a, b, c) << endl;

  return 0;
}
```




## 要点

- 最大8本の竹を3本にするっていうことに気づくのが大事だったと思う。
  - 8本のうち、どれかは3本の竹に使うとする。本当に使うかどうかは後で考えればいい。
  - これに気づいて全探索の方法が思いついた。
- DFSで「使わない」場合も列挙する
  - これ、結構書いてきたはずなんだけど思いつかなかった。悲しい。
- 「and」を使うと良い？
    - 「&」と「&&」を間違えないためにも「&&」ではなく「and」を使うと良さげ



## メモ

- [けんちょんさんの記事](http://drken1215.hatenablog.com/entry/2019/02/24/224100)。考えがうまいこと言語化されててすごい