Hatena::Grouptopcoder

cou929のTopCoder日記

2009-09-10

SRM448 div2

23:25

500がとけませんでした!

Easy - TheBlackJackDivTwo

簡単すぎる。特に説明することはなし。

class TheBlackJackDivTwo {
   public:
   int score(vector <string> cards)
  {
    int ret = 0;

    for (int i=0; i<cards.size(); i++)
      {
	if (cards[i][0] == 'T' || cards[i][0] == 'J' || cards[i][0] == 'Q' || cards[i][0] == 'K')
	  ret += 10;
	else if (cards[i][0] == 'A')
	  ret += 11;
	else
	  ret += cards[i][0] - '0';
      }

    return ret;
  }
};

Medium - TheCardShufflingDivTwo

カードのデッキをあるアルゴリズムに沿ってシャッフルしていく。シャッフルをm買い繰り返した後、デッキの最上段のカードは何か。

カードの種類n、繰り返し回数mともに、高々1000000なので、普通にシャッフルの動作を実装して、それをm買い繰り返していては間に合いません。しかし良いアルゴリズムが思いつかず時間切れ。

コンテスト終了後、他の人のコードを見ていて、とてもエレガントなコードがありました。デッキ最上カードの動きに注目して、その法則を見つけて、実装しています。こんな法則があるとは、全く気がつかなかった。

今後こういう問題が出たらどう対応すればいいだろう。今回のように、数列の法則に気づけるひらめきに頼るしかないのか。でもそれじゃあ、応用効かなそうだしなあ。

class TheCardShufflingDivTwo {
public:
  int shuffle(int n, int m)
  {
    int ret = 1;

    if (n % 2 == 1)
      n--;

    for (int i=0; i<m; i++)
      {
	if (ret*2 <=n)
	  ret *= 2;
	else
	  ret = ret*2 - n - 1;
      }

    return ret;
  }
};

Hard - TheCardLineDivTwo

コンテスト中は問題文だけ読んで、実装してません。終わった後にやってみました。

高々16種類のカードが与えられる。このカードを、隣り合うカード同士は数字(1から13)か色(黒か赤)なら並べても良い、というルールのもと並べる。並べ方は何通りあるか。

深さ優先探索と、メモ化で実装してみる。テストケースは大丈夫。でもシステムテストでTLE

再帰関数に毎回setを渡しているのが悪いのかも。他の人はbit演算とかでやってるっぽい。

あと、いかにもDPな問題なので、根本的に間違ってるところがありそう。DPは本当に早々に身につけたいです。

class TheCardLineDivTwo {
public:
  vector <string> cards;
  map <pair <set <int>, string>, int> memo;

  int color(string s)
  {
    int ret = 1;
    if (s[1] == 'C' || s[1] == 'S')
      ret = 0;

    return ret;
  }

  bool canNeighbor(string a, string b)
  {
    bool ret = false;

    if (a[0] == b[0])
      ret = true;
    else if (color(a) == color(b))
      ret = true;

    return ret;
  }

  int r(set <int> s, string last)
  {
    int ret = 0;
    set <int> ts = s;

    if (memo.find(make_pair(s, last)) != memo.end())
      return memo[make_pair(s, last)];

    if (s.empty())
      return 1;

    for (set <int>::iterator i=s.begin(); i!=s.end(); i++)
      {
	if (canNeighbor(last, cards[*i]))
	  {
	    ts.erase(*i);
	    ret += r(ts, cards[*i]);
	    ts.insert(*i);
	  }
      }

    memo[make_pair(s, last)] = ret;
    return ret;
  }

  int count(vector <string> _cards)
  {
    int ret = 0;
    cards = _cards;
    set <int> s;
    for (int i=0; i<cards.size(); i++)
      s.insert(i);

    for (int i=0; i<cards.size(); i++)
      {
	s.erase(i);
	ret += r(s, cards[i]);
	s.insert(i);
      }

    return ret;
  }
};

Challenge phase

以外とみんな慎重で、500を提出している人が少なくて、できませんでした。

Rating

微減で1078になりました。悔しい。