Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2011-07-10

TCO11 R3

| 04:42 | はてなブックマーク -  TCO11 R3 - cafelier@SRM

  • oxx でギリギリ通過。500は凡ミス。1000は境界条件2個ほど間違えてた。
  • 以下清書した物

250

int gcd(int x, int y)
{
   while(x)
      swap(x, y%=x);
   return y;
}

int lcm(int x, int y)
{
   return x/gcd(x,y)*y;
}

class ArtShift { public:
   int maxShifts(string sequence) 
   {
      int B=0, W=0;
      for(int i=0; i<sequence.size(); ++i)
         (sequence[i]=='B' ? B : W)++;
      memo.assign(31*31, set<int>());
      for(int b=0; b<=B; ++b) memo[b*31+0].insert(1);
      for(int w=0; w<=W; ++w) memo[0*31+w].insert(1);
      return *rec(B,W).rbegin();
   }

   vector< set<int> > memo;
   const set<int>& rec(int B, int W)
   {
      set<int>& result = memo[B*31+W];
      if( !result.empty() )
         return result;

      result.insert(B+W);
      for(int b=0; b+b<=B; ++b)
      for(int w=!b; w<=W; ++w) {
         const set<int>& x = rec(b,w);
         const set<int>& y = rec(B-b,W-w);
         for(set<int>::const_iterator it=x.begin(); it!=x.end(); ++it)
         for(set<int>::const_iterator jt=y.begin(); jt!=y.end(); ++jt)
            result.insert(lcm(*it,*jt));
      }
      return result;
   }
};
  • 黒B個白W個で作れる周期を全部setで計算、というDP
  • 周期はせいぜい因数分解したら和が30になる数のパターン数くらいしかないはずなのでそんな多くないはず
  • 実際はもっと素直に全探索でよかったらしい

500

class PrefixFreeSuperset { public:
   long long minSumLength(vector <string> cur, long long k) 
   {
      map<int,LL> open; {
         string me("");
         rec(me, cur, open);
      }

      LL totalLen = 0;
      for(int i=0; i<cur.size(); ++i)
         totalLen += cur[i].size();
      k -= cur.size();

      while(k) {
         if( open.empty() )
            return -1;
         map<int,LL>::iterator it = open.begin(); 
         int lll = it->first;
         LL  ccc = it->second;
         open.erase(it);

         if( k <= ccc ) {
            totalLen += lll*k;
            k         = 0;
         }
         else if( k <= ccc + open[lll+1] ) {
            totalLen += lll*ccc;
            k        -= ccc;
         }
         else if( k <= ccc*2 + open[lll+1] ) {
            LL div = k - (ccc+open[lll+1]);
            open[lll+1] += div*2;
            totalLen += (ccc-div)*lll;
            k        -= (ccc-div);
         }
         else
            open[lll+1] += ccc*2;
      }
      return totalLen;
   }

   void rec(string& me, const vector<string>& prefix, map<int,LL>& open)
   {
      bool iamprefix = false;
      for(int i=0; i<prefix.size(); ++i)
         if( me == prefix[i] )
            return;
         else if( is_prefix(me, prefix[i]) )
            iamprefix = true;
      if( iamprefix )
      {
         me += '0';
         rec(me, prefix, open);
         me.resize(me.size()-1);
         me += '1';
         rec(me, prefix, open);
         me.resize(me.size()-1);
      }
      else
      {
         open[me.size()] ++;
      }
   }

   bool is_prefix(const string& s, const string& t)
   {
      return s.size()<=t.size() && s==t.substr(0,s.size());
   }
};
  • 二分木を探索していって先が空いているノードの深さをとりあえず数える
  • あとは浅いところだけで足りそうならそれで、
  • 足りなかったら浅いところは2分割して使う
  • の繰り返し

1000

template<typename T>
struct DP3x
{
   int N1, N2, N3;
   vector<T> data;
   DP3x(int, int N2, int N3, const T& t = T())
      : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
};

static const int MODVAL = 1000000007;

class RowOfColors { public:
   int countWays(int w, int h, int k) 
   {
      DP3x<LL> dp(w+1, h+1, k+1);
      for(int i=w; i>=0; --i)
      for(int stack=0; stack<=h; ++stack)
      for(int used =0; used <=k; ++used)
         if( i == w )
            dp(i,stack,used) = (stack==1 && used==k ? 1 : 0);
         else {
            LL cnt = 0;
            if(stack+1<=h && used+1<=k) // push new color
               cnt += dp(i+1,stack+1,used+1);
            if(stack) // continue the same color
               cnt += dp(i+1,stack,used);
            if(stack && used+1<=k) // replace top
               cnt += dp(i+1,stack,used+1);
            if(stack>=2) // pop
               cnt += dp(i+1,stack-1,used);
            dp(i,stack,used) = cnt % MODVAL;
         }
      LL v = dp(0,0,0);
      for(int i=1; i<=k; ++i)
         v = (v*i) % MODVAL;
      return int(v);
   }
};
  • こんな感じに
RGR
RRR

RGBGRYCYR
RGGGRYYYR
RRRRRRRRR
  • 高さhあればh段のネストまでできるので、
  • という感じで(何段ネスト,何色使った,今何桁目まで決めた)をキーにDP
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20110710
 | 

presented by cafelier/k.inaba under CC0