読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2013 Round2B Easy FruitTrees

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

広告を非表示にする