Hatena::Grouptopcoder

cou929のTopCoder日記

2009-08-30

SRM223 div2

12:41

Prime Numbers, Factorization and Euler Function

素数のチュートリアルからの練習問題。

Hard - PrimeAnagrams

整数の集合が与えられ、それらを組み合わせて3つの素数を作る。その中から、3つの素数が最小のものを返す。

まずはbrute-forceなアプローチを考える。単に、全ての数の組み合わせを考え、条件を満たすものを返すというもの。ここでなんとなく、全ての組み合わせをやってたらTLEになりそうと感じ、別のアプローチを考える。でも思いつかない。

Editorialsをみると、brute-forceでやってた…。ワーストケースの計算量を見積もってみると、最大8文字なので、8!通りそれぞれについて、7C2通りで3部分に分ける。8! = 40320, 7C2 = 21, よって全部で846720通り。85万くらいだったらたしかに間に合いそう。うーんちゃんと定量的に見積もりすべきだった…。

実装してサブミットしたけども、0を含まない8桁の入力ではTLEしてしまう。よって何カ所か最適化をする。まず、素数判定に昔作ったisPrime()という関数を使っていたけれど、これは毎回計算してちぇっくしているため時間がかかるので、エラトステネスの篩で最初に素数のテーブルを作っておき、それを参照する方式に変更。ちなみに遅かったisPrime()関数はこちら。

bool isPrime(int n)
{
  if (n < 2)
    return false;

  if (n != 2 && n % 2 == 0)
    return false;

  int s = sqrt(n);

  for (int i=3; i<=s; i++)
    if (n % i == 0)
      return false;

  return true;
}

次にstringをintに変換するtoInt()関数も修正。istringstreamを使うと遅かった。修正前のものはこちら。

int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

これでなんとか間に合いました。

この問題、つまずいたポイントは、

  • 計算量の見積もり。まだ感覚ではなく、ちゃんと計算すべき。
  • next_permutation。最初にソートするのを忘れていた。
  • コードの最適化

チュートリアルとの関連部分は、素数判定のところだけど、この問題のポイントはそこではないし、みんな素数を判定する関数くらいは予め作っておいてストックしていると思う。数式的なこともほぼでてこなかったし、素数うんぬんよりはむしろコーディングのエクササイズになった印象です。

class PrimeAnagrams {
public:
  bool primeTable[1000000];
  int MAX;

  int toInt(string s)
  {
    int ret = 0; 
    for (int i=0; i<s.size(); i++)
      ret = ret*10 + (s[i] - '0');
    return ret;
  }

  void gen_primes()
  {
    int i,j;
    for(i=0;i<MAX;i++) primeTable[i] = true;
    primeTable[0] = false;
    primeTable[1] = false;
    for(i=2;i<=(int)sqrt(MAX);i++)
      if (primeTable[i])
	for(j=i;j*i<MAX;j++) primeTable[i*j] = false;
  }

  vector <int> primes(string anagram)
  {
    vector <int> ret;
    vector <vector <int> > candidates;
    MAX = 1000000;
    gen_primes();
    int mini = 1000000000;

    sort(anagram.begin(), anagram.end());
    do {
      if (anagram[0] == '0')
	continue;
      for (int i=0; i<anagram.size()-2; i++)
	{
	  if (anagram[i+1] == '0')
	    continue;
	  for (int j=i+1; j<anagram.size()-1; j++)
	    {
	      if (anagram[j+1] == '0')
		continue;
	      vector <int> t;
	      t.push_back(toInt(anagram.substr(0, i-0+1)));
	      t.push_back(toInt(anagram.substr(i+1, j-i)));
	      t.push_back(toInt(anagram.substr(j+1)));

	      if (primeTable[t[0]] && primeTable[t[1]] && primeTable[t[2]])
		if (mini > t[0] * t[1] * t[2])
		  {
		    mini = t[0] * t[1] * t[2];
		    ret = t;
		  }
	    }
	}
    } while (next_permutation(anagram.begin(), anagram.end()));

    sort(ret.begin(), ret.end());
    return ret;
  }

};


SRM216 div1

10:27

Prime Numbers, Factorization and Euler Function

素数のチュートリアルからの、練習問題。

Medium - Refactoring

整数nを因数分解する。何通りにできるか。例えば24なら、2*2*2*3, 2*2*6, 2*3*4, 2*12, 3*8, 4*6 の6通り。

最初に考えたアルゴリズムは、nを素因数分解し、その結果から組み合わせの数を数えるというもの。しかし、組み合わせの数を数えるスマートな方法が思いつかない。

Editorialsを見ると、再帰で因数分解を求める過程でカウントしている。それを参考に実装。今回のケースでは最適化は必要ないけども、練習のためメモ化も入れた。

チュートリアルとの関連性は、因数分解のアルゴリズムの部分かな。特に素数が必要となる部分はなかった。

class Refactoring {
public:
  map <pair <int, int>, int> memo;

  int count(int n, int last)
  {
    int ret = 0;
    if (memo.find(make_pair(n, last)) != memo.end())
      return memo[make_pair(n, last)];

    for (int i=last; i*i<=n; i++)
      if (n % i == 0)
	ret += count(n/i, i) + 1;

    memo[make_pair(n, last)] = ret;
    return ret;
  }

  int refactor(int n)
  {
    return count(n, 2);
  }
};