naoya_t@topcoder

SRM466 Medium: LotteryPyaterochka

過去問 | 22:24 |

• いきなりN=100とか考えてたから混乱した
• 500Ｃ5 = 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 |

• 約数の個数が奇数 = 平方数
  • 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 |

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

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

Easy(250): LotteryCheating

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

Medium(500): LotteryPyaterochka

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

Hard(1000): 開いてない

Challenge Phase:

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

Result:

0 point

Room: 16/20

Div I: 557/866

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

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