AOJ 1271 Power Calculus

反復深化dfsは始めて使いました。

Power Calculus (ICPC Asia 2006 F)

問題

数$1$から始めて、数字を作っていく。以下の操作が許される。

• 今までに数$a$と数$b$を作っているとき、
  • 数$a+b$を作る。
  • 数$a-b$ ($a-b \ge 1$)を作る。

数$n$ ($n \le 1000$)は最短何回の操作で作れるか。

解法

入力が1000通りと少ないので、表を事前生成する。

事前生成には反復深化dfsを使った。 枝刈りがたくさん必要。

実装

table生成

• 手元で7分要した。
• set使うのやめたらまともな速度で動くようになった。
• used_lenの値に深い根拠はない。

#include <iostream>
#include <vector>
#include <array>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= (m); --(i))
#define repeat_reverse(i,n) repeat_from_reverse(i,0,n)
using namespace std;
constexpr int max_n = 1000;
constexpr int used_len = 2 * max_n;
bool iddfs(vector<int> & s, array<bool,used_len> & used, int mx, int depth, int n) {
    if (used[n]) return true;
    if (depth == 0) return false;
    if ((mx << depth) < n) return false;
    repeat_reverse (i,s.size()) {
        repeat_reverse (j,i+1) {
            for (int x : { s[i] + s[j], abs(s[i] - s[j]) }) {
                if (x <= 0 or used_len <= x) continue;
                if (used[x]) continue;
                used[x] = true;
                s.push_back(x);
                if (iddfs(s, used, max(mx, x), depth-1, n)) return true;
                s.pop_back();
                used[x] = false;
            }
        }
    }
    return false;
}
int iddfs(int n) {
    int depth = 0;
    while (true) {
        vector<int> s { 1 };
        array<bool,used_len> used = {};
        used[1] = true;
        if (iddfs(s, used, 1, depth, n)) break;
        depth += 1;
    }
    return depth;
}
int main() {
    repeat_from (n,1,max_n+1) {
        cout << iddfs(n) << endl;
    }
    return 0;
}

提出

#include <iostream>
using namespace std;
int table[] = { -1, 0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 6, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 7, 7, 6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 9, 8, 8, 8, 8, 7, 8, 8, 8, 8, 9, 8, 9, 8, 9, 9, 9, 8, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 9, 8, 9, 9, 9, 8, 9, 8, 8, 7, 8, 8, 9, 8, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 10, 9, 9, 9, 9, 9, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 10, 9, 10, 9, 10, 9, 10, 10, 10, 9, 10, 10, 10, 9, 10, 10, 10, 9, 10, 9, 10, 9, 9, 9, 9, 8, 9, 9, 9, 9, 10, 9, 10, 9, 10, 10, 10, 9, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10, 9, 10, 9, 9, 8, 9, 9, 10, 9, 10, 10, 10, 9, 10, 10, 11, 10, 11, 10, 10, 9, 10, 10, 11, 10, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 11, 10, 10, 10, 11, 10, 11, 11, 11, 10, 11, 10, 11, 10, 11, 10, 11, 10, 11, 10, 10, 10, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 11, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 10, 11, 10, 10, 10, 10, 9, 10, 10, 10, 10, 11, 10, 11, 10, 11, 11, 11, 10, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 11, 12, 11, 11, 10, 11, 11, 12, 11, 12, 11, 11, 10, 11, 11, 11, 10, 11, 10, 10, 9, 10, 10, 11, 10, 11, 11, 11, 10, 11, 11, 12, 11, 12, 11, 11, 10, 11, 11, 12, 11, 12, 12, 11, 11, 12, 12, 12, 11, 12, 11, 11, 10, 11, 11, 12, 11, 12, 12, 12, 11, 11, 12, 12, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 12, 11, 11, 11, 12, 11, 12, 12, 12, 11, 12, 11, 12, 11, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 11, 12, 11, 12, 11, 11, 11, 11, 11, 11, 10, 11, 11, 11, 11, 11, 11, 12, 11, 12, 11, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 11, 12, 11, 11, 11, 11, 10, 11, 11, 11, 11, 12, 11, 12, 11, 12, 12, 12, 11, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 12, 12, 12, 12, 11, 12, 12, 12, 12, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 12, 12, 12, 13, 12, 13, 12, 12, 12, 13, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 13, 12, 12, 12, 13, 12, 13, 12, 12, 12, 13, 12, 13, 12, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 12, 13, 12, 13, 12, 13, 12, 13, 12, 13, 12, 13, 12, 13, 13, 13, 12, 13, 13, 13, 12, 13, 12, 13, 12, 13, 13, 13, 12, 13, 13, 13, 12, 13, 12, 13, 12, 12, 12, 13, 12, 13, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 12, 13, 12, 12, 12, 12, 12, 13, 12, 13, 13, 13, 12, 13, 13, 13, 12, 13, 12, 12, 11, 12, 12, 13, 12, 13, 13, 13, 12 };
int main() {
    while (true) {
        int n; cin >> n;
        if (n == 0) break;
        cout << table[n] << endl;
    }
    return 0;
}