Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-27

過去問マラソン(#4):SRM147

| 11:44 | 過去問マラソン(#4):SRM147 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#4):SRM147 - naoya_t@topcoder 過去問マラソン(#4):SRM147 - naoya_t@topcoder のブックマークコメント

四日(坊主)目。

昨日も一昨日もHardは問題名しか見てない...けどとりあえず先に進むよ。

// 先に昨日試作したビット列処理クラスのエントリを書くなどしたよ

Easy(350): PeopleCircle

  • なぜ350点
  • それはさておき
  • 簡単な実装問題なはずなのに18分...orz
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class PeopleCircle {
 public:
  string order(int numMales, int numFemales, int K) {
    int n=numMales+numFemales, rest=n;
    vector<char> ring(n,'M');
    K--;
    int here=0;
    rep(i,numFemales){
      // skip K men
      int skipped=0;
      while(skipped<K){
        if(ring[(here++)%n]=='M') skipped++;
      }
      // skip Fs // ←これが入ってなくて答えが合わず悩んだ
      while (1){
        if(ring[(here)%n]=='F') here++; else break;
      }
      ring[here%n] = 'F';
      rest--;
    }
    return string(all(ring));
  }
};

Medium(500): Dragons

  • 問題自体は平易。
  • 分数を表現するクラスが欲しい
  • 45ラウンドやった時の分子と分母の最大がlong longに収まるか ... Bignumが要るか要らないか →Test case見てると要らないみたい
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()

// Fraction class definition here...

class Dragons {
 public:
  string snaug(vector<int> initialFood, int rounds) {
    vector<vector<Fraction> > bowl(2,vector<Fraction>(6));
    rep(i,6) {
      bowl[0][i].init(initialFood[i]);
      bowl[1][i].init(0,1);
    }
    enum { FR=0, BK,UP,DN,LF,RG };
    
    rep(r,rounds){
      int i0=r%2, i1=(r+1)%2;

      bowl[i1][FR] = (bowl[i0][UP] + bowl[i0][DN] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][BK] = (bowl[i0][UP] + bowl[i0][DN] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][UP] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][DN] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][LF] + bowl[i0][RG])/4;
      bowl[i1][LF] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][UP] + bowl[i0][DN])/4;
      bowl[i1][RG] = (bowl[i0][FR] + bowl[i0][BK] + bowl[i0][UP] + bowl[i0][DN])/4;
    }
    return bowl[rounds%2][UP].desc();
  }
};
  • 分子が0の時に "0" ではなく "0/xxxx" な表記になっててsystest failed x 1
  • Fractionクラスは別エントリにて。submit時には必要最小限に削らないと30%ルールに引っかかるよ
  • 各面のinitialFoodを0〜3にして45ラウンド回してみたら分母の最大は70368744177664 (=2^46) だった。55ラウンドなら72057594037927936 (=2^56)。
    • 要するに 2^(ラウンド数+1)...0ラウンドで1, 1ラウンド回すと4、次から2倍ずつ
    • というわけでlong longでおk

Hard:

//

Fraction - 分数を表現するクラス

23:45 | Fraction - 分数を表現するクラス - naoya_t@topcoder を含むブックマーク はてなブックマーク - Fraction - 分数を表現するクラス - naoya_t@topcoder Fraction - 分数を表現するクラス - naoya_t@topcoder のブックマークコメント

  • テンプレート
  • TにBignum(自家製)を入れても動く(けどまあ遅いね)
//
// Fraction.h - (c)2009 by naoya_t
//
// ライセンスは NYSL 0.9982に従います http://www.kmonos.net/nysl/
//
#include <vector>
#include <string>
#include <sstream>
using namespace std;

template <typename T> T gcd(T m, T n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  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;
  }
}

