TCO2013のRound2B、参加してEasyも解けていたのにここに書き忘れていたので書いておく。
http://community.topcoder.com/stat?c=problem_statement&pm=12520
問題
1直線の道の上に、リンゴ、キウィ、ブドウの木が植えられている。
リンゴは、ある整数座標Xに対し、X-2*apple、X-apple、X、X+apple、X+2*appleのように、距離appleの間隔で並んでいる。
キウィも同様に整数座標Yから距離kiwiの間隔、ブドウの木は整数座標Zから距離grapeの間隔で並んでいる。
各木の最短間隔が最大となるようにし、その値を答えよ。
解法
3つの木だとややこしいので、まずはリンゴとキウィの2つを考える。
仮にX=Yの時、Xからappleとwiki最小公倍数の距離のでは重なるが、それ以外では距離の最短間隔はgcd(apple,kiwi)である。
よって、XとYをずらしたとき、A=gcd(apple,kiwi)とすると最小距離はmin*1%A)のいずれかである。
3つの木だと上記処理を2種類の木ごと3ペアについて行う必要がある。
ここで、apple,kiwi,grapeは高々2000なので、X=0と固定し、YとZを0～2000で動かしながら、3つのペアについて最小距離を求めればよい。
ll gcd(ll a, ll b) { return (b==0)?a:gcd(b,a%b);}
class FruitTrees {
public:
int maxDist(int A, int K, int G) {
int g1=gcd(A,K);
int g2=gcd(A,G);
int g3=gcd(K,G);
int ma=0;
int i,j;
FOR(i,max(max(A,K),G)+1) { // K
FOR(j,max(max(A,K),G)+1) { // G
int mi1=min(i%g1,(g1-(i%g1))%g1);
int mi2=min(j%g2,(g2-(j%g2))%g2);
int dis=(((i-j)%g3)+g3)%g3;
int mi3=min(dis,(g3-dis)%g3);
ma=max(ma,min(min(mi1,mi2),mi3));
}
}
return ma;
}
}
まとめ
一見難しそうで、実はgreedyでいい問題。
*1:Y-X)%A , (A-(Y-X
