cou929のTopCoder日記

SRM350 div2 (過去問)

11:00

Medium - SumsOfPerfectPowers

n = a^m + b^k (ただし各変数は非負、m, kは2以上) を満たすnを sum of two perfect powers と定義する。2つのint型の引数lowerBound, upperBound間の整数のうち、sum of two perfect powersとなる値の数を返す。lowerBound, upperBoundは1から5000000までの範囲。

最初に全てのsum of two perfect powersのリストを作り、求める値がそこにあるかを調べる戦略でいくことに。リストはsetで実装しました。

  int howMany(int lowerBound, int upperBound)
  {
    int i;
    set <int> p;
    set <int> pp;
    set <int>::iterator si;
    set <int>::iterator sj;
    int ret = 0;

    for (i=0; i*i<=upperBound; i++)
      {
	if (i <= 1)
	  p.insert(i);
	else
	  {
	    long long n = i*i;
	    while (n <= upperBound)
	      {
		p.insert(n);
		n *= i;
	      }
	  }
      }

    for (si=p.begin(); si!=p.end(); si++)
       for (sj=si; sj!=p.end(); sj++)
          if (*si + *sj <= upperBound)
	     pp.insert(*si + *sj);

    for (i=lowerBound; i<=upperBound; i++)
       if (pp.find(i) != pp.end())
	  ret++;

    return ret;
  }

しかしこのままでは、lowerBoundが1、upperBoundが5000000というワーストケースではTLEでした。最後のfind()で調べてカウントしている部分が重いので、boolの配列にフラグを立てる方法に代えました。

  int howMany(int lowerBound, int upperBound)
  {
    int i;
    set <int> p;
    set <int>::iterator si;
    set <int>::iterator sj;
    int ret = 0;

    bool used[5000001];
    memset(used, false, sizeof(used));

    for (i=0; i*i<=upperBound; i++)
      {
	if (i <= 1)
	  p.insert(i);
	else
	  {
	    long long n = i*i;
	    while (n <= upperBound)
	      {
		p.insert(n);
		n *= i;
	      }
	  }
      }

    for (si=p.begin(); si!=p.end(); si++)
      for (sj=si; sj!=p.end(); sj++)
	if (*si + *sj <= upperBound)
	  used[*si + *sj] = true;

    for (i=lowerBound; i<=upperBound; i++)
      ret += used[i];

    return ret;
  }

この変更で大丈夫でした。ワーストケースでも実行時間は約100msでした。

1~5000000の場合、答えは149070。よって上記のfind()を使うアルゴリズムだと、ほとんどの場合find()はリストの最後まで探索することになります。よって、約 4850000^2 というオーダーの計算量になるということだと思います。これは時間がかかるはずです。

Easy - DistanceBetweenStrings

文字間の距離を、(n1 - n2)^2、ただしn1は文字列aでの文字nの頻度、n2は文字列bでの文字nの頻度と定義する。文字列a, b, lettersetが与えられたとき、letterset内の各文字の距離の総和を返すという問題。

この問題ポイントは文字の頻度を数える部分だけだなと思い、そこの部分はmapで実装。テストケースも全て通り、サブミットするも、システムテストで落ちました。原因は大文字と小文字を区別しないという条件を忘れていたからでした。うっかりしてたと思いつつ、tolower()を追加し、無事システムテストも通りました。ただ、今回のテストケースでは、大文字小文字を区別"する"アルゴリズムでも正しい答えがでちゃうところがいやらしいなあと思いました。

  int getDistance(string a, string b, string letterSet)
  {
    int i;
    map <char, int> am;
    map <char, int> bm;
    int ret = 0;

    for (i=0; i<a.size(); i++)
      am[tolower(a[i])]++;

    for (i=0; i<b.size(); i++)
      bm[tolower(b[i])]++;

    for (i=0; i<letterSet.size(); i++)
      ret += (am[letterSet[i]] - bm[letterSet[i]])*(am[letterSet[i]] - bm[letterSet[i]]);

    return ret;
  }