Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-20

SRM329 div2

11:42

Easy - VowelEncryptor

文字列の中から母音を取り除く。ただし、母音のみの文字列の場合は、取り除かない。

問題の条件さえ間違わなければ大丈夫です。

class VowelEncryptor {
public:
  vector <string> encrypt(vector <string> text)
  {
    vector <string> ret;

    for (int i=0; i<text.size(); i++)
      {
	string s;

	for (int j=0; j<text[i].size(); j++)
	  if (text[i][j] != 'a' && text[i][j] != 'i' && text[i][j] != 'u' && text[i][j] != 'e' && text[i][j] != 'o')
	    s += text[i][j];

	if (s.empty())
	  s = text[i];

	ret.push_back(s);
      }

    return ret;
  }
};

Medium - RailroadSeatNumeration

列車の座席の表示方法を統一する問題。

引数は同じ方式(domesticsかinternationals)での表記である」という条件が抜けていたため、一度システムテストに落ちてしまいました。それがちゃんとできていれば、500点の割には簡単だったと思います。

class RailroadSeatNumeration {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  
  string getInternational(vector <int> tickets)
  {
    string ret;
    vector <int> domestics;
    vector <int> internationals;
    int intSeat[] = {1, 3, 4, 6};

    for (int i=0; i<tickets.size(); i++)
      {
	if (tickets[i] <= 36)
	  {
	    int t = (double)tickets[i] / 4 + 0.9;
	    t = t*10 + intSeat[(tickets[i] - 1) % 4];
	    domestics.push_back(t);
	  }

	if (tickets[i] / 10 <= 9 && tickets[i] > 9)
	  if (tickets[i] % 10 == 1 || tickets[i] % 10 == 3 || tickets[i] % 10 == 4 || tickets[i] % 10 == 6)
	    internationals.push_back(tickets[i]);
      }

    if (domestics.size() != tickets.size() && internationals.size() != tickets.size())
      return "BAD DATA";
    else if (domestics.size() == tickets.size() && internationals.size() == tickets.size())
      return "AMBIGUOUS";

    if (domestics.size() == tickets.size())
      for (int i=0; i<domestics.size(); i++)
	ret += toStr(domestics[i]) + " ";

    if (internationals.size() == tickets.size())
      for (int i=0; i<internationals.size(); i++)
	ret += toStr(internationals[i]) + " ";

    ret.erase(ret.end()-1);

    return ret;
  }
};

SRM328 div2

11:42

Easy - MarbleNecklace

与えられた文字列が循環しているリストだとする。例えばABC, BCA, CABは同一。また、逆順も同一(CBA, BAC, ACB)。この中で最も辞書順がはやいものを返す。

そのままの方法でやりました。

class MarbleNecklace {
public:
  string normalize(string necklace)
  {
    vector <string> ret;

    for (int i=0; i<necklace.size(); i++)
      {
	string s;
	s = necklace.substr(i);
	s += necklace.substr(0, i);
	ret.push_back(s);
      }

    reverse(necklace.begin(), necklace.end());

    for (int i=0; i<necklace.size(); i++)
      {
	string s;
	s = necklace.substr(i);
	s += necklace.substr(0, i);
	ret.push_back(s);
      }

    sort(ret.begin(), ret.end());

    return ret[0];
  }
};

Medium - LightsCube

N*N*Nのキューブがある。最初、1以上のキューブのライトがついている。ライトがついているキューブに隣接しているキューブは、同じ色のライトがつく。最初についているライトの座標が与えられる。最終的に、何色のライトが何個ついているかを返す。

毎回ライトを伝播させていき、最終的に何個ついているかを数えるというストレートな方法で解きました。ミスなくできたのですが、時間がかかってしまいました。本番では間に合わなかった。

class LightsCube {
public:
  int N;
  int l[40][40][40];
  int tmp[40][40][40];

  bool inRange(int n)
  {
    if (0 <= n && n < N)
      return true;
    return false;
  }

  int ltotmp()
  {
    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
	for (int z=0; z<N; z++)
	  tmp[x][y][z] = l[x][y][z];
    return 0;
  }

  int tmptol()
  {
    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
	for (int z=0; z<N; z++)
	  l[x][y][z] = tmp[x][y][z];
    return 0;
  }

  vector <int> around(int _x, int _y, int _z)
  {
    map <int, int> m;
    vector <int> ret;
    char dir[2] = {-1, 1};

    for (int i=0; i<2; i++)
      {
	int x = _x + dir[i];
	int y = _y;
	int z = _z;

	if (inRange(x) && inRange(y) && inRange(z))
	  if (l[x][y][z] != -1)
	    m[l[x][y][z]]++;
      }

    for (int i=0; i<2; i++)
      {
	int x = _x;
	int y = _y + dir[i];
	int z = _z;

	if (inRange(x) && inRange(y) && inRange(z))
	  if (l[x][y][z] != -1)
	    m[l[x][y][z]]++;
      }

    for (int i=0; i<2; i++)
      {
	int x = _x;
	int y = _y;
	int z = _z + dir[i];

	if (inRange(x) && inRange(y) && inRange(z))
	  if (l[x][y][z] != -1)
	    m[l[x][y][z]]++;
      }

    for (map <int, int>::iterator i=m.begin(); i!=m.end(); i++)
      ret.push_back(i->first);

    return ret;
  }

  vector <int> count(int _N, vector <string> lights)
  {
    vector <int> ret;
    map <int, int> m;
    memset(l, -1, sizeof(l));
    N = _N;

    for (int i=0; i<lights.size(); i++)
      {
	int x, y ,z;
	sscanf(lights[i].c_str(), "%d %d %d", &x, &y, &z);
	l[x][y][z] = i;
      }

    while (1)
      {
	bool found = false;
	ltotmp();

	for (int x=0; x<N; x++)
	  for (int y=0; y<N; y++)
	    for (int z=0; z<N; z++)
	      if (l[x][y][z] == -1)
		{
		  found = true;
		  vector <int> res = around(x, y, z);
		  if (res.empty())
		    continue;

		  sort(res.begin(), res.end());
		  tmp[x][y][z] = res[0];
		}

	if (!found)
	  break;

	tmptol();
      }

    for (int x=0; x<N; x++)
      for (int y=0; y<N; y++)
	for (int z=0; z<N; z++)
	  m[l[x][y][z]]++;

    for (int i=0; i<lights.size(); i++)
      ret.push_back(m[i]);

    return ret;
  }
};