Hatena::Grouptopcoder

cou929のTopCoder日記

2009-10-04

SRM408 div2

01:28

Easy - TournamentJudging

同じ長さの数列 rawScores と conversionFactor が与えられるので、 rawScores[i]/conversionFactor[i] (小数点以下は四捨五入)の総和を求めよ。

四捨五入はその数値に0.5を加え、小数点以下を切り捨てることで実現できます。

class TournamentJudging {
public:
  int getPoints(vector <int> rawScores, vector <int> conversionFactor)
  {
    int ret = 0;

    for (int i=0; i<rawScores.size(); i++)
      {
	double d = (double)rawScores[i]/conversionFactor[i];
	ret += (int)(d+0.5);
      }

    return ret;
  }
};

Medium - OlympicCandles

毎日キャンドルに灯をともす。灯をともすキャンドルの数は、1日目は1本、2日目は2本、...、n日目はn本。キャンドルの灯は毎日消すが、一度つけるごとに長さが1減る。キャンドルの長さを表す数列 candles が与えられるので、これらのキャンドルで何日間上記の作業をできるか求める。

できるだけ長いキャンドルから灯をつけていくという、greedyっぽいアルゴリズムで大丈夫です。

class OlympicCandles {
  int getArriveCandleNum(vector <int> candles)
  {
    int ret = 0;

    for (int i=0; i<candles.size(); i++)
      if (candles[i] > 0)
	ret++;

    return ret;
  }

public:
  int numberOfNights(vector <int> candles)
  {
    int ret = 0;

    while (getArriveCandleNum(candles) >= ret+1)
      {
	ret++;

	sort(candles.rbegin(), candles.rend());

	for (int i=0; i<ret; i++)
	  candles[i]--;
      }

    return ret;
  }
};

Hard - MarblesInABag

袋に赤と青の玉が入っており、そこから玉を取り出すゲームをする。自分は赤と青の玉全体から同確率で玉を引き、相手は必ず青い玉を引く。最後に袋から取り出される玉が青ならば自分が勝ち、そう出なければ相手の勝ち。ゲームは自分が先攻ではじまる。赤青両方の玉の個数が与えられた場合、自分が勝つ確率を求める。

メモ化再帰でのアプローチを試みたんですが、一部のテストケースで落ちてしまいます。bad_allocの例外が出ているので、メモに使っているmapが巨大になり、メモリが確保できなくなったのではないかと予想しています。またそれ以前に、ローカルで試したところ時間がかかっているので、メモリがもっとあってもTLEになると思います。別のアプローチを考える必要があるようです。

ちなみに、再帰関数は毎回青をとった場合、赤をとった場合それぞれについて計算しています。メモは最初double memo[4001][4001]という配列を使おうとしましたが、大きすぎて使えなかったのでmapにしています。しかしこれでも結局メモリの上限(確か64M)に達してしまうようです。

一応エラーメッセージもはっておきます。

terminate called after throwing an instance of 'std::bad_alloc'
what():  St9bad_alloc
class MarblesInABag {
public:
  map <pair <int, int>, double>m;

  double r(int red, int blue)
  {
    double ret = 0;

    if (red>blue)
      return 0;

    if (m.find(make_pair(red, blue)) != m.end())
      return m[make_pair(red, blue)];

    ret += ((double)blue/(red+blue)) * r(red, blue-2);
    if (red >= 1)
      ret += ((double)red/(red+blue)) * r(red-1, blue-1);

    m[make_pair(red, blue)] = ret;

    return ret;
  }

  double getProbability(int redCount, int blueCount)
  {
    m[make_pair(0, 1)] = 1;

    return r(redCount, blueCount);
  }
};


SRM156 div2

12:35

Hard - WordParts

originalとcompoundの二つの文字列が与えられる。compoundをいくつかのサブ文字列に分割し、かつ全てのサブ文字列がoriginalのprefixかsuffixになるようにしたい。分割に仕方の最小を求める。

Editorialを見ながら再帰+メモ化で解きました。ポイントは最初にprefixとsuffixを全部詰め込んだ辞書を作ることと、compound文字列の位置だけを持ち回す再帰関数を使う点だと思います。

あと、なぜかローカルのテストでテストケース6だけが、返り値14となって落ちていました。サーバでは正常に意図した値を返しています。テストのコードはTZTesterが自動生成したものそのままです。原因がまだわからず、これで時間を取られました。

class WordParts {
public:
  string comp;
  vector <string> dic;
  int m[100];

  int r(int pos)
  {
    int & ret = m[pos];

    if (m[pos] != -1)
      return m[pos];

    if (pos == comp.size())
      return 0;

    ret = 10000;

    for (int i=0; i<dic.size(); i++)
      if (comp.substr(pos, dic[i].size()) == dic[i])
	ret = min(ret, 1 + r(pos+dic[i].size()));

    return ret;
  }

  int partCount(string original, string compound)
  {
    int ret = 0;
    comp = compound;
    memset(m, -1, sizeof(m));

    for (int i=0; i<original.size(); i++)
      {
	if (i != 0)
	  dic.push_back(original.substr(0, i));
	dic.push_back(original.substr(i));
      }
 
    ret = r(0);

    if (ret > 1000)
      ret = -1;

    return ret;
  }
};