naoya_t@topcoder

過去問マラソン(#9): SRM151

過去問マラソン | 18:00 |

毎日という目標からは遠いけれど、まずは継続

Easy(250): Archimedes

• pi定数は脳内からコピペ直打ち
  • なんか題意からしてpiとかsinとか使うのどうよと思うけど
• 半径は1だが、分母は直径なので2（これ忘れてたのでSample Caseで答えが２倍になってて気がついた）
• 241.91pt (5'13'')
• passed system test

const double pi = 3.141592653589793238462643383279;

class Archimedes {
 public:
  double approximatePi(int numSides) {
    double rad = pi * 2 / numSides;
    // h/r = sin(rad/2)
    double perimeter = (sin(rad/2) * 2) * numSides;
    return perimeter / 2.0;
  }
};

Medium(500): MergeSort

• 実装するだけ？比較回数をカウントするだけ？
• 簡単すぎない？罠なさすぎない？
  • INT_MINとINT_MAXの比較があるのでcmp()は引き算で実装しないほうがいい、とかね。そういうのはありますが
• 377.84pt (17'21'')
  • TLEになるの？とか心配して長さ50の最悪ケーステスト書いたけど全然余裕
• passed system test
  • これは全員Hardまで解けよという問題セット

#define sz(a)  int((a).size())

class MergeSort {
  int cnt;
  int cmp(int x, int y) {
    cnt++;
    if (x<y) return -1;
    else if (x>y) return 1;
    else return 0;
  }
  vector<int> mergeSort(vector<int>& a) {
    int al=sz(a);
    if (al<=1) return a;

    vector<int> b(a.begin(), a.begin()+al/2),
                c(a.begin()+al/2, a.end());
    return merge( mergeSort(b), mergeSort(c) );
  }
  vector<int> merge(const vector<int>& b, const vector<int>& c) {
    int bl=sz(b), cl=sz(c);
    vector<int> a(bl+cl);
    for (int ai=0,bi=0,ci=0;;) {
      if (bi==bl) { while(ci<cl) a[ai++]=c[ci++]; break; }
      else if (ci==cl) { while(bi<bl) a[ai++]=b[bi++]; break; }
      int cmpd=cmp(b[bi],c[ci]);
      if (cmpd < 0) a[ai++]=b[bi++];
      else if (cmpd > 0) a[ai++]=c[ci++];
      else { a[ai++]=b[bi++]; a[ai++]=c[ci++]; }
    }
    return a;
  }
  
 public:
  int howManyComparisons(vector<int> numbers) {
    cnt = 0;
    mergeSort(numbers);
    return cnt;
  }
};

Hard(1000): Gauss

• なにこれ超簡単
  • こういうのが超簡単に見えるのは最近インドの怪しい数学コンテストに参加してたからですが
  • 範囲が[a, b]のときb(b+1)/2 - a(a-1)/2 = targetですから
  • ということは (b+a)(b-a+1) = target*2
  • target*2 の約数が全部求められればa,bが出せるじゃん
  • あとは実装実装
• 538.95pt (32'56'')
• failed system test
  • ごめんなさいごめんなさいごめんなさい
  • target=99999999997 のときにアウト
  • (1)素因数分解のミス：√2Tまでの素数で割って行ったときに余りが出たらそれは√2T超の素数なので入れてやるべき
  • (2)intでは足りないところにintを使ってる場所いくつか
  • それらを修正してpassed system test

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

vector<int> primes;
char *is_prime = NULL;

void dealloc_sieve() {
  if (is_prime) { free((void*)is_prime); is_prime = NULL; }
}

int prepare_primes_until(int till) {
  is_prime = (char *)malloc(1+till);
  if (!is_prime) return -1;
  memset((void*)is_prime, 1, 1+till);
  primes.clear();

  for (int i=2; i<=till; i++){
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j=i*2; j<=till; j+=i) is_prime[j] = false;
    }
  }
  return primes.size();
}

class Gauss {
  ll s2ll(string str){
    ll a=0LL;
    rep(i,sz(str)){
      a = a*10LL + (str[i] - '0');
    }
    return a;
  }
  string range(ll a, ll b){
    stringstream ss;
    ss << "[" << a << ", " << b << "]";
    return ss.str();
  }

  vector<pair<ll,int> > facv; //★pair<int,int>でやってた
  int facvn;

  map<int,list<ll> > submemo;
  
  list<ll> sub(int from){
    if(found(submemo,from)) return submemo[from];

    list<ll> ans;
    if (from==facvn) {
      ans.pb(1); submemo[from] = ans; return ans;
    }

    ll prime=facv[from].first, cnt=facv[from].second; //★intでやってた
    
    list<ll> s = sub(from+1);
    tr(s,it) {
      for(ll i=0,x=1LL;i<=cnt;i++,x*=prime){
        ans.pb(*it * x);
      }
    }
    submemo[from] = ans;
    return ans;
  }
  
 public:
  vector<string> whichSums(string target) {
    facv.clear();
    submemo.clear();
    
    int pn = prepare_primes_until( 316228 );

    ll t2 = s2ll(target) * 2;
    vector<string> ans;

    map<ll,int> fac; //★map<int,int>でやってた

    ll tmp=t2;
    rep(i,pn) {
      ll prime = primes[i];
      if (prime>tmp) break;
      if (tmp%prime == 0) {
        do {
          tmp /= prime;
          if(found(fac,prime)) fac[prime]++;
          else fac[prime]=1;
        } while (tmp>1 && tmp%prime==0);
      }
    }

    if (tmp>1) fac[tmp]=1; //★これ必要

    facv.assign( all(fac) );
    facvn = sz(facv);

    list<ll> xs = sub(0);
    vector<pair<ll,ll> > ans_;
    
    tr(xs,it) {
      ll x = *it, y = t2 / x;
      // b+a=x, b-a+1=y
      // 2b+1=x+y, 2a-1=x-y
      ll b2 = x+y-1, a2 = x-y+1;
      if (b2 % 2 || a2 % 2 || b2<=0 || a2<=0 || a2>=b2) continue;
      ans_.pb( make_pair(a2/2, b2/2) );
    }

    sort( all(ans_) );
    tr(ans_,it) {
      ans.pb( range( it->first, it->second ) );
    }
    
    dealloc_sieve();
    return ans;
  }
};

この回は三問完答者続出したんじゃないかな？と思って統計見てみた...

SRM 151 (06.17.2003)

参加者(DivI): 145人（少なっ）

Level	name	submit	正答率	平均点
Easy	Archimedes	129/145	94.57%	204.58
Medium	MergeSort	140/145	77.86%	353.71
Hard	Gauss	72/145	59.72%	652.95

やはり２人に１人が解いてます…（正答率は６割弱）

普段はMediumで出る程度のレベルの問題なだけに、落としたのが悔しいです。