Hatena::Grouptopcoder

cou929のTopCoder日記

2009-08-31

SRM302 div2

01:56

Prime Numbers, Factorization and Euler Function

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

Hard - DivisorInc

問題文は省略。

この問題のポイントは幅優先探索を書けるかどうか。その中でも個人的につまづいたのは2点で、ひとつはすべての約数を導出する部分。例えばNの約数(1とN以外)を出すとき、

for (int i=2; i<=N/2; i++)
  if (N % i == 0)
    {
      // N/i の操作
    }

このように、N/2までループすると、とても遅く、今回の問題だとTLEになる。そこで、

for (int i=2; i*i<=N; i++)
  if (N % i == 0)
    {
      // N/i の操作
      // i の操作
    }

こうすると、ループを少なくすることができる。

もう一点は素数の判定。Mが素数のとき-1を返すようにしていたら、N=Mのときに間違った答えを返すことになった(正解は0)。

チュートリアルで紹介されていたから素数を使うのかと思ったんだけど、今回も特にチュートリアルで学んだことが活かせる部分はなかった。こんなことなら、先にDPとかグラフの練習をした方がいい気がしてきた…。

class DivisorInc {
public:
  int countOperations(int N, int M)
  {
    int ret = -1;
    queue <int> q;
    int t[100001];
    memset(t, -1, sizeof(t));
    t[N] = 0;

    q.push(N);

    while (!q.empty())
      {
	int cur = q.front();
	q.pop();
  
	if(cur == M)
	  {
	    ret = t[cur];
	    break;
	  }

	for (int i=2; i*i<=cur; i++)
	  if (cur % i == 0)
	    {
	      if (cur + i <= M && t[cur + i] == -1)
		{
		  t[cur + i] = t[cur] + 1;
		  q.push(cur + i);
		}
	      if (cur + cur / i <= M && t[cur + cur / i] == -1)
		{
		  t[cur + cur / i] = t[cur] + 1;
		  q.push(cur + cur / i);
		}
	    }
      }

    return ret;
  }
};

SRM259 div2

16:53

Prime Numbers, Factorization and Euler Function

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

Medium - PrimePolynom

引数A, B, Cが与えられ、A*M^2 + B*M + C が素数でない最小のM(正の整数)を返す。

exampleでMの最大値が80と与えられているので、0から80までループし、解が素数かどうか調べるだけです。

チュートリアルとの関連は、素数の判定です。これならチュートリアルを読む前からで来たと思うので、あまり練習にならなかった。

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

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

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

    int s = (int)sqrt(n);

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

    return true;
  }

  int reveal(int A, int B, int C)
  {
    int ret = 0;

    for (int i=0; i<=80; i++)
      if (!isPrime(i*i*A + i*B + C))
	{
	  ret = i;
	  break;
	}

    return ret;
  }
};

Easy - CompetitionStatistics

チュートリアルとは関係ないですが、ついでに。

あるプレイヤーのレイティングの変化の時系列が与えられる。連続してレイティングが上がった最大の期間を返す。

簡単すぎでした。

class CompetitionStatistics {
public:
  int consecutiveGrowth(vector <int> ratingChanges)
  {
    int ret = 0;
    int increase = 0;

    for (int i=0; i<ratingChanges.size(); i++)
      if (ratingChanges[i] > 0)
	increase++;
      else
	{
	  ret = max(ret, increase);
	  increase = 0;
	}

    if (increase > 0)
      ret = max(ret, increase);

    return ret;
  }
};

Hard - NumericalSequence

こちらもチュートリアルとは関係ないですが、ついでに。

回文状の数列を作る。また、数列状の隣り合う二つの要素を、その和で置き換えることができる。与えられた数列を回文状にするには、この操作を最小何回行えば良いか。

数列の最大要素数が50なので、幅優先探索で全探索することはできない。いいアルゴリズムが思いつかないので、DPかなーと思いながらeditolialsをみてみると、「数列の両端を調べ、等しければ除く。等しくなければ、小さい方の値を操作し増加させる」というアルゴリズムが紹介されていました。これはシンプルでいいですね。

class NumericalSequence {
public:
  int makePalindrome(vector <int> sequence)
  {
    int ret = 0;

    while (sequence.size() > 1)
      {
	int left = sequence[0];
	int right = sequence[sequence.size()-1];

	if (left == right)
	  {
	    sequence.erase(sequence.begin());
	    sequence.erase(sequence.end()-1);
	  }
	else
	  {
	    if (left < right)
	      {
		int tmp = sequence[0] + sequence[1];
		sequence.erase(sequence.begin());
		sequence.erase(sequence.begin());
		sequence.insert(sequence.begin(), tmp);
	      }
	    else
	      {
		int tmp = sequence[sequence.size()-1] + sequence[sequence.size()-2];
		sequence.erase(sequence.end()-1);
		sequence.erase(sequence.end()-1);
		sequence.push_back(tmp);
	      }
	    ret++;
	  }
      }

    return ret;
  }
};


SRM239 div2

09:36

Prime Numbers, Factorization and Euler Function

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

Hard - DivisibilityCriteria

問題文は省略。

各桁数のPの倍数を作ることができれば解けると思ったけれど、最大18桁なので難しい。Editorialsを見ると、すごくシンプルなコードだったけど、理解できない。この問題とチュートリアルとの関連も謎。うーん。

class DivisibilityCriteria {
public:
  vector <int> multipliers(int N, int P)
  {
    vector <int> ret(1, 1);
    int mul = 1;

    for (int i=1; i<N; i++)
      {
	mul = (mul * 10) % P;
	ret.push_back(mul);
      }

    reverse(ret.begin(), ret.end());

    return ret;
  }
};