2013 TCO Round 2B Easy - FruitTrees (×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12520&rd=15633
・appleとkiwi、grapeがあり、それぞれ与えられた間隔で一定に置いていく。
・このとき、２つの果物間の最短距離が最も大きくなるような並べ方のときの
最短距離を求める。
解き方
・３つ果実があると複雑そう。
・appleの距離が４、kiwiの距離が３のとき、と考えるとどう置いても重なる・・うまく見つからない。
→他の人のコードをみてみる
・もう少し洞察してみると、２つの果実の距離のgcdのMODが最短距離となる。
・よって、appleを固定し、kiwiとgrapeを変化させそのときの最短距離を求めればよい。
・反省：紙に書いてもっと検討・試行錯誤してみることが必要。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FruitTrees {
public:
int gcd(int x,int y){
return y ? gcd(y,x%y) : x;
}
int maxDist(int apple, int kiwi, int grape) {
int g1=gcd(apple,kiwi);
int g2=gcd(apple,grape);
int g3=gcd(kiwi,grape);
int ret=0;
FORE(i,0,2001)FORE(j,0,2001){
int tmp=1e+9;
tmp=min(tmp,min(i%g1,(g1-i%g1)%g1));
tmp=min(tmp,min(j%g2,(g2-j%g2)%g2));
int d=(g3+(i-j)%g3)%g3;
tmp=min(tmp,min(d,(g3-d)%g3));
ret=max(ret,tmp);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FruitTrees {
public:
int gcd(int x,int y){
return y ? gcd(y,x%y) : x;
}
int maxDist(int apple, int kiwi, int grape) {
int g1=gcd(apple,kiwi);
int g2=gcd(apple,grape);
int g3=gcd(kiwi,grape);
int ret=0;
FORE(i,0,2001)FORE(j,0,2001){
int tmp=1e+9;
tmp=min(tmp,min(i%g1,(g1-i%g1)%g1));
tmp=min(tmp,min(j%g2,(g2-j%g2)%g2));
int d=(g3+(i-j)%g3)%g3;
tmp=min(tmp,min(d,(g3-d)%g3));
ret=max(ret,tmp);
}
return ret;
}
};
