Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-01-13

kurukshetra contestメモ

| 22:00 | kurukshetra contestメモ - naoya_t@topcoder を含むブックマーク はてなブックマーク - kurukshetra contestメモ - naoya_t@topcoder kurukshetra contestメモ - naoya_t@topcoder のブックマークコメント

http://www.athena.kurukshetra.org.in/

  • インド!インド!インド!
  • 問題(ちょっとブロークンな感じの英語)の意図を読み取るのがひと苦労。TopCoderの問題文は曖昧さが少なくていいなあ
    • 最初の1パラグラフは(大抵)題意に関係ない
  • 前の問題を正解しないと次の問題が出てこない。(=問題を飛ばすことはできない)
  • ボーナス問題の得点は500点から経過時間(分)で減っていくらしい。トップ集団の得点に端数があるのはそのためらしい。
    • 参加が遅かった自分はボーナス問題解いても(まだ1問しか解いてないけど)最低点の250点しかもらえない
  • で、現在1250点(レベル11)で、全世界(というか全インド)で64位
  • このコンテストいつまでなの?もしかして終わらないの?

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

| 18:00 | 過去問マラソン(#9): SRM151 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#9): SRM151 - naoya_t@topcoder 過去問マラソン(#9): SRM151 - naoya_t@topcoder のブックマークコメント

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

Easy(250): Archimedes

  • pi定数は脳内からコピペ直打ち
    • なんか題意からしてpiとかsinとか使うのどうよと思うけど
  • 半径は1だが、分母は直径なので2(これ忘れてたのでSample Caseで答えが2倍になってて気がついた)
  • 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人(少なっ)

Levelnamesubmit正答率平均点
EasyArchimedes129/14594.57%204.58
MediumMergeSort140/14577.86%353.71
HardGauss72/14559.72%652.95

やはり2人に1人が解いてます…(正答率は6割弱)

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

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100113