topcoder

naoya_t@topcoder

2012-02-24

SRM534 − 今日は出ましたがrating減

00:28 |

（http://naoyat.hatenablog.jp/entry/2012/02/24/233000 からの転載）

Easy(250): ◯<148.47>
Medium(500): 撃沈<0>
Hard(1000): 開いた<0>

12/20 in the room, 414/717 in Div1

1652 -> 1610

なんか最近EasyはDP有りで、Mediumはかなりうまく書かないとTLE/MLEになるぎりぎりの設定になってる印象。

Easy (250): EllysCheckers

こういうNim系が相変わらず苦手で困る
checkerの数が0の局面から逆方向に考えていくDP
boardのサイズが最大20なので状態数は2^20=1048576
148.47 points (27'52'')
Passed system test

#include <iostream>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class EllysCheckers {
 public:
  string getWinner(string board) {
    int s=sz(board);
    int n=1<<s;
    vector<int> dp(n,-1);
    dp[0] = 0;
    for (int x=0; x<n; x++) {
      for (int m=1; m<=x; m<<=1) {
        if (m&x) {
          int m_ = m << 1;
          if (m_ < n && !(m_ & x)) {
            int y = (x - m) | m_;
            dp[y] = 1-dp[x];
          }
          int _mmm = m*7, mmmm = m*15;
          if (mmmm < n && (x & mmmm) == _mmm) {
            int y = (x - _mmm) | (_mmm << 1);
            dp[y] = 1-dp[x];
          }
        }
      }
      if ((x & 1) == 0) {
        int y = x|1;
        dp[y] = 1-dp[x];
      }
    }
    int b=0; rep(i,s-1) b = b*2 + ((board[i]=='o')?1:0);
    return dp[b] ? "YES" : "NO";
  }
};

Medium (500): EllysNumbers

数の集合が与えられ、互いに素であるような部分集合で積がnである組み合わせが何通りあるか
nの約数以外は捨ててよさそう。1が入ってる場合は答えを2倍にすればよさそう。
集合の要素を端から1つずつ掛けたり掛けなかったりして行く感じのメモ化再帰を書いてみた。新たに掛ける数とそこまでの積とのgcdが1でない場合は掛けられない縛り

#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#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())

ll gcd(ll m, ll n)
{
  if (m == 0 || n == 0) return 0LL;
  if (m == 1 || n == 1) return 1LL;
  if (m == n) return m;
  while (1) {
        if (m == 0) return n;
        if (n == 0) return m;
        if (m > n) m %= n; else n %= m;
  }
}

class EllysNumbers {
  vector<ll> ns;
  int nn;
  ll n_;

  map<pair<ll,int>,ll> mm;

  ll sub(ll x, int ix) {
    if (ix == nn) return (x == n_ ? 1LL : 0LL);

    pair<ll,int> k(x, ix);
    if (found(mm,k)) return mm[k];

    if (gcd(x, ns[ix]) == 1) {
      return mm[k] = sub(x*ns[ix], ix+1) + sub(x, ix+1);
    } else {
      return mm[k] = sub(x, ix+1);
    }
  }

 public:
  long long getSubsets(long long n, vector <string> special) {
    n_ = n;
    stringstream ss;
    tr(special,it) ss << *it; ss << " ";
    string s = ss.str(); int sn = s.size();
    ll a = 0;
    vector<ll> nums;
    rep(i,sn) {
      if (s[i] == ' ') {
        if (a >= 0) nums.pb(a);
        a = -1;
      } else {
        ll b = (ll)(s[i] - '0');
        if (a >= 0) a = a*10LL + b;
        else a = b;
      }
    }

    set<ll> nset; bool has1 = false;
    tr(nums,it) {
      if (*it == 1) { has1 = true; continue; }
      if (n % *it) continue;
      nset.insert(*it);
    }
    ns.assign(all(nset));
    nn = ns.size();
    if (nn == 0) return 0LL;
    if (nn == 1 && ns[0] != n) return 0LL;

    mm.clear();
    return sub(1LL, 0) * (has1 ? 2 : 1);
  }
};

