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);
    }
  }
};

[][] Project Euler Problem 75 12:27 はてなブックマーク -  Project Euler Problem 75 - 練習帳

問題文

 http://projecteuler.net/index.php?section=problems&id=75

要約

 1 本の針金を折り曲げて,各辺の長さが整数の直角三角形をつくる.長さが1500000 以下で,作れる直角三角形が 1 種類しかないものの個数を求めよ.

方針

 3辺の長さが互いに素ならば,その3辺は適当な正数m>nを用いて,m^{2} + n^{2}, m^{2} - n^{2}, 2mnと表せる.従って,これを整数倍したものを数え上げれば良い.互いに素な3辺を上のように表す(m, n) は一意的だが,3辺を整数倍して,k (m^{2} + n^{2} ), k *( m^{2} - n^{2} ), k * 2mnというものをすべて数え上げるとダブりが生じてしまう.例えば,

(m, n, k) → (作られる3辺) 
(2, 1, 2) →  (10, 8, 6)
(3, 1, 1) →  (10, 6, 8)

 下のコードでは,3辺を長い順にソートし表示が一意的になるようにし,set を用いて既に現れた組はものを追加しないようにしている.

コード例(C++)

実行時間は11秒程度でした

#include <iostream>
#include <map>
#include <set>
#include <utility>

using namespace std;

static const int N = 1500000;
map<int , set<pair<int ,pair<int,int> > > > l;

int main(){
  for(long long  m = 1; (2 * m * (m+1) ) < N; m++){
    for(long long  n = 1; n < m &&  (2 * m * (m+n) ) < N; n++){
      for(long long k = 1; (2 * m * (m+n) ) * k < N; k++){
	int a = k * (m * m + n * n);
	int b = k * (m * m - n * n);
	int c = k * (2 * m * n);
	if(b < c) swap(b,c);
	l[a+b+c].insert(l[a+b+c].end(), make_pair(a, make_pair(b,c)));
      }
    }    
  }

  int ans = 0;
  
  typedef map<int , set<pair<int ,pair<int,int> > > >::const_iterator ittype;
  for(ittype it = l.begin(); it != l.end() ;it++){
    if((it->second).size() == 1){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}