template <typename T> class Fraction {
  T numer, denom;
 public:
  Fraction(){ init(0,1); }
  Fraction(T n, T d=1){ init(n,d); }
  Fraction(const Fraction<T>& other){ init(other); }

  Fraction<T>& init(T n, T d); // impl.below
  Fraction<T>& init(const Fraction<T>& other); // impl.below

  Fraction<T> operator+(const Fraction<T>& other) const; // impl.below
  Fraction<T> operator-(const Fraction<T>& other) const; // impl.below
  Fraction<T> operator*(const Fraction<T>& other) const; // impl.below
  Fraction<T> operator/(const Fraction<T>& other) const; // impl.below

  Fraction<T> operator+(T n) const { return Fraction<T>(numer+denom*n, denom); }
  Fraction<T> operator-(T n) const { return Fraction<T>(numer-denom*n, denom); }
  Fraction<T> operator*(T n) const { return Fraction<T>(numer*n, denom); }
  Fraction<T> operator/(T n) const { return Fraction<T>(numer, denom*n); }

  Fraction<T>& operator=(const Fraction<T>& other){ return init(other); }
  Fraction<T>& operator+=(const Fraction<T>& other); // impl.below
  Fraction<T>& operator-=(const Fraction<T>& other); // impl.below
  Fraction<T>& operator*=(const Fraction<T>& other) {
    return init(numer * other.numer, denom * other.denom); }
  Fraction<T>& operator/=(const Fraction<T>& other) {
    return init(numer * other.denom, denom * other.numer); }

  Fraction<T>& operator+=(T n){ return init(numer+denom*n, denom); }
  Fraction<T>& operator-=(T n){ return init(numer-denom*n, denom); }
  Fraction<T>& operator*=(T n){ return init(numer*n, denom); }
  Fraction<T>& operator/=(T n){ return init(numer, denom*n); }

  string desc() const; // impl.below
};

/// implementation
template <typename T> Fraction<T>&
Fraction<T>::init(T n, T d)
{
  if (d < 0) n=-n, d=-d;
  if (n == 0) {
    numer = 0, denom = 1;
  } else {
    T g = gcd(n,d);
    numer = n / g, denom = d / g;
  }
  return *this;
}

template <typename T> Fraction<T>&
Fraction<T>::init(const Fraction<T>& other){
  numer = other.numer, denom = other.denom;
  return *this;
}

template <typename T> Fraction<T>
Fraction<T>::operator+(const Fraction<T>& other) const
{
  T g = gcd(denom, other.denom), l = denom / g * other.denom;
  T n = numer * (other.denom / g) + other.numer * (denom / g);
  return Fraction(n, l);
}

template <typename T> Fraction<T>
Fraction<T>::operator-(const Fraction<T>& other) const
{
  T g = gcd(denom, other.denom), l = denom / g * other.denom;
  T n = numer * (other.denom / g) - other.numer * (denom / g);
  return Fraction(n, l);
}

template <typename T> Fraction<T>
Fraction<T>::operator*(const Fraction<T>& other) const
{
  T n = numer*other.numer, l = denom*other.denom;
  return Fraction(n,l);
}

template <typename T> Fraction<T>
Fraction<T>::operator/(const Fraction<T>& other) const
{
  T n = numer*other.denom, l = denom*other.numer;
  return Fraction(n,l);
}

template <typename T> Fraction<T>&
Fraction<T>::operator+=(const Fraction<T>& other)
{
  T g = gcd(denom, other.denom), l=denom/g*other.denom;// l=denomm*other.denom/gcd
  T n = numer*(other.denom/g) + other.numer*(denom/g);
  return init(n,l);
}

template <typename T> Fraction<T>&
Fraction<T>::operator-=(const Fraction<T>& other)
{
  T g = gcd(denom, other.denom), l = denom/g*other.denom;// l=denomm*other.denom/gcd
  T n = numer*(other.denom/g) - other.numer*(denom/g);
  return init(n,l);
}

template <typename T> string
Fraction<T>::desc() const
{
  stringstream ss;
  ss << numer;
//if (denom != 1) ss << "/" << denom; // oops!
  if (numer != 0 && denom != 1) ss << "/" << denom;
  return ss.str();
}

template <typename T> ostream& operator<<(ostream &s, Fraction<T> fr)
{
  s << fr.desc(); return s;
}

Bignum

23:45 | Bignum - naoya_t@topcoder を含むブックマーク はてなブックマーク - Bignum - naoya_t@topcoder Bignum - naoya_t@topcoder のブックマークコメント

