CODE FESTIVAL 2016 Final: B - Exactly N points

,

http://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_b

分からなくて焦ったのだが、なんとなく書いてみたら通った。

solution

上限を決め打ちして大きいものから貪欲に採用する。上限を二分探索すれば$O(\sqrt{N} \log{N})$だが、小さい方から順に試しても$O(N)$。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
vector<int> func(int n, int k) {
    vector<int> result;
    for (; k >= 1 and n != 0; k = min(k-1, n)) {
        if (n >= k) {
            n -= k;
            result.push_back(k);
        }
    }
    if (n) result.clear();
    return result;
}
int main() {
    int n; cin >> n;
    repeat (k,n+1) {
        vector<int> xs = func(n, k);
        if (not xs.empty()) {
            for (int x : xs) cout << x << endl;
            break;
        }
    }
    return 0;
}