Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-26

SRM327 div2

12:45

Easy - FunnyFence

文字列中のシーケンス(|-|-というふうに|と-が交互に現れる)の最大長を返す問題。問題ありませんでした。

class FunnyFence {
public:
  int getLength(string s)
  {
    int ret = 0;
    for (int i=0; i<s.size(); i++)
      {
	bool preIsHifun = false;;
	if (s[i] == '-')
	  preIsHifun = true;

	int j = i + 1;
	int len = 1;

	while ((preIsHifun && s[j] == '|') || (!preIsHifun && s[j] == '-'))
	  {
	    preIsHifun = !preIsHifun;
	    len++;
	    j++;
	  }

	ret = max(ret, len);
      }
    return ret;
  }
};


Medium - IQTest

IQテストによくある、数列が与えられて次にくる数字は何?という問題を解く。数列の要素(全部でN個)をk1 ~ kNとすると、数列はkn = Kn-1 * p + qと定式化できる。ただしpとqは整数とする。

すべてのpとqの候補を探索し、条件にマッチするものを探すというbruto-forceなやり方で解きました。しかし、探索の範囲を適当に決めていたため、システムテストで一度落ちました。この点を最初にしっかり検討しておく必要がありました。

class IQTest {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  string nextNumber(vector <int> previous)
  {
    vector <pair <int, int> > sols;

    if (previous.size() == 1)
      return "AMBIGUITY";

    for (int i=-1000; i<=1000; i++)
      for (int j=-20000; j<=20000; j++)
	if (previous[0] * i + j == previous[1])
	  {
	    pair <int, int> tmp(i, j);
	    sols.push_back(tmp);
	  }

    for (int i=1; i<previous.size()-1; i++)
      for (int j=0; j<sols.size(); j++)
	if (previous[i] * sols[j].first + sols[j].second != previous[i+1])
	  {
	    sols.erase(sols.begin() + j);
	    j--;
	  }

    set <int> next;
    for (int i=0; i<sols.size(); i++)
      next.insert( previous[previous.size()-1] * sols[i].first + sols[i].second);

    if (sols.size() == 0)
      return "BUG";

    if (next.size() > 1)
      return "AMBIGUITY";

    return toStr(*next.begin());
  }
};

SRM422 div2

12:36

Easy - MultiNumber

ある整数を2つのパートにわけ(1234を12と34など)、左右それぞれの数字を掛け合わせる(1*2と3*4など)。左右の計算結果が等しければ"YES"、異なれば"NO"を返す。

全ての組み合わせについて調べるという方法で、そのまま実装しました。

class MultiNumber {
public:
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}
  string check(int number)
  {
    string ret = "NO";
    string n = toStr(number);

    for (int i=1; i<n.size(); i++)
      {
	int productL = 1, productR = 1;

	for (int j=0; j<i; j++)
	  productL *= n[j] - '0';

	for (int j=i; j<n.size(); j++)
	  productR *= n[j] - '0';

	if (productL == productR)
	  {
	    ret = "YES";
	    break;
	  }
      }

    return ret;
  }
};

Medium - PrimeSoccer

AとBの2チームがある。それぞれ18回得点のチャンスがあり、2チームそれぞれ一回ごとに得点できる確率が与えられる。少なくとも1チームが、素数得点をあげる確率を求める。

18以下の正の整数のみ扱えばいいので、両チームとも非素数得点をとる確率を計算し、1からマイナスすればokです。

 1 - \sum_{i \in S} _{18}C_{i} \times ProbOfTeamA \times (1 - ProbOfTeamA) \times \sum_{i \in S} _{18}C_{i} \times ProbOfTeamB \times (1 - ProbOfTeamB)

tex記法を使ってみました。Sは18以下の非素数です。

class PrimeSoccer {
public:
  double combination(int n, int r)
  {
    int i, j;
    double result[r+1], tmp[r+1];

    for (i=0; i<=r; i++)
      {
	result[i] = 0;
	tmp[i] = 0;
      }

    result[0] = 1;

    for (i=1; i<=n; i++)
      {
	tmp[0] = 1;

	for (j=1; j<=r; j++)
	  tmp[j] = result[j-1] + result[j];

	for (j=0; j<=r; j++)
	  result[j] = tmp[j];
      }

    return result[r];
  }

  double getProbability(int skillOfTeamA, int skillOfTeamB)
  {
    int notPrimes[12] = {0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18};
    double probA = 0, probB = 0;
    double skillA = (double)skillOfTeamA / 100, skillB = (double)skillOfTeamB / 100;

    for (int i=0; i<12; i++)
      {
	probA += combination(18, notPrimes[i]) * pow(skillA, notPrimes[i]) * pow(1 - skillA, 18 - notPrimes[i]);
	probB += combination(18, notPrimes[i]) * pow(skillB, notPrimes[i]) * pow(1 - skillB, 18 - notPrimes[i]);
      }

    return 1 - probA * probB;
  }
};