naoya_t@topcoder

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

過去問マラソン | 11:44 |

四日(坊主)目。

昨日も一昨日も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:

//