Hatena::Grouptopcoder

hotokuの日記@topcoder部 このページをアンテナに追加 RSSフィード

 | 

2012-09-08

SRM 555

| 10:25

最初に書いたeasyがテストケースに通らなくて、何で????てなって、慌てちゃって駄目だった。メンタル大事。

easy

system test failed.

    m = board[0].size();

の部分をboard[1]で提出してた…

全列挙

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

vector<vector<int> > c;
int n, m;

class XorBoardDivTwo{
public:
  void debug(){
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	cout << c[i][j];
      }
      cout << endl;
    }
  }
  int num(vector<string> board, int r, int col){
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	c[i][j] = board[i][j]-'0';
	if(r==i) c[i][j] = c[i][j]^1;
	if(col==j) c[i][j] = c[i][j]^1;
      }
    }
    int ret=0;
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	ret+=c[i][j];
      }
    }
    // debug();
    // cout << ret << endl;
    return ret;
  }
  int theMax(vector <string> board){
    n = board.size();
    m = board[0].size();
    c.resize(n, vector<int>(m));
    int ret = -1;
    for(size_t i = 0; i < n; ++i){
      for(size_t j = 0; j < m; ++j){
	ret = max(ret, num(board, i, j));
      }
    }
    return ret;
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor



medium

幅優先探索。幅優先を書いたのは実は初めてだ。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;

queue<pair<string, int> > x;

string v[] = {"1",
	      "101",
	      "11001",
	      "1111101",
	      "1001110001",
	      "110000110101",
	      "11110100001001",
	      "10011000100101101",
	      "1011111010111100001",
	      "111011100110101100101",
	      "100101010000001011111001",
	      "10111010010000111011011101",
	      "1110100011010100101001010001",
	      "1001000110000100111001110010101",
	      "101101011110011000100000111101001",
	      "11100011010111111010100100110001101",
	      "10001110000110111100100110111111000001",
	      "1011000110100010101111000010111011000101",
	      "110111100000101101101011001110100111011001",
	      "100010101100011100100011000001001000100111101",
	      "10101101011110001110101111000101101011000110001",
	      "1101100011010111001001101011011100010111011110101",
	      "1000011110000110011110000011001001101110101011001001",
	      "101010010110100000010110001111110000101001010111101101",
	      "11010011110000100001101111001110110011001110110110100001",
	      "10000100010110010101000101100001010000000001010010000100101",
	      "1010010101101111101001011011100110010000000110011010010111001",
	      "110011101100101110001111001001111111010000100000000011110011101"};


class CuttingBitString{
public:
  int bfs(string s, int k){
    for(size_t i = 0; i < 28; ++i){
      if(v[i]==s){
	return k;
      }
      if(s.size() >= v[i].size() &&
	 s.substr(0, v[i].size())==v[i]){
	x.push(make_pair(s.substr(v[i].size(), 100), k+1));
      }
    }
    return -1;
  }

  int getmin(string S){
    x = queue<pair<string, int> >();
    x.push(make_pair(S, 1));
    int k=-1;
    while(x.size()){
      k = bfs(x.front().first, x.front().second);
      if(k>0) return k;
      x.pop();
    }
    return -1;
  }



};



// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

MaVadoMaVado2012/11/15 04:57God, I feel like I suhold be takin notes! Great work

aceumolrumaceumolrum2012/11/16 11:148e7OP3 , [url=http://tiujxmzupahs.com/]tiujxmzupahs[/url], [link=http://qxybcgqfzxvc.com/]qxybcgqfzxvc[/link], http://vaskdacsjgum.com/

ujndyxhamujndyxham2012/11/17 11:54igiTue <a href="http://adlcoeifsfqs.com/">adlcoeifsfqs</a>

ndxwedtubndxwedtub2012/11/17 21:30onU0bu , [url=http://rhcyzrovgklm.com/]rhcyzrovgklm[/url], [link=http://fzggvjadkdvm.com/]fzggvjadkdvm[/link], http://sgafbvxrtbgo.com/

 |