SRM555

255 - XorBoardDivTwo

■問題
'0'と'1'のみで作られた長方形が与えられます。
その長方形の任意の横一列と縦一列の要素を反転させた時、その長方形に含まれる'1'の最大数を求めなさい。

■解法
縦一列、横一列の組み合わせを全通り試す。
一列見ていって'1'だったら-1、'0’だったら+1される。
ただし、選んだ縦と横の交点は反転の反転で元に戻るので無視する。

■ソース

テンプレート省略

  int theMax(vector <string> board) {
    int result;
    int all = 0;
    int best = -10000;
    for(int i=0;i<board.size();i++){
      for(int j=0;j<board[0].size();j++){
	int temp =0;
	if(board[i][j] == '1') all++;
	for(int k=0;k<board[0].size();k++){
	  if(j==k)continue;
	  if(board[i][k]=='1')temp--;
	  else temp++;
	}
	for(int k=0;k<board.size();k++){
	  if(i==k)continue;
	  if(board[k][j]=='1')temp--;
	  else temp++;
	}
	best = max(best,temp);
      }
    }
    result = all + best;
    return result;
  }

555 - CuttingBitString

■問題
1と0のみでなる文字列が与えられます。この文字列を5の累乗の2進数ずつ分けていった時、最小何個にわけられますか？

■解法
50文字以下なので5^23までの2進数を求めておく。
後は普通にdpやるだけ

■ソース
直角二等辺三角形みたいなのは気にしてはいけない

  int ss;
  int dp[100];
  string sd;
  string f[23];

  int getmin(string S) {
    int result;
    for(int i=0;i<100;i++)dp[i]=0;
    ss = S.size();
    sd = S;
    f[0]  = "1";
    f[1]  = "101";
    f[2]  = "11001";
    f[3]  = "1111101";
    f[4]  = "1001110001";
    f[5]  = "110000110101";
    f[6]  = "11110100001001";
    f[7]  = "10011000100101101";
    f[8]  = "1011111010111100001";
    f[9]  = "111011100110101100101";
    f[10] = "100101010000001011111001";
    f[11] = "10111010010000111011011101";
    f[12] = "1110100011010100101001010001";
    f[13] = "1001000110000100111001110010101";
    f[14] = "101101011110011000100000111101001";
    f[15] = "11100011010111111010100100110001101";
    f[16] = "10001110000110111100100110111111000001";
    f[17] = "1011000110100010101111000010111011000101";
    f[18] = "110111100000101101101011001110100111011001";
    f[19] = "100010101100011100100011000001001000100111101";
    f[20] = "10101101011110001110101111000101101011000110001";
    f[21] = "1101100011010111001001101011011100010111011110101";
    f[22] = "1000011110000110011110000011001001101110101011001001";
    result = solve(0);
    if(result>100) result = -1;
    return result;
  }

  int solve(int m){
    if(dp[m]>0) return dp[m];
    if(ss==m)return 0;
    if(ss<m)return 111111;
    int res = 111111;
    for(int i=0;i<23;i++){
      int j;
      for(j=0;j<f[i].size() && m+j<ss;j++){
	if(f[i][j]!=sd[m+j])break;
      }
      if(j==f[i].size()){
	res = min(res,solve(m+j)+1);
      }
    }
    return dp[m] = res;
  }

●余談
ゾロ目回で、初med＆初2完で嬉しかった。
785 -> 887
灰色脱却を目指したい。
翻訳サイトを使ってやるなら、全体はgoogle翻訳で怪しいとこだけyahoo翻訳にするとわかりやすい。