2013 TCO Algorithm Round 2B easy: FruitTrees
解法
まず, りんごの木の位置は 0 に固定しても問題ないです。他の 2 つの初期位置を動かしましょう。これで O(n^2) みたいな感じになるので, あとは O(1) で木の最小距離 x を求められるようにしたいです。
りんごとキウィの距離の最小値は, ak = gcd(apple, kiwi) として, min(x%ak, ak-x%ak) となります。他の木の組み合わせも同様にして最小距離を求めます。
class FruitTrees { public: int maxDist(int apple, int kiwi, int grape) { int ak = __gcd(apple, kiwi), kg = __gcd(kiwi, grape), ga = __gcd(grape, apple); int ret = 0; for (int k = 0; k < kiwi; k++) for (int g = 0; g < grape; g++) { int x = 100000; int tmp = min(k%ak, ak-k%ak); x = min(x, tmp); tmp = min(g%ga, ga-g%ga); x = min(x, tmp); tmp = (g-k)%kg + kg; tmp = min(tmp%kg, kg-tmp%kg); x = min(x, tmp); ret = max(ret, x); } return ret; } };