TCO13 Round2B

TopCoder

今さらながら一応書いておくことに。

  • -

250. FruitTrees

問題：りんごをx間隔、キウイをy間隔、ぶどうをz間隔で植えるとき、異なるフルーツの最小距離の最大値は？

  • 各パラメータが2000以内
  • りんごの位置を固定し、キウイの位置とぶどうの位置の全探索を考える。
  • が、各フルーツの位置を決めたときの距離を定数時間で出す方法が分からず…。
  • 2つの距離に絞って考えれば最大距離はgcd以上にはならない
  • 位置aにりんご、位置bにキウイがあれば、最小距離は(b-a)%gcd(x,y)かx-(b-a)%gcd(x,y)
  • で、全探索したら通った
class FruitTrees {
private:
    int gcd(int a, int b){
        return a%b ? gcd(b, a%b) : b;
    }
public:
    int maxDist(int apple, int kiwi, int grape) {
        int res = 0;
        int ab = gcd(apple, kiwi);
        int bc = gcd(kiwi, grape);
        int ca = gcd(grape, apple);
        for(int b=0;b<kiwi;b++){
            for(int c=0;c<grape;c++){
                int d = min(b%ab, (apple-b+ab)%ab);
                d = min(d, min(c%ca, (apple-c+ca)%ca));
                int nc = (c-b+kiwi)%kiwi;
                d = min(d, min(nc%bc, (kiwi-nc+bc)%bc));
                res = max(res, d);
            }
        }
        return res;
    }
};

500. ScotlandYard

問題：タクシー、バス、地下鉄の交通網が与えられる。移動手段の系列から現在地が特定されないように移動するとき、特定されるまでor移動できなくなるまでの最大ステップ数は？

  • まるで分からず、2^50に賭けるしかないのか…と思ってたら終わった。
  • 解法が凄い賢かったので悔しい。
  • -

結果：AC / -- / -- ，+0, 180.75 pt, 185位
レーティング：2402 -> 2399


今回の反省は500解きたかったぜ…という点に尽きます。
同じ部屋に250を式一発で出してた人がいたのはシビれました。