Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-08

SRM338 div2(過去問)

15:21

Easy - BinaryIncrementation

'0'と'1'のみから成る文字列が与えられる。これは2進数を表現している。この数に1を足し、同様のフォーマットで返す。

問題文の通りに実装しました。他には、引数を数値に変換し、1を足し、また文字列に戻すという方法もあると思います。

  string plusOne(string x)
  {
    string ret = "0";
    ret += x;

    int cur = ret.size() - 1;
    while (cur >= 0)
      {
	if (ret[cur] == '0')
	  {
	    ret[cur] = '1';
	    break;
	  }
	else
	  {
	    ret[cur] = '0';
	    cur--;
	  }
      }

    if (ret[0] == '0')
      ret.erase(0, 1);

    return ret;
  }

SRM339 div2(過去問)

09:58

Easy - BettingStrategy

問題文が長く、細かいところをきちんと読まなかったせいで、システムテストに落ちました。betを途中で打ち切るタイミングを勘違いしていました。

  int finalSum(int initSum, string outcome)
  {
    int ret = initSum;
    int bet = 1;

    for (int i=0; i<outcome.size(); i++)
      {
	if (outcome[i] == 'W')
	  {
	    ret += bet;
	    bet = 1;
	  }
	else
	  {
	    ret -= bet;
	    bet *= 2;
	    if (ret - bet < 0)
	      break;
	  }
      }
    return ret;
  }

Medium - ProblemsToSolve

通し番号付きの問題集が与えられる。問題は順番に解くか、1つとばしに解くことができる。また0問目は必ず解かなければいけない。intのベクタpleasantnessと整数varietyが与えられる。pleasantnessは各問題の満足度?である。順に問題を解いていき、既に解いた問題の最大と最小の満足度の差がvariety以上であれば、問題集をやめてよい。そうでなければ、全問解く必要がある。解くべき最小の問題数を求めよ。

戦略:pleasantnessから2つの要素を選び、その差がvariety以上ならば、必要な問題数を計算し、保存する。この操作を全ての組み合わせに対して行う。最小値を返す。

簡単そうに思えたのですが、意外に難しかったです。submit->system testを何度か繰り返してしまいました。特に、最初に見つかった解が最適ではないケースが、テストケースに含まれていなかったので、ここでつまずきました。

  int getProbNum(int r, int l)
  {
    int ret = 0;

    // rとlの間にある、解くべき問題数
    ret += 2;
    ret += (l - r - 1) / 2;

    // 0とrの間にある、解くべき問題数
    if (r != 0)
      {
	ret++;
	ret += (r - 1) / 2;
      }

    return ret;
  }

  int minNumber(vector <int> pleasantness, int variety)
  {
    int ret = pleasantness.size();

    for (int i=1; i<pleasantness.size(); i++)
      {
	bool found = false;
	for (int j=0; j<i; j++)
	  {
	    if (abs(pleasantness[i] - pleasantness[j]) >= variety)
	      {
		ret = min(getProbNum(j, i), ret);
		found = true;
	      }
	  }
	if (found)
	  break;
      }

    return ret;
  }