mayoko’s diary

プロコンとかいろいろ。

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;
    }
};