Hatena::Grouptopcoder

cou929のTopCoder日記

2009-05-03SRM346 div2(過去問)

Easy - DiamondHunt

'<'と'>'から成る文字列が与えられる。文字列から'<>'(ダイアモンド)を探す。見つかったダイアモンドは文字列から取り除かれる。その際、新しいダイアモンドができる場合もある。文字列に含まれるダイアモンドの数を返す。例えば、'<<>>'の場合2を返す。

文字列からダイアモンドを一つ探し、見つかればそれを取り除く。この作業をダイアモンドがなくなるまで繰り返す、という単純な戦略で実装しました。findやeraseを使うと簡単に実装できます。

  int countDiamonds(string mine)
  {
    int ret = 0;
    size_t pos;

    while (1)
      {
	pos = mine.find("<>");
	if (pos == string::npos)
	  break;
	mine.erase(pos, 2);
	ret++;
      }
    return ret;
  }

Medium - CommonMultiples

整数のセットと、上限値、下限値が与えられる。[下限値, 上限値]の範囲の整数で、整数セット中の全ての整数の倍数となっているものの数を返す。

最も単純な戦略は、[下限値, 上限値]の各整数について、整数セットの各値で割り切れるかをチェックするというもの。しかし、これでは最大 2*10^9*50 回操作があるので、明らかに時間がかかる。よって、整数セットの全ての値の最小公倍数を求め、その最小公倍数の倍数の中から、条件を満たすものの数を数えるという戦略で行いました。

  int gcd(int _a, int _b)
  {
    int a = max(_a, _b);
    int b = min(_a, _b);

    while (b)
      {
	int tmp = a % b;
	a = b;
	b = tmp;
      }

    return a;
  }

  double lcm(int _a, int _b)
  {
    int a = max(_a, _b);
    int b = min(_a, _b);

    return (double)a / gcd(a, b) * b;
  }


  int countCommMult(vector <int> a, int lower, int upper)
  {
    int ret = 0;

    double l = a[0];
    for (int i=1; i<a.size(); i++)
      {
	l = lcm(max((int)l, (int)a[i]), min((int)l, (int)a[i]));
	if (l > 2000000000)
	  return 0;
      }

    if (upper < l)
      return 0;

    ret = upper / l;

    if (l < lower)
      ret -= (int)((lower-1) / l);

    return ret;
  }