しかし撃墜される。TLE？MLE？

再考

積の要素が互いに素であるという条件はもっと活用すべき。nも集合各要素も素因数分解してみて、例えばnが2^3を持つなら2^2,2^1を持つ要素は排除できるよね
n≦1e18ならnは高々15種類の素数（の累乗）の積と考えてよさそう。cf. (2^1)*(3^1)*(5^1)*(7^1)*(11^1)*(13^1)*(17^1)*(19^1)*(23^1)*(29^1)*(31^1)*(37^1)*(41^1)*(43^1)*(47^1)=614889782588491410
nとspecial integersをそれぞれ nに含まれる素因数の有無をビットのon/offで表したら最長15ビット(<32768)
special integersは高々500種類なので500*32768=16384000; long longだと131072000バイトでMLE。
もしかして答えが32bit intを超えることがない？だとしたら32bit intで確保して65536000バイト。
でもMLE…もしかしてこれって64MB制限に引っかかる？
practice roomで実際にアロケートできたのがsizeof(int)*484*32768=63438848バイト。
ああーもういいや最初の484個だけメモって残り16個ぐらい何度でも再帰させてしまえ
これでpassed system test

#include <iostream>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#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())

ll gcd(ll m, ll n)
{
  if (m == 0 || n == 0) return 0LL;
  if (m == 1 || n == 1) return 1LL;
  if (m == n) return m;
  while (1) {
        if (m == 0) return n;
        if (n == 0) return m;
        if (m > n) m %= n; else n %= m;
  }
}

class EllysNumbers {
  vector<int> ns; // 15bit
  int nn, allocated;
  int n_; // 15bit

  int *mm;

  ll sub(int x, int ix) { // 15bit, 500=9bit
    if (ix == nn) return (x == n_ ? 1LL : 0LL);

    int k = (ix << 15) | x;
    if (ix < allocated && mm[k] >= 0) return mm[k];

    ll ans = sub(x, ix+1);
    if ((x & ns[ix]) == 0) ans += sub(x | ns[ix], ix+1);

    if (ix < allocated) mm[k] = ans;
    return ans;
  }

  bool has1;

 public:
  bool prepare(long long n, vector<string> special) {
    // special integersをパース
    stringstream ss;
    tr(special,it) ss << *it; ss << " ";
    string s = ss.str(); int sn = s.size();
    ll a = 0;
    vector<ll> nums;
    rep(i,sn) {
      if (s[i] == ' ') {
        if (a >= 0) nums.pb(a);
        a = -1;
      } else {
        ll b = (ll)(s[i] - '0');
        if (a >= 0) a = a*10LL + b;
        else a = b;
      }
    }

    // エラトステネスのふるい
    char sieve[32768+1];
    memset(sieve, 1, 32768+1);

    sieve[0] = sieve[1] = false;
    for (int i=3; i<32768; i+=2) {
      sieve[i+1] = false;
      if (!sieve[i]) continue;
      for (int j=i*2; j<32768; j+=i) sieve[j] = false;
    }

    int primes[3512], j=0;
    rep(i,32768) if (sieve[i]) primes[j++] = i; // 3512 primes in [0 .. 32767]

    // special integers の中で要らない子を捨てつつ、それぞれを素因数分解
    set<ll> nset; has1 = false;
    set<int> used_primes; map<int,int> max_fact;
    map<ll,map<int,int> > pset;
    tr(nums,it) {
      int num = *it; if (num == 1) { has1 = true; continue; }
      if (n % num) continue;

      // prime factorization
      map<int,int> ps;
      int x = num;
      rep(j,3512){
        int prime = primes[j];
        while (x % prime == 0) {
          if (found(ps,prime))
            ps[prime]++;
          else
            ps[prime] = 1;
          x /= prime;
        }
      }
      if (x > 1) ps[x] = 1;

      tr(ps,pt) {
        used_primes.insert(pt->first);
        if (found(max_fact, pt->first))
          max_fact[pt->first] = max(max_fact[pt->first], pt->second);
        else
          max_fact[pt->first] = pt->second;
      }

      nset.insert(num);
      pset[num] = ps;
    }
    nn = nset.size();
    if (nn == 0) return false;
    if (nn == 1 && *nset.begin() != n) return false;

    // special integersで使った素数のみでnを素因数分解。できなければ return 0
    ll x = n;
    map<int,int> n_fact;
    tr(max_fact,it) {
      ll prime = (int)it->first;
      int f = 0, maxf = it->second;
      while (x % prime == 0) {
        ++f; x /= prime;
      }
      if (f) n_fact[prime] = f;
      if (f > maxf) return false;
    }
    if (x != 1) return false;

    map<int,int> n_fact_map;
    n_ = 0;
    int ix = 0;
    tr(n_fact,it) {
      n_ |= (1 << ix);
      n_fact_map[it->first] = ix++;
    }

    // nで使われていない素因数を含むspecial integersを排除
    ns.clear();
    tr(pset,it) {
      int bs = 0;
      bool use_this = true;
      tr(it->second,jt) {
        int prime = jt->first, f = jt->second;
        if (!found(n_fact, prime) || f != n_fact[prime]) { use_this = false; break; }
        bs |= (1 << n_fact_map[prime]);
      }
      if (use_this) ns.push_back(bs);
    }
    nn = ns.size();

    return true;
  }

