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か。

という具合。