AOJ 1307 - Towns along a Highway

解法

こういうのは確定できるところからさせるもの。
とりあえず一番遠いところは unique に定まるので確定させる。
次は、残ってる d の中で最も大きい値を選ぶ。
こいつは、明らかに端のどっちかと最も遠い位置関係にあるはず。
どっちと遠いかは 2 通りあるが、n <= 20 なので両方試す全探索が可能。
その座標に置いたときに、すでに確定させた位置との相対距離の集合が、残ってる d の集合の部分集合であればOKで、一旦それを消して次の探索に移る。

ソースコード

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

int main() {
    int n;
    while(cin >> n, n) {
        multiset<int, greater<>> d;
        for(int i = 0; i < n * (n - 1) / 2; ++i) {
            int x; cin >> x;
            d.insert(x);
        }

        vector<int> cur = {0, *d.begin()}; // x position
        d.erase(d.begin());
        vector<vector<int>> ans;
        function<void(multiset<int, greater<>>&)> dfs = [&] (multiset<int, greater<>>& s) {
            if((int)cur.size() == n) { // ok
                ans.push_back({});
                for(int i = 1; i < n; ++i) {
                    ans.back().push_back(cur[i] - cur[i - 1]);
                }
                return;
            }
            auto attempt = [&] (int p) {
                vector<int> rm;
                for(auto x : cur) {
                    const auto it = s.lower_bound(abs(p - x));
                    if(it == end(s) || *it != abs(p - x)) break;
                    rm.push_back(*it);
                    s.erase(it);
                }
                if(rm.size() == cur.size()) {
                    cur.insert(lower_bound(begin(cur), end(cur), p), p);
                    dfs(s);
                    cur.erase(find(begin(cur), end(cur), p));
                }
                s.insert(begin(rm), end(rm));
            };
            attempt(*s.begin());
            attempt(cur.back() - *s.begin());
        };

        dfs(d);
        sort(begin(ans), end(ans));
        ans.erase(unique(begin(ans), end(ans)), end(ans));
        for(auto const& v : ans) {
            for(int i = 0; i < n - 1; ++i) {
                cout << v[i] << " \n"[i + 1 == n - 1];
            }
        }
        cout << "-----" << endl;
    }
}

感想

800点といわれて身構えてしまい、難しく考えすぎた。良くないね。
考察はわかりきったところから攻めていかないとなあ。