問題
http://community.topcoder.com/stat?c=problem_statement&pm=12055&rd=14739
柱が２つ与えられる。柱の間の距離はｗ。
２つの柱の最大の長さｘ、ｙが与えられ、１～ｘ、１～ｙの間で好きに決めることができる。
最後に、柱のてっぺんをロープで結び、その長さの平均値を求める。
解き方
ｘ、ｙが１０＾５のため、全探索で解くことはできない。
２つの柱の差の数は、２つの求め方がある。
１）ｘ、ｙから計算式を求めて一意に決定
２）ｘのみ１～ｘまで変化させ、それぞれに対しとりうる値を区間で求める。
今回は２の方法でコーディングしました。
１つエラーではまった原因としては、iをint型で計算したため数が大きい場合にエラーになってしまいました。
「計算は全て型を一致させる」、という基本を忘れないようにします。
ちなみに１の場合は、長さのとりうる値１－ｘからｙ－１までループさせ、
i<=０のときはmin(y,x+i)
i>0のときはmin(x,y-i)分だけその長さが存在することになります。
コード
class Pillars {
public: double getExpectedLength(int w, int x, int y) {
if(x>y)swap(x,y);
double ret=w*x;
for(int len=1;len<=y-1;len++){
int cnt=max(0,min(x,y-len))+max(0,min(x-len,y));
ret+=cnt*sqrt((double)len*len+w*w);
}
return ret/x/y;
}
};
public: double getExpectedLength(int w, int x, int y) {
if(x>y)swap(x,y);
double ret=w*x;
for(int len=1;len<=y-1;len++){
int cnt=max(0,min(x,y-len))+max(0,min(x-len,y));
ret+=cnt*sqrt((double)len*len+w*w);
}
return ret/x/y;
}
};
using namespace std;
#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 Pillars {
public:
double getExpectedLength(int w, long long x, long long y) {
double ret=0;
if(x>y)swap(x,y);
double dp[y];
dp[0]=0;
for(long long i=1;i<y;i++)dp[i]=dp[i-1]+sqrt((double)(w*w+i*i));
for(long long i=1;i<=x;i++)ret+=dp[i-1]+dp[y-i]+w;
return ret/x/y;
}
};
#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 Pillars {
public:
double getExpectedLength(int w, long long x, long long y) {
double ret=0;
if(x>y)swap(x,y);
double dp[y];
dp[0]=0;
for(long long i=1;i<y;i++)dp[i]=dp[i-1]+sqrt((double)(w*w+i*i));
for(long long i=1;i<=x;i++)ret+=dp[i-1]+dp[y-i]+w;
return ret/x/y;
}
};