前に作ったやつに少し手を加えた

//
// Bignum.h - (c)2009 by naoya_t
//
// ライセンスは NYSL 0.9982に従います http://www.kmonos.net/nysl/
//
#include <vector>
#include <string>
#include <sstream>
using namespace std;

class Bignum {
  int sign;
  int size;
  vector<int> values;

  int default_radix_;
  int remainder_;

 public:
  Bignum(int val=0){set(val);default_radix_=10;}
  Bignum(string val, int radix=10){set(val,default_radix_=radix);}
  Bignum(const Bignum& num){set(num);}
  Bignum(int sg,const vector<int> &vals,int radix=0){set(sg,vals,radix);}

  Bignum& operator=(int val){ set(val); return *this; }
  Bignum& operator=(string val){ set(val,default_radix_); return *this; }
  Bignum& operator=(const Bignum& num){ set(num); return *this; }

  void set( int val );
  void set( string val, int radix=10 );
  void set( const Bignum& num );
  void set( int sg, const vector<int> &vals, int radix=0 );

 private:
  bool is_zero() const { return (size==1 && values[0]==0)? true : false; };
  void set_zero();
  void normalize();

  char enc(int n) const { return n<10 ? '0'+n : 'A'+(n-10); }
  int dec(int ch) const { return ch<='9' ? ch-'0' : 10+ch-'A'; }

 public:
  void set_default_radix(int radix) { default_radix_=radix; }
  int get_default_radix() { return default_radix_; }

  string sdump() const;
  void dump() { cout << sdump(); }

  Bignum abs() const { Bignum num(*this); num.sign = 1; return num; }
  Bignum minus() const { Bignum num(*this); if (!is_zero()) num.sign = -num.sign; return num; }

  int cmp(const Bignum &n) const;
  int cmp_abs(const Bignum &n) const;

  int to_i();
  string to_s(int radix=10) const;

  Bignum operator+(const Bignum& rop) const { Bignum newnum(*this); newnum += rop; return newnum; }
  Bignum operator-(const Bignum& rop) const { Bignum newnum(*this); newnum += rop.minus(); return newnum; }
  Bignum operator*(const Bignum& rop) const { Bignum newnum(*this); newnum *= rop; return newnum; }
  Bignum operator/(const Bignum& rop) const { Bignum newnum(*this); newnum /= rop; return newnum; }

  Bignum operator-(){ return Bignum(this->minus()); }

  Bignum operator+(int rop) const { Bignum num(*this); num += rop; return num; }
  Bignum operator-(int rop) const { Bignum num(*this); num -= rop; return num; }
  Bignum operator*(int rop) const { Bignum num(*this); num *= rop; return num; }
  Bignum operator/(int rop) const { Bignum num(*this); num /= rop; return num; }
  Bignum operator%(int rop) const { Bignum num(*this); num %= rop; return num; }

  bool operator==(const Bignum& rop) const { return cmp(rop)==0; }
  bool operator!=(const Bignum& rop) const { return cmp(rop)!=0; }
  bool operator>(const Bignum& rop) const { return cmp(rop)>0; }
  bool operator>=(const Bignum& rop) const { return cmp(rop)>=0; }
  bool operator<(const Bignum& rop) const { return cmp(rop)<0; }
  bool operator<=(const Bignum& rop) const { return cmp(rop)<=0; }

  Bignum& operator+=(const Bignum& num);
  Bignum& operator-=(const Bignum& num){ return operator+=(num.minus()); }
  Bignum& operator*=(const Bignum& num);
  Bignum& operator/=(const Bignum& num);
  Bignum& operator%=(const Bignum& num);

  Bignum& operator+=(int n);
  Bignum& operator-=(int n){ return operator+=(-n); }
  Bignum& operator*=(int n);
  Bignum& operator/=(int n);
  Bignum& operator%=(int n);
  int remainder(){ return remainder_; }

  Bignum add(const Bignum& n){ Bignum num(*this); num += n; return num; }
  Bignum sub(const Bignum& n){ Bignum num(*this); num += n.minus(); return num; }
  Bignum mul(const Bignum& n){ Bignum num(*this); num *= n; return num; }
  Bignum div(const Bignum& n){ Bignum num(*this); num /= n; return num; }

