Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-10

SRM335 div2(過去問)

18:15

Easy - Palindromize

回文をつくる問題。文字列の末尾に一文字ずつ追加していき、その度に回文になっているかを判定する戦略でできました。

  bool isPalindrome(string s)
  {
    for (int i=0; i<s.size()/2; i++)
      if (s[i] != s[s.size() - 1 - i])
	return false;

    return true;
  }

  string minAdds(string s)
  {
    string ret;

    for (int i=0; i<s.size(); i++)
      {
	string sub = s.substr(0, i);
	reverse(sub.begin(), sub.end());
	if (isPalindrome(s + sub))
	  {
	    ret = s + sub;
	    break;
	  }
      }

    return ret;
  }

Medium - Multifactorial

Multifactorialという値を計算する。Multifactorial(n, k)はすべて正の n - X*k の積。ただしXは正の整数

doubleでMultifactorialを計算しながら、オーバーフローを検出するという戦略で解きました。ただ、解説記事によると、この解法は正確さの点でトリッキーだそうです。よくわからないのですが、浮動小数点の誤差の関係でしょうか。いまいちよく理解できていません。

  string toStr(long long n) {ostringstream ss; ss << n; return ss.str();}

  double fac(int n, int k)
  {
    double ret = n;

    while (k < n)
      {
	n = n-k;
	ret *= n;
	if (ret > 1000000000000000000.0)
	  return -1;
      }

    return ret;
  }

  string calcMultiFact(int n, int k)
  {
    string ret;

    double f = fac(n, k);

    if (f == -1)
      return "overflow";

    ret = toStr((long long)f);

    return ret;
  }

SRM336 div2(過去問)

11:59

Easy - VowelLatin

引数母音と子音を分離する問題。特に問題なし。

  string translate(string word)
  {
    string vow;
    string nvow;
    for (int i=0; i<word.size(); i++)
      {
	if (word[i] == 'a' ||
	    word[i] == 'i' ||
	    word[i] == 'u' ||
	    word[i] == 'e' ||
	    word[i] == 'o' ||
	    word[i] == 'A' ||
	    word[i] == 'I' ||
	    word[i] == 'U' ||
	    word[i] == 'E' ||
	    word[i] == 'O' )
	  vow += word[i];
	else
	  nvow += word[i];
      }
    return nvow + vow;
  }

Medium - ServiceNames

引数パース、整形する問題。戻り値をアルファベット順にソートする必要があったのですが、それを忘れていてシステムテストに一度落ちてしまいました。

  // stringを文字列delで分離し、ベクタで返す関数
  vector <string> split(const string _s, const string del)
  {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
	size_t pos = s.find(del);
	string sub = "";
	sub = s.substr(0, pos);
	ret.push_back(sub);
	if (pos != string::npos)
	  pos += del.size();
	s.erase(0, pos);
      }

    return ret;
  }

  vector <string> makeList(vector <string> services)
  {
    vector <string> ret;
    map <string, vector <string> > m;

    // 引数をパースし、結果をmapにつめていく
    for (int i=0; i<services.size(); i++)
      {
	vector <string> elems = split(services[i], " ");

        // elems[0]がKindOfInput、elems[1]以降がservice names
	for (int j=1; j<elems.size(); j++)
	  m[elems[j]].push_back(elems[0]);
      }

    // 出力をつくる
    for (map <string, vector<string> >::iterator i=m.begin(); i!=m.end(); i++)
      {	
        // service namesをアルファベット順にソートする
	sort(i->second.begin(), i->second.end());

        // service namesを", "区切りで並べる
	string tmp = i->second[0];
	for (int j=1; j<i->second.size(); j++)
	  tmp += ", " + i->second[j];

        // KindOfInputとservice namesをつなぐ
	ret.push_back(i->first + " ==> " + tmp);
      }

    return ret;
  }