  long long getSubsets(long long n, vector<string> special) {
    if (!prepare(n, special)) return 0LL;

    //mm.assign(500*32768, -1);
    allocated = 0;
    for (int sz=500; sz>0; --sz) {
      mm = (int *)malloc(sizeof(int)*sz*32768);
      if (mm) { allocated = sz; break; }
    }

    ll ans = 0;
    if (mm) {
      memset(mm, -1, sizeof(int)*allocated*32768);
      ans = sub(0, 0) * (has1 ? 2 : 1);
      free((void*)mm);
    }
    return ans;
  }
};

Hard (1000): EllysString

Mediumを提出して５分ぐらい残ってたので開いてみた。Levenshtein距離的な何かを求める問題。文字の置き換えと、隣接する2文字の交換が許されている。
あとで考える

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20120224

2012-02-20

SRM533 - 深夜開催のSRMがちょっと辛い今日この頃

01:55 |

（http://naoyat.hatenablog.jp/entry/2012/02/20/014918 からの転載）

最近ちょっと早寝早起きサイクルになってるので2amからとかちょっときついですね。

というわけでSRM533の問題を見てみた話。配点的には250-500-1000ですが・・・

出てたら430位ぐらいでレーティング横ばい〜微減、かな。

続きを読む

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20120220

2012-02-16

SRM532 - 寝倒した先日の問題を見てみた

01:54 |

（http://naoyat.hatenablog.jp/entry/2012/02/16/184337 からの転載）

300 - 450 - 1000 ってまた気持ち悪い配点だけれど、本番じゃないしMediumから手をつけてみようかと。

続きを読む

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20120216

2012-01-31

SRM531 Div1 Medium: MonsterFarm

過去問 | 02:29 |

なんかEasyより簡単そうに思えたんだけど、やってみて5回目でSystem Test通った程度の体たらくなのでまあEasy頑張っておいてよかった的な。

続きを読む

SRM531 - 1年3ヶ月ぶりのTopCoder参戦

00:00 |

（http://naoyat.hatenablog.jp/entry/2012/01/31/235459 からの転載）

1/31 21:05〜

久しぶりすぎて緊張する

300-500-1000だ

Easy300点は不吉

続きを読む

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20120131

2011-05-08

GCJ2001 QR参戦メモ

00:40 |

Google Code Jam 2011 - Qualification Round

http://code.google.com/codejam

（naoya.t さんで出ています）

競技やるの半年ぶりぐらいでしょうか…

続きを読む

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20110508