  Bignum add(int n){ Bignum num(*this); num += n; return num; }
  Bignum sub(int n){ Bignum num(*this); num += (-n); return num; }
  Bignum mul(int n){ Bignum num(*this); num *= n; return num; }
  Bignum div(int n){ Bignum num(*this); num /= n; return num; }
};

ostream& operator<<(ostream &s, const Bignum& b)
{
  s << b.to_s(); return s;
}

///
void
Bignum::set(int val){
  if (val == INT_MIN) {
    values.resize(size = 2);
    sign = -1;
    values[0] = 0; values[1] = 0x8000;
  } else {
    if (val < 0) { sign = -1; val = -val; } else sign = 1;
    if (val >= 65536) {
      values.resize(size = 2);
      values[0] = val % 65536; values[1] = val >> 16;
    } else {
      values.resize(size = 1);
      values[0] = val;
    }
  }
}

void
Bignum::set_zero(){
  values.resize(size = 1);
  size = 1; sign = 1; values[0] = 0;
}

void
Bignum::set(const Bignum& num){
  values.assign(num.values.begin(), num.values.end());
  sign = num.sign; size = num.size; default_radix_ = num.default_radix_;
}

void
Bignum::set(int sg,const vector<int> &vals,int radix){
  if (radix == 0) {
    size=1;
    for(int i=0,s=vals.size();i<s;i++) if (vals[i]>0) size=i+1;
    values.assign(vals.begin(), vals.begin()+size);
    sign = is_zero()? 1 : sg;
  } else {
    set_zero();
  }
}

int
Bignum::to_i() {
  switch(size){
    case 1:
      return sign * values[0];
    case 2:
      if (values[1]<=0x7fff)
        return sign * ((values[1]<<16) | values[0]);
      else if (values[1]==0x8000 && values[0]==0 && sign==-1)
        return INT_MIN;
      else
        ; // else ; thru
    default:
      return INT_MAX+1;
  }
}

string
Bignum::sdump() const {
  stringstream ss;
  ss << ((sign > 0) ? "+" : "-") << hex << uppercase;
  for (int i=0;i<size;i++) {
    if (i>0) ss << ":";
    ss << values[size-i-1];
  }
  ss << "<" << size << ">";
  return ss.str();
}

int
Bignum::cmp(const Bignum &n) const {
  if(sign != n.sign) return (sign - n.sign)/2;
  return sign * cmp_abs(n);
}

int
Bignum::cmp_abs(const Bignum &n) const {
  if(size!=n.size)
    return size - n.size;
  for(int i=size-1;i>=0;i--)
    if(values[i]!=n.values[i]) return values[i] - n.values[i];
  return 0;
}

Bignum&
Bignum::operator+=(const Bignum &n){
  if(n.is_zero()) return *this;
  if(sign == n.sign) {
    if(size < n.size) {
      values.resize(n.size);
      for(int i=size;i<n.size;i++) values[i]=0;
      size = n.size;
    }
    // simple addition
    for(int i=0;i<n.size;i++) values[i] += n.values[i];
  } else {
    if(cmp_abs(n) >= 0) {
      for(int i=0;i<n.size;i++) {
        if (values[i] >= n.values[i]) {
          values[i] -= n.values[i];
        } else {
          int pl=i+1;
          for(int j=i+1;j<n.size;j++) if(values[j]>0){ pl=j; break; }
          for(int j=pl;j>i;j--) { values[j]--; values[j-1]+=65536; }
          values[i] -= n.values[i];
        }
      }
    } else {
      Bignum t(n);
      set(t + *this);
    }
  }
  normalize();
  return *this;
}

Bignum&
Bignum::operator*=(const Bignum &n){
  if(is_zero()) return *this;
  if(n.is_zero()){ set_zero(); return *this; }
  sign *= n.sign;

  vector<int> tmp(size + n.size, 0);
  for(int i=n.size-1;i>=0;i--){
    int ni = n.values[i];
    for(int j=size-1;j>=0;j--){
      unsigned int ij = (unsigned int)ni * values[j];
      tmp[i+j] += ij % 65536;
      tmp[i+j+1] += ij >> 16;
    }
  }
  values.assign(tmp.begin(), tmp.end());
  size += n.size;
  normalize();
  return *this;
}

