Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-04-04

SRM466 Medium: LotteryPyaterochka

| 22:24 | SRM466 Medium: LotteryPyaterochka - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM466 Medium: LotteryPyaterochka - naoya_t@topcoder SRM466 Medium: LotteryPyaterochka - naoya_t@topcoder のブックマークコメント

  • いきなりN=100とか考えてたから混乱した
  • 500C5 = 255244687600 はlong longに収まる
  • N=1,N=2,N=3,と順に落ち着いて全パターンを洗い出す。{5},{4,1},{3,2},{3,1,1},{2,2,1},{2,1,1,1},{1,1,1,1,1}の合計が1になることをデバッグの為に確認して、{5},{4,1},{3,2},{3,1,1} までの和を返せば計算がちゃんと合った。
typedef long long ll;

ll c(int n, int r) // nCr
{
  if (n == 0 || r == 0 || r == n) return 1LL;
  if (r > n-r) r = n-r;
  return c(n-1,r-1) * n / r;
}
ll fac(int x) // x!
{
  ll val = 1;
  for (ll i=x; i>1; i--) val *= i;
  return val;
}

class LotteryPyaterochka {
public:
  double chanceToWin(int N) {
// BEGIN CUT HERE
    //if (N<=2) return 1.0; // まあこれでいいんですが以下の数え上げのデバッグの為にコメントアウト
// END CUT HERE

    ll all = c(N*5,5);// c(5,5)=1 .. c(500,5)=255244687600
    
    ll p = 0;
    // 5
    p += c(N,1) * fac(1) * 1;
    if (N>=2) {
      // 41
      p += c(N,2) * fac(2) * c(5,4) * c(5,1);
      // 32
      p += c(N,2) * fac(2) * c(5,3) * c(5,2);

      if (N>=3) {
        // 311
        p += c(N,3) * 3 * c(5,3) * c(5,1) * c(5,1);
// BEGIN CUT HERE
        /* 以下、数え上げのデバッグの為
        // 221
        p += c(N,3) * 3 * c(5,2) * c(5,2) * c(5,1);
        if (N>=4) {
          // 2111
          p += c(N,4) * 4 * c(5,2) * c(5,1) * c(5,1) * c(5,1);
          if (N>=5) {
            // 11111
            p += c(N,5) * 1 * c(5,1) * c(5,1) * c(5,1) * c(5,1) * c(5,1);
          }
        }
        */
// END CUT HERE
      }
    }
// BEGIN CUT HERE
    //printf("%lld / %lld\n", p, all);
// END CUT HERE
    return (double)p / all;
  }
};
  • passed system test

SRM466 Easy: LotteryCheating

| 04:10 | SRM466 Easy: LotteryCheating - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM466 Easy: LotteryCheating - naoya_t@topcoder SRM466 Easy: LotteryCheating - naoya_t@topcoder のブックマークコメント

  • 約数の個数が奇数 = 平方数
    • n = p1^a1 * p2^a2 * ... * pn^an のとき
    • 約数の個数は (a1+1)(a2+1)..(an+1)
    • これが奇数ということはa1...anはすべて偶数
    • だったら n={(p1^(a1/2))(p2^(a2/2))..(pn^(an/2))}^2
  • 0≦n≦9999999999 なので0≦x≦99999の二乗を調べればよい
  • それぞれの平方数と比較して、何文字異なるか
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()

class LotteryCheating {
public:
  int minimalChange(string ID) {
    int n=sz(ID);
    ll nmax=1; rep(i,n) nmax*=10; nmax--;

    int ch=n+1;
    for(ll i=0;i<100000;i++){
      ll ii=i*i; if (ii > nmax) break;
      string iis(n,'0');
      rep(j,n) { iis[n-1-j] = '0' + (ii%10); ii/=10; }
      int cn=0;
      rep(j,n) {
        if (iis[j]!=ID[j]) cn++;
      }
      ch = min(cn,ch);
    }
    return ch;
  }
};
  • passed system test

SRM466

03:20 | SRM466 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM466 - naoya_t@topcoder SRM466 - naoya_t@topcoder のブックマークコメント

