naoya_t@topcoder

SRM365 Div1 Easy: PointsOnCircle

過去問, 練習 | 12:52 |

300点問題・・・普通にやってたらTLE

• r^2の約数のうち、4で割って1ないし3余るものを全てカウントする必要があるが
• 約数すべて求める・・・
• やみくもに割っていくのは時間的に間に合わない
• 素因数分解して、4で割って余りの出る約数を全部見て行くか
• コーディングに時間かかったけどシステムテスト一発通過。122.65点
• Project Eulerではよくある処理だったのでSchemeでは書いた気がするが・・・ライブラリを整備したい

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

ll primes[44721];// 357768 bytes
int primes_cnt;

int e_sieve(int till)
{
  vector<bool> sieve(till+1,true);
  primes_cnt = 0;

  sieve[2] = true;
  primes[primes_cnt++] = 2;

  for (int prime=3;;) {
    primes[primes_cnt++] = prime;
    for (int i=prime*3;i<=till;i+=(prime*2)) sieve[i] = false;

    int next_prime = -1;
    for (int j=prime+2; j<=till; j+=2) {
      if (sieve[j]) { next_prime = j; break; }
    }

    if (next_prime == -1) break;
    prime = next_prime;
  }

  return primes_cnt;
}

map<int,int> prime_factors(int n)
{
  map<int,int> factors;
  for (int i=0; i<primes_cnt; i++) {
    int prime = primes[i];
    while (n % prime == 0) {
      if(found(factors,prime)) factors[prime]++;
      else factors[prime]=1;
      n /= prime;
    }
    if (n==1) return factors;
  }
  factors[n] = 1; return factors;
}

vector<ll> divisors(map<int,int> pfs){
  set<ll> s;
  s.insert(1LL);
  
  tr(pfs,it){
    ll prime=(ll)it->first,mx=it->second,n=1LL;
    set<ll> t(all(s));
    rep(i,mx) {
      n *= prime;
      tr(s,st) t.insert(n*(*st));
    }
    s=t;
  }
  vector<ll> ans(all(s));
  return ans;
}

class PointsOnCircle {
 public:
  long long count(int r) {
    // 素数を準備
    e_sieve((int)sqrt(r));

    // rを素因数分解; 2000000000 => { 2 => 10, 5 => 9 } 
    map<int,int> pfs=prime_factors(r);

    // r^2を素因数分解、というかrの結果を２乗。
    // ４で割って余りが出るものだけにしたいので、
    // ここで 2^k の係数を1以下に限定する。
    // => { 2 => (20→)1, 5 => 18 } 
    tr(pfs,it){
      it->second *= 2;
      if(it->first==2) it->second=min(2,it->second);
    }
    // 素因数分解の結果から約数を求める
    vector<ll> ds = divisors(pfs);

    // 4*(d1(n)-d3(n))を求める
    ll c=0LL;
    tr(ds,it){
      int rm=(*it)%4;
      if(rm==1) c++;
      else if(rm==3) c--;
    }
    return c<<2;
  }
};

SRM366 Div1 Easy: ChangingSounds

過去問, 練習 | 05:33 |

231.62点。（7'55") // Passed System Test

変数名を打ち込む時間が勿体ない。使ってないマクロを消す時間が勿体ない。

class ChangingSounds {
 public:
  int maxFinal(vector<int> changeIntervals, int beginLevel, int maxLevel) {
    int n=sz(changeIntervals);
    bool lev[2][maxLevel+1];
    rep(i,maxLevel+1) lev[0][i]=lev[1][i]=false;
    lev[0][beginLevel]=true;
    rep(s,n){
      int ci=changeIntervals[s];
      rep(i,maxLevel+1) lev[(s+1)%2][i]=false;
      rep(i,maxLevel+1) {
        if(lev[s%2][i]){
          if(i+ci<=maxLevel) lev[(s+1)%2][i+ci]=true;
          if(i-ci>=0) lev[(s+1)%2][i-ci]=true;
        }
      }
    }
    for(int i=maxLevel;i>=0;i--){
      if(lev[n%2][i]) return i;
    }
    return -1;
  }
};

SRM367 Div1 Easy: ObtainingDigitK

過去問, 練習 | 04:49 |

速攻でsubmitできた(248.28point)、と思ったら問題読めてなかった。問題文のテストケースは通るがFailed System Test...

• 場合分けしようかと思ったが、全桁計算した方が確実な気が
• 二度目のsubmit（148.80point）でPassed System Test

#define rep(var,n)  for(int var=0;var<(n);var++)

class ObtainingDigitK {
  vector<int> ds;
  int l,k_;
  bool inc(){
    for(int i=l;i>=0;i--){
      if(ds[i]==9){
        ds[i]=0;
        if(k_==0) return true;
      }else{
        ds[i]++;
        return (ds[i]==k_);
      }
    }
    return false;
  }
 public:
  int minNumberToAdd(string originalNumber, int k) {
	l=originalNumber.length(); k_=k;
    ds.resize(l+1);
    ds[0]=0;
    rep(i,l) {
      ds[i+1]=originalNumber[i]-'0';
      if(ds[i+1]==k) return 0;
    }
    for(int i=1;i<=10;i++){
      //cout << "ds: " << ds << endl;
      if(inc()) return i;
    }
    return 222;
  }
};

SRM368 Div1 Easy: JumpingBoard

過去問, 練習 | 03:04 |

3回目のsubmitでやっとSystem Testに通った。

• とりあえずBFSで探索
• 既に通った場所に戻ってきたら無限ループ可能なので-1を返す。が、BFSでやるなら通過履歴はちゃんとクリアしないと駄目
• メモ化しないとTLE

typedef vector<string> vs;
#define sz(a)  int((a).size())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define found(s,e)  ((s).find(e)!=(s).end())

#define xy(x,y) (((x)<<6)|(y))
#define num(c) ((c)=='H')?-1:((c)-'0')

class JumpingBoard {
  vs orig;
  bool bd[50][50];
  int h,w;
  map<int,int> memo;
  
  int sub(int mv,int x,int y){
    int key=xy(x,y);
    if(found(memo,key)) return mv+memo[key];
    if(bd[x][y]) return -1;
    bd[x][y]=true;
    int a=num(orig[y][x]);
    int rmax=mv+1;
    if(x>=a && orig[y][x-a]!='H') {
      int r=sub(mv+1,x-a,y); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    if(x+a<w && orig[y][x+a]!='H') {
      int r=sub(mv+1,x+a,y); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    if(y>=a && orig[y-a][x]!='H') {
      int r=sub(mv+1,x,y-a); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    if(y+a<h && orig[y+a][x]!='H') {
      int r=sub(mv+1,x,y+a); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    bd[x][y]=false;
    memo[key]=rmax-mv;
    return rmax;
  }

 public:
  int maxJumps(vector<string> board) {
    orig=board;
    h=sz(board); w=sz(board[0]);
    mset(bd,0);
    return sub(0,0,0);
  }
};