2009-12-27

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

四日(坊主)目。

昨日も一昨日も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でおｋ

Hard:

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

23:45 |

テンプレート
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.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;
}

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20091227

naoya_t@topcoder - [過去問マラソン]過去問マラソン...

		2009/12
日	月	火	水	木	金	土
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

naoya_t@topcoder

2009-12-27

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

Easy(350): PeopleCircle

Medium(500): Dragons

Hard:

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

Bignum