SRM 492 div1 easy:TimeTravellingGardener

昔の easy は簡単(最初に考えた方針が間違えていて, しかもサンプルが無かったら絶対 WA してた)。

問題

TopCoder Statistics - Problem Statement

解法

n = (木の本数) とします。
まず, 答えが n-1 以下になることは明らかです。一番低い木に合わせて他の木を削れば良いので。

答えを n-2 以下にしたいとしましょう。その際, そのままの高さで残しておく可能性のある木の組 (i, j) を選べば, 直線が一意に定まります。なので後はこの直線に対して木の高さを調整すれば OK です。
ただ, 木の高さとしてありえないものがあった時は, その場合の (i, j) の組は採用できないので無視です。

class TimeTravellingGardener {
public:
    int determineUsage(vector <int> d, vector <int> h) {
        int n = h.size();
        int ret = n-1;
        vector<int> D(n);
        for (int i = 1; i < n; i++) D[i] = D[i-1]+d[i-1];
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int cnt = 0;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) continue;
                    int H = h[i]*(D[j]-D[i]) + (h[j]-h[i])*(D[k]-D[i]);
                    if (h[k]*(D[j]-D[i]) < H || H < 0) {
                        cnt = n;
                        break;
                    } else if (h[k]*(D[j]-D[i]) != H) cnt++;
                }
                ret = min(ret, cnt);
            }
        }
        return ret;
    }
};