Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-14

SRM330 div2

11:22

Easy - Sortness

sortnessを計算する問題。ソートされた後の位置との差が大きいほどsortnessは大きくなる。問題文通りに実装すれば解ける。

class Sortness {
public:
  double getSortness(vector <int> a)
  {
    double ret = 0;
    for (int i=0; i<a.size(); i++)
      {
	int sortness = 0;
	for (int j=0; j<a.size(); j++)
	  {
	    if (j < i)
	      if (a[j] > a[i])
		sortness++;

	    if (j == i)
	      continue;

	    if (i < j)
	      if (a[i] > a[j])
		sortness++;
	  }
	ret += sortness;
      }

    return ret / (double)a.size();
  }
};

Medium - Arrows

文字列に含まれる矢印の最大長を返す問題。450点問題だったので、とても簡単だった。

class Arrows {
public:
  string s;
  int getArrowLength(int pos, int dir)
  {
    int ret = 1;

    if (dir == 0)
      {
	for (int i=pos+1; i<s.size(); i++)
	  {
	    if (s[i] == '<' || s[i] == '>')
	      break;

	    if (s[i] == s[pos+1])
	      ret++;
	    else
	      break;
	  }
      } 
    else if (dir == 1)
      {
	for (int i=pos-1; i>=0; i--)
	  {
	    if (s[i] == '<' || s[i] == '>')
	      break;

	    if (s[i] == s[pos-1])
	      ret++;
	    else
	      break;
	  }
      }

    return ret;
  }

  int longestArrow(string _s)
  {
    s = _s;
    int ret = -1;
    for (int i=0; i<s.size(); i++)
      if (s[i] == '<')
	ret = max(ret, getArrowLength(i, 0));
      else if (s[i] == '>')
	ret = max(ret, getArrowLength(i, 1));

    return ret;
  }
};

Hard - NextPalindromicNumber

引数以上の数で、回文となっている数を返す問題。

とりあえずナイーブなアルゴリズムを実装しました。引数をインクリメントしていき、回文になっているかを判定するというものです。しかし、大きな数ではあきらかにTLEになってしまいます。あとで考えるかも。

class NextPalindromicNumber {
public:
  bool isPal(string s)
  {
    if (s.size() == 1)
      return true;

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

    return true;
  }

  string plusone(string s)
  {
    bool up = true;
    for (int i=1; i<=s.size(); i++)
      {
	if (s[s.size()-i] != '9')
	  {
	    int c = s[s.size()-i] - '0';
	    s[s.size()-i] = c + 1 + '0';
	    up = false;
	    break;
	  }
	else
	  s[s.size()-i] = '0';
      }

    if (up)
      s.insert(s.begin(), '1');

    return s;
  }

  string getNext(string n)
  {
    while (1)
      {
	n = plusone(n);
	if (isPal(n))
	  break;
      }

    return n;
  }
};