SRM 458 Div2 Hard ProductTriplet
問題
http://apps.topcoder.com/stat?c=problem_statement&pm=10698&rd=14180
を満たすような自然数の組はいくつあるか。ただしこれらの数字の下限、上限は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)
で場合わけしてもいいけどバグらせそうだ。上のやりかたのほうが賢いと思う。