Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-13

SRM331 div2

13:54

Easy - SantaGifts

サンタがプレゼントを、子供たちにどのように配るかという問題。STLの練習問題といったところです。

class SantaGifts {
public:
  vector <string> distribute(vector <string> gifts, int N)
  {
    vector <string> ret(N);

    int limit = min((int)gifts.size(), N*4);
    for (int i=0; i<limit; i++)
      ret[i % N] += gifts[i] + " ";

    for (int i=0; i<N; i++)
      if (ret[i][ret[i].size()-1] == ' ')
	ret[i].erase(ret[i].end()-1);

    return ret;
  }
};

Medium - CarolsSinging

こちらもクリスマスにちなんだ問題。全員が歌えるように、クリスマスキャロルを選曲します。

全ての組み合わせを考えても、高々2^10となるので、brute-forceな戦略がよさそうです。再帰を使ってdfsを実装し、解きました。

class CarolsSinging {
public:
  vector <string> lyrics;
  int ret;

  bool check(vector <int> v)
  {
    bool sang[lyrics.size()];
    memset(sang, false, sizeof(sang));

    for (int i=0; i<lyrics.size(); i++)
      for (int j=0; j<v.size(); j++)
	if (v[j] == 1 && lyrics[i][j] == 'Y')
	  sang[i] = true;

    for (int i=0; i<lyrics.size(); i++)
      if (!sang[i])
	return false;

    int tmp = 0;
    for (int i=0; i<v.size(); i++)
      if (v[i] == 1)
	tmp++;

    ret = min(ret, tmp);

    return true;
  }

  int dfs(int c, vector <int> & v)
  {
    if (c == lyrics[0].size())
      {
	check(v);
	return 0;
      }

    c++;
    v.push_back(0);
    dfs(c, v);
    v.erase(v.end()-1);

    v.push_back(1);
    dfs(c, v);
    v.erase(v.end()-1);

    return 0;
  }

  int choose(vector <string> _lyrics)
  {
    lyrics = _lyrics;
    ret = lyrics.size();
    vector <int> tmp;

    int b = 1 << 3;

    dfs(0, tmp);

    return ret;
  }

その後他の人のコードを見ていると、組み合わせの生成にビットをうまく使っている解法が多く使われていました。このテクニックにはかなり感動しました。この問題では、各キャロルを歌うか歌わないか、その全ての組み合わせが必要です。言い換えると、各要素が0と1をとる数列の、全てのパターンがわかればいいわけです。よって、0から目的のビット数までを順に調べていけば、目的が達成できることになります。例えば、キャロルが3曲の場合、000, 001, 010, 011, 100, 101, 110, 111が得られます。

class CarolsSinging {
public:
  int choose(vector <string> lyrics)
  {
    int ret = lyrics.size();

    for (int i=0; i<(1 << lyrics[0].size()); i++)
      {
	bool sang[lyrics.size()];
	memset(sang, false, sizeof(sang));

	for (int j=0; j<lyrics.size(); j++)
	  for (int k=0; k<lyrics[0].size(); k++)
	    if ((i & 1 << k) && lyrics[j][k] == 'Y')
	      sang[j] = true;

	bool ok = true;
	for (int j=0; j<lyrics.size(); j++)
	  if (!sang[j])
	    ok = false;

	if (ok)
	  ret = min(ret, __builtin_popcount(i));
      }

    return ret;
  }
};

チュートリアルにビットに関する記事があったので、あとで読んでみたいと思います。

A bit of fun: fun with bits