問題の分析
N本の一直線に並んだ木があり、それぞれの高さheightと間隔distanceが与えられます。
各木の高さは自由に縮められます。整数でなくてもよいです。
各木の頂点を一直線に並べるために必要な、木を縮める操作の回数の最小値を求めなさい。
方針
木の頂点をX,Y座標上の頂点を見なし、すべての二頂点の組み合わせについて二頂点を結ぶ直線上に頂点がいくつ乗るかを調べます。
その直線がすべての木の地面から頂点の間を通ることを確認します。
上記の条件が満たされなければその直線上にすべての頂点を並べることは出来ないからです。
ソースコード
canColinear関数の中でdouble型での演算をしていますが、最初は丸め誤差のため不具合が出ました。
doubleを使う場合は誤差に気をつけないといけませんね。何桁目で四捨五入するべきかがわかってないのですが。。
あと、一次関数の扱い(ある点が直線上に乗ってるかどうかの判定など)がすぐできなくて焦りました。数学勉強し直さないとだめですね。。
using System; using System.Collections.Generic; using System.Text; public class TimeTravellingGardener { public int determineUsage(int[] distance, int[] height) { int n = height.Length; int[] x = new int[n]; int[] y = height; x[0] = 0; for (int i = 1; i < n; i++) x[i] = x[i - 1] + distance[i - 1]; int min = n - 1; for(int i = 0;i < n;i++) for (int j = i + 1; j < n; j++) { int colinear = 0; for (int k = 0; k < n; k++) { if (k != i && k != j) { if (isColinear(x[i], x[j], x[k], y[i], y[j], y[k])) colinear++; if (!canColinear(x[i], x[j], x[k], y[i], y[j], y[k])) { colinear = -1; break; } } } min = Math.Min(min, n - 2 - colinear); } return min; } private bool isColinear(int x1, int x2, int x3, int y1, int y2, int y3) { return (y1 - y3) * (x3 - x2) == (y3 - y2) * (x1 - x3); } private bool canColinear(double x1, double x2, double x3, double y1, double y2, double y3) { double y = (y2 - y1) / (x2 - x1) * (x3 - x1) + y1; y = Math.Round(y, 6); return 0 <= y && y <= y3; } }