naoya_t@topcoder

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