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を使わないといけない。が、こんな引っかけにはもう引っかからない。

view plainprint?

1. class BestView {  
2. public:  
3.    int numberOfBuildings(vector<int> heights) {  
4.        int n = heights.size();  
5.        vector<long long int>h(n);  
6.   
7.        REP(i, n) h[i] = heights[i];  
8.        int ret = 0;  
9.        REP(i, n) {  
10.            int val = 0;  
11.            REP(j, n) if (i != j){  
12.                bool ck = true;  
13.                if (j < i) {  
14.                    FOR (k, j+1, i)  
15.                        if (h[i] * ABS(i-j) + (h[j] - h[i]) * ABS(k-i) <= h[k] * ABS(i-j)) ck = false;  
16.                } else {  
17.                    FOR (k, i+1, j)  
18.                        if (h[i] * ABS(i-j) + (h[j] - h[i]) * ABS(k-i) <= h[k] * ABS(i-j)) ck = false;  
19.                }  
20.                if (ck) ++val;  
21.            }  
22.            ret = max(ret, val);  
23.        }  
24.   
25.        return ret;  
26.    }  
27. };  

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

という具合。