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点といわれて身構えてしまい、難しく考えすぎた。良くないね。
考察はわかりきったところから攻めていかないとなあ。