cafelier@SRM

TCO11 R3

SRM | 04:42 |

• 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