Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-27

SRM326 div2

10:02

Easy - AdditionCycles

たとえば26という整数の場合、2+6=8, 6 and 8 -> 68, 6+8=14, 8 and 4 -> 84, 8+4 = 12, 4 and 2 -> 42, 4+2=6, 2 and 6 -> 26 という具合に、このような計算を繰り返すともとの値にもどってくる。何回のイテレーションでもとの値にもどるか。

単純にもとの値に戻るまで繰り返しました。

class AdditionCycles {
public:
  int cycleLength(int n)
  {
    int ret = 0;
    int cur = n;

    while (++ret)
      {
	int tmp = cur/10 + cur%10;
	cur = cur%10 * 10 + tmp%10;
	if (cur == n)
	  break;
      }

    return ret;
  }
};

Medium - PositiveID

ベクトルが何本か与えられるので、2つのベクトル間の類似度を"同じ要素の個数"と定義し、最大の類似度を返す。

ベクトルが高々50、要素数が高々25なので、全探索しても問題なく時間内に終わります。引数からベクトルを生成する部分は、以前作ったsplitという関数コピペすることで時間短縮できました。同一ベクトル内に同じ要素がある場合({aaa, bbb, aaa, ccc}など)を考慮して、setを使ったのですが、システムテストテストケースをちらっと見たところでは、そんなケースはなかったので、setでなく普通にvectorでもよかったかもしれません。また今回は要素の探索にfind()を使ったので問題なかったのですが、ある要素が別の要素のサブセットになっている場合("blond"と"blondie"など)を特に意識していなかったので、もしfind()の部分を自分で実装していたとしたら、ここで引っかかっていたかもしれません。

class PositiveID {
public:
  set <string> split(const string _s, const string del)
  {
    set <string> ret;
    string s = _s;

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

    return ret;
  }

  int maximumFacts(vector <string> suspects)
  {
    int ret = 0;
    vector <set <string> > sus;

    for (int i=0; i<suspects.size(); i++)
      sus.push_back(split(suspects[i], ","));

    for (int i=0; i<sus.size(); i++)
      for (int j=0; j<sus.size(); j++)
	if (i != j)
	  {
	    int c = 0;
	    for (set <string>::iterator it=sus[i].begin(); it!=sus[i].end(); it++)
	      {

		if (sus[j].find(*it) != sus[j].end())
		  c++;
	      }
	    ret = max(c, ret);
	  }

    return ret;
  }
};