SRM547 Div.1

結果

o--(+2/-1) 318.87pts 53rd
朝SRMで人が少ないけど、最高順位更新。

レートは1594->1731で1700台復帰。

250　Pillers

問題

2本の棒が距離wで立っている。
棒の高さはそれぞれ[1,x],[1,y](1<=x,y<=10^5)でrandomのとき、
棒の先端同士の距離の期待値を求める。

解法

高さが等しければ距離はwで、高さがd違ったらsqrt(w*w+d*d)異なるのは明らかなので

accum[k] := 1 <= i <=kのsqrt(w*w+i*i)の和

という累積和を使えばO(min(x,y))で計算できる。
かなり速くバグなく実装できたのが勝因。
10000*10000がintではoverflowするので注意。

     double getExpectedLength(int w, int x, int y) {
         double accum[100001];
         int mini = min(x,y);
         int maxi = max(x,y);
         double ret = 0;
         memset(accum, 0, sizeof(accum));

         for(int i=1;i<100001;i++){
             accum[i] = accum[i-1] + sqrt(w*w+(ll)i*i);
         }
         
         for(int i=1;i<=mini;i++){
             ret += (w + accum[i-1] + accum[maxi - i]) / ((ll)x*y);
         }
         return ret;
     }

500 RectangularSum.cpp

practiceで通しました。

問題

     0   1   2   3 ...  W-1
     W W+1 ... ... ... 2W-1

(H-1)W ... ... ... ... HW-1

という数の並びが与えられ、この中で囲まれた部分の和がSに等しくなるような
部分長方形のうち、囲まれた部分に含まれる数の個数の最小値を求める。
そのような部分長方形が存在しなければ-1を返す。

解法

左上をαとする縦r,横cの長方形を考えると、その右下は

α+(r-1)*w+c-1

として表すことができる。これによってこの長方形内の数の和がSに等しいとき

(2α+(r-1)*w+c-1)*r*c/2=S
  (2α+(r-1)*w+c-1)*r*c=2S

と書くことができる。このときr,cは2Sのdivisorなのでこれらを列挙して対応する
αを求め、そのとき右下の点が元の長方形内に収まっていれば値を更新していけばよい。

• r,cはそれぞれ2Sのdivisorだが、r*cはそうでない可能性がある
• 2αは0より大きく、かつ偶数でないといけない

あたりをチェックすればいい。

     long long minimalArea(int _h, int _w, long long S) {
         vector<ll> divs;
         ll ret = 1ll << 50;
         ll h = _h;
         ll w = _w;
         S *= 2;
         for(ll i=1;(long long)i*i<=S;i++){
             if(S%i==0){
                 divs.PB(i);
                 if(i*i != S){
                     divs.PB(S/i);
                 }
             }
         }
         sort(divs.begin(), divs.end());

         for(ll i=0;i<(int)divs.size();i++){
             for(int j=0;j<(int)divs.size();j++){
                 if(divs[i] * divs[j] > S) break;
                 if(S % (divs[i] * divs[j] )) continue;
                 ll left = S / divs[i] / divs[j];
                 ll alpha = left - (divs[i] - 1) * w - (divs[j] - 1);
                 if(alpha < 0 || alpha & 1) continue;
                 alpha /= 2;
                 ll y = alpha / w;
                 ll x = alpha % w;
                 if(x + divs[j] - 1 < w && y + divs[i] - 1 < h){
                     ret = min(ret, divs[i]*divs[j]);
                 }
             }
         }
         return ret == 1ll << 50?-1:ret;
     }

challenge

250でoverflowするのに気づいていたので、llなりdoubleにしていないやつで+2、
500でTLEしそうなやつを見つけてchallengeするも、答えが1になるケースを打ち込んでしまい-1。

感想

レートが戻ったのでよかった。