Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-03

[][] TopCoder Single Round Match 505 Div1 00:23 はてなブックマーク -  TopCoder Single Round Match 505 Div1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

3001:14:55.450Opened0.00
5000:38:24.331Opened0.00
10000:00:00.000Unopened0.00
Challenge..0.00

部屋(Room 36) 7位,全体 306位

Rating : 1484 → 1453 (-31)

何にも出来なかったです・・.取りあえず500のコードだけ掲載します.

500 SetMultiples

要約

 集合S2がS1の倍数であるとは,S1の任意の元xに対しあるS2の元yが存在し,yがxの倍数になっている事をいう.例えば{4}は{1,2,4}の倍数になっている.正数A, B, C, Dが与えられていて,S = {x | xは正数,A <= x <= B or C <= x <= D}とする.Sの部分集合で,Sの倍数になっているものうち,要素数が最小のものの個数を求めよ.

 A, B, C, Dは1 <= A <= B < C <= D <= 10^{10} を満たす.

 

方針

 まず,区間が一つ([C, D])しかない場合を考える.[D/2+1, D]は他の要素の倍数では書けないので,これは残さないといけない,逆に残りの[C, D/2]部分は不要,というのもこれらを

[C, D / n]・・・[D/5 + 1, D/4], [D/4 + 1, D/3], [D/3 + 1, D/2] (※)

と分割すると,例えばI_{3} = [D/4 + 1, D/3]の中にある数は3倍すれば先頭部分のI _{1} = [D/2+ 1, D]に入るからである(以下,I_{k} = [D / (k +1) + 1, D/k]と書く).

(CやDが最大10^{10}なので,個々の数ではなく,区間で考えようという発想は自然だと思います).

うれしいのは,I_{k}達はkを増やしていくとD以下の正数を網羅している事で,I_{1} が[C, D]より区間として大きかったら,今回の問題のように複数の区間でも答えはI_{1}となる.

 そこでC * 2 > Dの場合に話を限定する(と言ってもこの仮定は後で外せる).この場合も上の考察から[C/k, D/k](これをJ_{k}と書く事にする)と[A, B]の共通部分に入らない数がいくつあるかを数え上げれば良いとわかる.問題なのはJ_{k+1}とJ_{k}が交わる可能性がある事で,単純にJ_{k}と[A, B]の共通部分の個数すべて足し上げるとダブりが生じてしまう.上の(※)の場合を参考にして,J_{k}の下限をD/(k+1)で切り取って,それらと{A, B]との共通部分を取ればダブりは解消できる(これはJ_{k}とI_{k}の共通部分を取っている事に対応する).下限を切り取ってしまえば,C * 2 > Dでない場合も同様に扱える.

 以上のアルゴリズムで正しい答えは返せるが,例えば次のケースでTLEを起こす.

(A, B, C, D) = (1,100, 9999999990, 10000000000)

つまり,([D/(double)(k+1), D/(double)k]はほとんどの場合正数を含まないにもかかわらず,)[D/(double)(k+1), D/(double)k] が[A, B]と共通部分を持つようなkが大量にある事が問題となる.このようになるケースではA,Bが小さいので,[A, B]の要素を1個ずつ調べればよい.

コード例
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

typedef long long ll;

long long maxl (ll a, ll b ){return a > b ? a : b;}
long long maxl (ll a, ll b ){return a < b ? a : b;}

const static ll INF = 10000000;

class SetMultiples {
public:
  long long smallestSubset(long long A, long long B, long long C, long long D) {
    A = max(A, (B/2 ) + 1);
    C = max(C, (D/2 ) + 1);
    
    ll kmn = (C+B-1) / B;
    ll kmx = D / A;
    if(kmx - kmn < INF){
      ll res = B - A + 1;
      for(ll k = kmn;k <= kmx;k++){
	ll l = maxl(D/(k+1)+ 1, maxl((C+k-1)/k, A) ) ;
	ll r = minl(D/k, B);

	res -= (r >= l) ? (r - l + 1) : 0;
      }
      return res + (D - C + 1);
    }else{
      ll res = 0;
      for(int i = A;i<=B;i++){
	if( (D/i) * i < C){
	  res ++;
	}
      }
      return res + (D - C + 1);
    }
  }
};