読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 458 Div2 Hard ProductTriplet

探索 SRM
問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10698&rd=14180

 x \time y = zを満たすような自然数の組はいくつあるか。ただしこれらの数字の下限、上限はminx, miny, minz, maxx, maxy, maxz(~1000,000,000)で与えられる。

やりかた

一変数を固定すると式を満たすTripletの数がすぐわかる。
xをある数字に固定すると式を満たすようなTripletの数はminz / x <= y <= maxz / xかつminy <= y <= maxyの範囲にあるyの数になる。なのでxをminxからmaxxまで変えて数えていけばいいのだけれど普通にやるとO(maxx - minx)になるのでTLEする。なので工夫が必要になる。

まずLIMというxの上限を決めてmin(maxx, LIM - 1)までxを走査してTripletの数を数えてみる。なのでこのとき求まるTripeletのxはかならずLIM未満になる。続いてyをmin(maxy, LIM - 1)まで走査してTripletを数える。ただしこのときx < LIMとなるようなTripletは上ですでに数えているのでそれは無視してxがLIM以上になるTripletを数える。こうすることで x < LIM なるTripletと LIM <= x なるTripletがもれなくかつダブりなくもとまる。LIMはだいたいsqrt(1e9)前後の数で、O(LIM)かつO(1e9 - LIM)が通りそうなくらいの数にすればいい。

というかんじ。practice roomのlyricallyさんのコードを参考にした。とてもきれいなコードだと思う。
ある範囲までのxはfor分の条件で計算して、それ以降の範囲のxは次のfor文の中身で数えるってことになるようだ。

以下ソース。

class ProductTriplet {
public:
  long long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz) {
    ll ans = 0;
    int LIM = 1 << 16;

    for(ll i = minx; i <= maxx && i < LIM; i++){
      ll uby, lby;
      uby = min((ll)maxy, maxz / i);
      lby = max((ll)miny, (minz - 1) / i + 1);
      
      if(i * lby > maxz) uby = 0;
      if(i * uby < minz) lby = 1LL << 60;

      ans += max(0LL, uby - lby + 1);
    }

    for(ll i = miny; i <= maxy && i < LIM; i++){
      ll ubx, lbx;
      ubx = min((ll)maxx, maxz / i);
      lbx = max((ll)minx, (minz - 1) / i + 1);
      
      if(i * lbx > maxz) ubx = 0;
      if(i * ubx < minz) lbx = 1LL << 60;
      if(lbx < LIM) lbx = LIM;
      ans += max(0LL, ubx - lbx + 1);
    }
    return ans;
  }
};

まだ自分ではよく消化し切れてない。。
x = y = sqrt(z)
x < sqrt(z), and thus y > sqrt(z)
x > sqrt(z), and thus y < sqrt(z)
で場合わけしてもいいけどバグらせそうだ。上のやりかたのほうが賢いと思う。

しょげないでよBaby 眠れば治る