前回休んだのでちょっと久しぶり。1amまで寝てた。

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 LotteryCheating 提出 - 撃沈 - 0.0
1 550 LotteryPyaterochka 間に合わず - - - -
1 1000 - - -

Easy(250): LotteryCheating

  • 律儀に1文字ずつローテートして約数数えて
  • 3つまでしかチェックしてなくてそれ以上だと4
  • と思ってたらバグあるし

Medium(500): LotteryPyaterochka

  • 250で時間取りすぎた
  • 数え上げ
  • 数が合わないいい
  • 間に合わん

Hard(1000): 開いてない

Challenge Phase:

  • 撃沈
  • 偉い人の見たら1から100000までの二乗で何かごにょごにょしてる
  • しかも簡潔
  • そうか約数が奇数な数って全部二乗数になるのか
  • ごめんなさい出直します

Result:

0 point

Room: 16/20

Div I: 557/866

1438 → 1370 (-68) 絶賛転落中…

http://gyazo.com/7197246baf1b545d86798956cbc3234f.png

Practice Room:

  • 250のソース(※1字訂正)を通してみたら"9999999999"でTLEだった。
  • まあそりゃそうだ...
  • 以下TLEコード
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())

class LotteryCheating {
  int n;
  vector<char> sv;
  vector<ll> ps;

  int count(const vector<char>& cs){
    ll v=0LL, c=1;
    rep(i,n) v=v*10 + (cs[i]-'0'); if (v == 0LL) return 1;

    ll vm = sqrt(v);

    tr(ps,p){
      if (*p > vm) break;
      int d = 1;
      while (v % (*p) == 0) { d++; v /= *p; }
      c *= d;
    }
    if (v > 1) c *= 2;

    return c;
  }

public:
  int minimalChange(string ID) {
    n=sz(ID);
    int till=100000;
    sv.assign(till+1,1);

    for (int i=4; i<=till; i+=2) sv[i] = 0;
    for (int i=3; i<=till; i+=2){
      if (sv[i]) {
        for (int j=i*3; j<=till; j+=i+i) sv[j] = 0;
      }
    }
    ps.resize(1); ps[0] = 2;
    for (int i=3; i<till; i+=2) {
      if(sv[i]) ps.pb(i);
    }

    vector<char> cs(all(ID));
    if (count(cs) & 1) return 0;

    // #1
    rep(i,n) {
      int o=cs[i];
      rep(z,10) {
        cs[i]++; if (cs[i]==0x3a) cs[i]='0';
        if (cs[i]==o)continue;
        if (count(cs) & 1) return 1;
      }
    }
    if (n==1) return 1;

    // #2
    rep(i,n) {
      int o=cs[i];
      rep(j,n) { if (j==i) continue;
        int o2=cs[j];
        rep(z,10){
          cs[i]++; if (cs[i]==0x3a) cs[i]='0';
          if (cs[i]==o)continue;
          rep(y,10) { // 10000
            cs[j]++; if (cs[j]==0x3a) cs[j]='0';
            if (cs[j]==o2)continue;
            if (count(cs) & 1) return 2;
          }
        }
      }
    }
    if (n==2) return 2;

    // #3
    rep(i,n) {
      int o=cs[i];
      rep(j,n) { if (j==i) continue;
        int o2=cs[j];
        rep(k,n) { if (k==j || k==i) continue;
          int o3=cs[k]; // ★提出コードでo3=cs[j]って書いてた件
          
          rep(z,10){
            cs[i]++; if (cs[i]==0x3a) cs[i]='0';
            if (cs[i]==o)continue;
            rep(y,10) {
              cs[j]++; if (cs[j]==0x3a) cs[j]='0';
              if (cs[j]==o2)continue;
              rep(x,10) { // 1000000
                cs[k]++; if (cs[k]==0x3a) cs[k]='0';
                if (cs[k]==o3)continue;
                if (count(cs) & 1) return 3;
              }
            }
          }
        }
      }
    }
    if (n==3) return 3;

    return 4;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100404