Bignum&
Bignum::operator/=(const Bignum& num)
{
  //  cout << "Bignum::/= is not implemented yet..." << endl;
  Bignum quotient(0);
  Bignum _num = num.minus();
  while (sign == 1 && !is_zero()) { *this += _num; quotient+=1; }
  if (sign == -1) quotient-=1;

  set(quotient);
  return *this;
}
Bignum&
Bignum::operator%=(const Bignum& num)
{
  //cout << "Bignum::%= is not implemented yet..." << endl;
  // assert(this >= 0)
  // assert(num > 0)
  Bignum _num = num.minus();
  while (sign == 1 && !is_zero()) *this += _num;
  if (sign == -1) *this += num;
  return *this;
}

///
Bignum&
Bignum::operator+=(int n){
  if (n==0) return *this;
  if (sign*n<0){
    int m=this->to_i();
    if (m!=INT_MAX+1){
      set(m + n);
      return *this;
    }
  }
  if(sign==-1) n=-n;
  values[0] += n;
  normalize();
  return *this;
}

Bignum&
Bignum::operator*=(int n)
{
  if(n==0){ set_zero(); return *this; }
  if(n==1){ return *this; }
  if(n==-1){ sign=-sign; return *this; }
  if(n<0){ sign=-sign; n=-n; }
  for(int i=0;i<size;i++) values[i]*=n;
  normalize();
  return *this;
}

Bignum&
Bignum::operator/=(int n)
{
  if(n==0){ set_zero(); return *this; } // NaN
  if(n==1){ return *this; }
  if(n==-1){ sign=-sign; return *this; }
  if(n<0){ sign=-sign; n=-n; }
  int r = 0;
  for(int i=size-1; i>=0; i--){
    int v = (r << 16) + values[i];
    r = v % n;
    values[i] = v / n;
  }
  normalize();
  remainder_ = r;
  return *this;
}

void
Bignum::normalize()
{
  unsigned int overflown=0;
  int sz=1;
  for(int i=0;i<size;i++){
    if (values[i]>0) sz=i+1;
    if (values[i]<0) {
      if (i==size-1) {
        // underflow
        sign=-sign;
        values[i]=-values[i];
        for (int j=i-1;j>=0;j--){
          //...
        }
      } else {
        // borrowable
        int b=-values[i];
        values[i+1] -= (b >> 16);
        if (b&0xffff){
          values[i+1]--;
          values[i] = 65536 - b;
        } else {
          values[i] = 0;
        }
      }
    }
    if (values[i]>=65536){
      if (i==size-1) overflown = values[i] >> 16;
      else values[i+1] += values[i] >> 16;
      values[i] %= 65536;
    }
  }
  if (overflown == 0) {
    if (sz<size) values.resize(size=sz);
    if (is_zero()) sign=1;
  } else if (overflown < 65536){
    values.resize(size+1);
    values[size++] = overflown;
  } else {
    values.resize(size+2);
    values[size++] = overflown % 65536;
    values[size++] = overflown >> 16;
  }
}

string
Bignum::to_s(int radix) const {
  if (is_zero()) return "0";
  if (radix < 2 || 36 < radix) return "?";

  stack<char> s;
  Bignum tmp(*this);
  while(!tmp.is_zero()){
    tmp /= radix;
    s.push(enc(tmp.remainder()));
  }
  stringstream ss;
  if (sign == -1) ss << "-";
  while(!s.empty()){
    ss << s.top();
    s.pop();
  }
  return ss.str();
}

void
Bignum::set(string val, int radix){
  set_zero();
  if (radix < 2 || 36 < radix) return;
  default_radix_ = radix;

  int l=val.size();
  int start=0, sg=1;
  if(val[0]=='-'){ sg = -1; start++; }
  else if(val[0]=='+') start++;
  for(int i=start,s=val.size();i<s;i++){
    operator*=( radix );
    operator+=( dec(val[i]) );
  }
  normalize();
  sign = sg;
}
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091227