kmjp's blog

競技プログラミング参加記です

TopCoder SRM 555 Div1 Easy CuttingBitString、Medium XorBoard

SRM

久々のSRM参加。
ox-で１個Challenge成功して1785→1805でした。
今回SRM 555だったためか5に関するテーマが多めだったね。
http://community.topcoder.com/stat?c=problem_statement&pm=12155
http://community.topcoder.com/stat?c=problem_statement&pm=12180

255 CuttingBitString

2進数の文字列が与えられるので、5の累乗で分割するもの。
最初に1,5,25,125…から文字列を作っておいて、あとはDFSで分割パターンを列挙。
特に問題なし。

class CuttingBitString { 
  char type[50][60]; 
  char str[100]; 
  u64 num[50]; 
  int tl[50]; 
  int nt,sl; 
  int res; 
  int memo[100]; 
   
  public: 
   
  void setb(u64 v,char* s) { 
    char* ps=s; 
    while(v>0) { 
      *s = '0' + (v&1); 
      v>>=1; 
      s++; 
    } 
    *s=0; 
  } 
   
  int dfs(int pos) { 
    int i; 
     
    if(memo[pos]!=-2) return memo[pos]; 
    if(pos==sl) { 
      return 0; 
    } 
     
    int min=999; 
    int v; 
    FOR(i,nt) { 
      if(sl-pos < tl[i]) break; 
      if(memcmp(&str[pos],type[i],tl[i])==0) { 
        v = dfs(pos + tl[i]); 
        if(v<999) { 
          v++; 
          if(v < min) min = v; 
        } 
      } 
       
    } 
    memo[pos]=min; 
    return min; 
  } 
   
  int getmin(string S) { 
    u64 v; 
    int i; 
     
    ZERO(str); 
    FOR(i,100) memo[i]=-2;; 
    FOR(i,S.size()) str[i]=S.c_str()[S.size()-1-i]; 
    sl = strlen(str); 
     
    v=1; 
    nt=0; 
    while(v<(1ULL<<51)) { 
      num[nt]=v; 
      setb(v,type[nt]); 
      tl[nt]=strlen(type[nt]); 
      nt++; 
      v*=5; 
    } 
    res=999; 
    res = dfs(0); 
     
    if(res==999) return -1; 
    return res; 
  } 
};

555 XorBoard

H・Wが与えられ、0で埋まったボードを、列と行を指定回数0/1反転させて1の数がSになるパターンを列挙する。
2回反転させると元に戻るので、列をR、行をC回反転させるとして

WxR + HxC - 2xRxC = S

を満たすR・Cを探し、その数を列挙すればよい。

全反転数をRa・Caとし、２回反転させる数をR2・C2と置くとR2=(Ra-R)/2、C2=(Ca-C)/2となる。

  • １回反転させるパターンは組み合わせで{}_H C_R \times {}_W C_C 回
  • ２回反転させるパターンは重複組み合わせで{}_H H_R_2 \times {}_W H_C_2 回

なのでこれらを掛け算して掛け合わせればよい。

ただ、自分は競技中重複組み合わせの計算方法を知らず、しばらく考えてストップ。
途中でWikipediaを見て{}_n H_m = {}_{n+m-1} C_mと知ったので、なんとかSubmit。

残念ながら、最初のR・Cの列挙にミスがあり、WA。
終了後Practiceで正解したのが下記コードになります。

int mo=555555555;
int Com[3001][3001];

class XorBoard {
	s64 res;
	int rc,cc;
	int hh,ww;
	public:
	
	s64 Co(int n,int m) {
		return Com[n][m];
		
	}
	
	s64 Ha(int n,int m) {
		return Co(n+m-1,m);
	}
	
	
	void add(int y,int x) {
		int ty,tx;
		s64 cy,cx,r;
		
		if(y>rc || x>cc) return;
		if((rc-y)%2==1) return;
		if((cc-x)%2==1) return;
		ty = (rc-y)/2;
		tx = (cc-x)/2;
		r = 1;
		r *= Co(hh,y);
		r %= mo;
		r *= Co(ww,x);
		r %= mo;
		r *= Ha(hh,ty);
		r %= mo;
		r *= Ha(ww,tx);
		r %= mo;
		res += r;
		res %= mo;
	}
	
	int count(int H, int W, int Rcount, int Ccount, int S) {
		int tr,tc;
		int y,x,n,m;
		hh=H; ww=W;
		ZERO(Com);
		Com[0][0]=1;
		
		FOR(n,3000) {
			if(n==0) continue;
			FOR(m,n+1) {
				if(m==0) Com[n][m]=1;
				else Com[n][m]=(Com[n-1][m-1]+Com[n-1][m])%mo;
			}
		}
		
		
		rc=Rcount;
		cc=Ccount;
		tr = min(H,Rcount);
		tc = min(W,Ccount);
		res = 0;
		FOR(y,tr+1) {
			int num = S - W*y;
			if(2*y==H) {
				if(num!=0) continue;
				FOR(x,tc+1) {
					if (x >= 0 && x <= W)add(y,x);
				}
			}
			else {
				if(num % (H-2*y) == 0) {
					x = num / (H-2*y);
					if (x >= 0 && x <= W) add(y,x);
				}
			}
		}
		return (int)res;
	
	}
};

まとめ

重複組み合わせの計算方法を勉強できて良かった。
凡ミスで555落としたのは残念、Challengeを成功したのでギリギリレートが上がった感じ。
今回の問題で555は若干簡単な気がするけど、SRM555のためのお祭りと思えばいいのかな。