Search on the blog

2011年3月16日水曜日

SRM BrushUp: BestView (436 div2 Middle)

引き続き、SRMの復習。

n個のビルが等間隔に直線状に並んでいる。i番目のビルの高さをheights[i]とする。
あるビルの屋上からは、一番多くのビルの姿を見ることができる。そのビルから見ることのできるビルの数を求めよ。

ビルxからビルyが見えるためには、xからyを結ぶ直線より上にあるビルが区間(x, y)に無ければよい。
しかしここで注意。
x, yはintだが、普通に傾きを取って計算するとdoubleになる。

doubleとintの比較。。

これはNG。

例えば、
if (a1 + 1.*b/c *a2 <= d)
という式は、
if (a1*c + b *a2 <= d*c)
と書くのが鉄則。

あと、この問題では、掛け算した結果が10^10オーダーになるのでlong long intを使わないといけない。が、こんな引っかけにはもう引っかからない。

class BestView {
public:
int numberOfBuildings(vector<int> heights) {
int n = heights.size();
vector<long long int>h(n);

REP(i, n) h[i] = heights[i];
int ret = 0;
REP(i, n) {
int val = 0;
REP(j, n) if (i != j){
bool ck = true;
if (j < i) {
FOR (k, j+1, i)
if (h[i] * ABS(i-j) + (h[j] - h[i]) * ABS(k-i) <= h[k] * ABS(i-j)) ck = false;
} else {
FOR (k, i+1, j)
if (h[i] * ABS(i-j) + (h[j] - h[i]) * ABS(k-i) <= h[k] * ABS(i-j)) ck = false;
}
if (ck) ++val;
}
ret = max(ret, val);
}

return ret;
}
};
余談になるが、doubleの最大値、精度について、
  • 符号部 1bit
  • 仮数部 52bit
  • 指数部 11bit
なので、最大値は2^1024 ~ 10^300、精度は2^52 ~ 10^15くらい。
実はこのビット数は簡単に覚えられる。
まず、doubleは64bit。符号部が1bit必要。
指数部は切りの良い値にしたい。⇒1000くらいかな。でプラマイにふるから2000。2^11 ~ 2000だから指数部は11bit。
じゃ仮数部は、64-1-11=52bitか。
という具合。

0 件のコメント:

コメントを投稿