Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/910-683ce00a
この記事にトラックバックする(FC2ブログユーザー)

SRM458 DIV2 HARD - ProductTriplet (この記事を編集する[管理者用])

Source

TopCoder SRM458 DIV2 HARD (950pt)
Problem Statement

問題概要

x, y, zの下限,上限がそれぞれ与えられるので,
 x * y = z
を満たす(x,y,z)の組の数を求める問題.下限の下限は1,上限の上限は10億.

解法

xを固定したら,zが範囲入るような,yの範囲は簡単に計算可能.
しかし,xを1ずつ動かしつつ,それを数えれば,xは10億ぐらい動くのでTLE.
だけど,xが大きいと,yの範囲がなかなか変わらないので,yの範囲が変わらない部分をまとめて処理してやればOK.
その範囲はちゃんと計算できると思うのだけど,TopSubmissionは2分探索で求めているみたいだった.
もっと手を抜いて,適当に飛ばした先を見てやって,yの範囲が同じなら,そこまでいっぺんに処理してやるという手抜きコードが下のコード.(一応最悪ケースで85msぐらいで動くらしい)

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define WIDTH 2000 // てきとーな値

class ProductTriplet {
public:
long long countTriplets(int xa, int xb, int ya, int yb, int za, int zb) {
  int a, b, A, B, xc, skip;
  long long res=0;

  while(xa <= xb){
    xc = xa+WIDTH-1;

    a = (za+xa-1)/xa; b = zb/xa;
    A = (za+xc-1)/xc; B = zb/xc;
    if(a<ya) a=ya; if(b>yb) b=yb;
    if(A<ya) A=ya; if(B>yb) B=yb;

    skip = 1;
    if(a==A && b==B && xc<=xb) skip=WIDTH;
    if(a<=b) res += (b-a+1)*skip;
    xa+=skip;
  }

  return res;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/910-683ce00a
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。