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;
  }
};

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);
  }
};

2009-08-26

SRM447 div2

12:42

250, 500は素早く解けたのですが、900が間に合いませんでした。これが解けるかどうかで、div1へ上がれるかどうかが分かれる気がします。

あと、レイティングのpercentileが50%を超えていました。これでなんとか、平均よりプログラミングできます、と言えるかな。

Easy - ImportantTasks

タスクとコンピュータの2つの集合が与えられる。タスクの集合はそれぞれタスクの難易度を表しており、コンピュータの集合はその性能を表している。コンピュータはその性能以下の難易度のタスクしか扱えない。また1台のコンピュータは1つ以下のタスクしか扱えない。この条件で、処理できるタスクの個数を返す問題。

それぞれの数列をソートして、コンピュータ視点からでタスクを処理できるか、順に見ていきました。

部屋で一番最初に解けて満足です。

class ImportantTasks {
public:
  int maximalCost(vector <int> complexity, vector <int> computers)
  {
    int ret = 0;
    int mark[complexity.size()];
    memset(mark, 0, sizeof(mark));

    sort(complexity.rbegin(), complexity.rend());
    sort(computers.rbegin(), computers.rend());

    for (int i=0; i<computers.size(); i++)
      {
	for (int j=0; j<complexity.size(); j++)
	  {
	    if (mark[j] == 0 && complexity[j] <= computers[i])
	      {
		ret++;
		mark[j] = 1;
		break;
	      }
	  }
      }

    return ret;
  }
};

Medium - KnightsTour

チェスの盤上でナイトをあるアルゴリズムで動かす。アルゴリズムは:ナイトはブロックされているセルと既に訪れたセルに行くことはできない。ナイトが次に進むセルは、"次の次に進めるセルの候補数"が最小のもの、それが同じなら、行数、列数の少ないものへ進む。というもの。ナイトはいくつのセルを進めるか。

アルゴリズムをそのまま実装するだけで、スピード勝負でした。

class KnightsTour {
public:
  bool inRange(int x, int y)
  {
    bool ret = false;
    if (0<=x && x<8 && 0<=y && y<8)
      ret = true;
    return ret;
  }

  int visitedPositions(vector <string> board)
  {
    int ret = 1;
    vector <string> inaccess = board;
    int x, y;
    int dirs[8][2] = {{-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}};

    for (int i=0; i<board.size(); i++)
      for (int j=0; j<board[i].size(); j++)
	if (board[i][j] == 'K')
	  {
	    x = i;
	    y = j;
	  }

    while (1)
      {
	vector <pair <int, int> > candidates;
	vector <pair <int, pair <int, int> > > c;

	inaccess[x][y] = '*';

	for (int i=0; i<8; i++)
	  if (inRange(x+dirs[i][0], y+dirs[i][1]) && inaccess[x+dirs[i][0]][y+dirs[i][1]] != '*')
	    candidates.push_back(make_pair(x+dirs[i][0], y+dirs[i][1]));

	for (int i=0; i<candidates.size(); i++)
	  {
	    int cx = candidates[i].first;
	    int cy = candidates[i].second;
	    int accNum = 0;
	    for (int j=0; j<8; j++)
	      if (inRange(cx+dirs[j][0], cy+dirs[j][1]) && inaccess[cx+dirs[j][0]][cy+dirs[j][1]] != '*')
		accNum++;

	    c.push_back(make_pair(accNum, candidates[i]));
	  }

	sort(c.begin(), c.end());

	if (c.empty())
	  break;
	else
	  {
	    x = c[0].second.first;
	    y = c[0].second.second;
	    ret++;
	  }
      }

    return ret;
  }
};

Hard - ImportsList

あるスクリプトAは、別のスクリプトBをインポートする。このとき、スクリプトBはスクリプトCをインポートしていたとすると、スクリプトAはBとC両方にアクセスできる。このルールのもと、スクリプトの集合と、それぞれのスクリプトがアクセスする必要がある別のスクリプトの一覧が与えられる。この一覧の条件を満たし、インポートする数は最小化するという条件の元で、それぞれのスクリプトがインポートすべき数の集合を返す。

それぞれのスクリプトがインポートしなければならないスクリプトの数を、小さい方から順に調べていく方法でまず実装してみました。Yが1のスクリプトを調べていき、次に2、3という具合です。ちゃんと証明せず、決めうちで始めたので、間違っている可能性が高いです。特に、必要なスクリプト数が複数のときの処理。今は、できるだけインポート数が少なくなるよう、できるだけ多くのスクリプトにアクセスできるスクリプトから順にインポートするようにしているのですが、これでいいんだろうか。

まだ実行時にエラーが出ます。あとで直す。

class ImportsList {
public:
  bool contain(vector <int> s, vector <int> d)
  {
    bool ret = true;
    for (int i=0; i<d.size(); i++)
      if (find(s.begin(), s.end(), d[i]) != s.end())
	{
	  ret = false;
	  break;
	}
    return ret;
  }

  vector <int> eraseElem(vector <int> s, vector <int> d)
  {
    vector <int> ret = s;
    for (int i=0; i<d.size(); i++)
      ret.erase(find(ret.begin(), ret.end(), d[i]));

    return ret;
  }

  vector <int> importsCount(vector <string> requires)
  {
    vector <int> ret;
    vector <int> yNums;
    vector <vector <int> > imlists(requires.size());
    vector <vector <int> > accessible;
    int yMax = 0;

    for (int i=0; i<requires.size(); i++)
      {
	int tc = 0;
	for (int j=0; j<requires[i].size(); j++)
	  if (requires[i][j] == 'Y')
	    tc++;
	yNums.push_back(tc);
	yMax = max(yMax, tc);
      }

    for (int i=0; i<requires.size(); i++)
      accessible[i].push_back(i);

    for (int i=1; i<=yMax; i++)
      {
	for (int j=0; j<yNums.size(); j++)
	  {
	    if (yNums[j] == i)
	      {
		vector <int> req;
		vector <pair <int, int> > can;
		for (int k=0; k<requires[j].size(); k++)
		  if (requires[j][k] == 'Y')
		    req.push_back(k);

		while (!req.empty())
		  {
		    for (int k=0; k<accessible.size(); k++)
		      if (accessible[k].size() <= req.size())
			if (contain(req, accessible[k]))
			  can.push_back(make_pair(accessible[k].size(), k));

		    sort(can.rbegin(), can.rend());

		    req = eraseElem(req, accessible[can[0].second]);
		    imlists[j].push_back(can[0].second);
		    for (int k=0; k<accessible[can[0].second].size(); k++)
		      accessible[j].push_back(accessible[can[0].second][k]);
		  }
	      }
	  }
      }

    for (int i=0; i<imlists.size(); i++)
      ret.push_back(imlists[i].size());

    return ret;
  }
   

};

Challenge phase

特に何もおこりませんでした。250で致命的な間違いをしている人は、早々に撃墜されてしまっていたし、システムテストで落ちている人は1人しかいませんでした。問題の難易度が低めのスピードレースだったせいだと思います。

Rating

1015 -> 1094 に上がることができました。あと100あがれば青色です。

2009-08-20

arenaがエラーで起動しなくなった問題

00:18

なんかarenaを起動しようとすると、"Application error, Unable to launch the application"と出て、起動しなくなりました。

解決法

結論から言うと、"Java preference"を起動し、"Network"タブの"Delete files..."ボタンを押して、キャッシュファイル?を消去すればなおりました。

原因

エラーがおこったのはこんな状況です。はじめ、有線のlanでつなぎながらarenaに入っていたんですが、突然それが切れました。その後こんどは無線lanからつなぎ、arenaに入ろうとしたんですが、上記のエラーが発生しました。よっておそらく、有線のlanでつなごうとする設定やキャッシュが残っていたため、起動できなかったんだと思います。

2009-08-14

SRM446 div2

23:18

本番には参加できなかったため、プラクティスルームでの練習です。

Easy - SoldierLabeling

1~nまでの整数のうち、桁数が lowerBound 以上 upperBound 以下のものの個数を返す問題。そのまんまです。

class SoldierLabeling {
public:
  int count(int n, int lowerBound, int upperBound)
  {
    int ret = 0;
    int lowN = (int)pow(10.0, (lowerBound - 1));
    int upN = (int)pow(10.0, upperBound) - 1;
    int up = min(n, upN);

    ret = max(0, up - lowN + 1);

    return ret;
  }
};

Medium - CubeWalking

各面が3 x 3のセル状になっているの立方体の上を、ロボットが移動する。各セルには色が付けられている。またロボットの動き方は3つの命令 - 右90度か移転、左90度回転、1セル前進 - から成りたっている。ロボットの初期位置と命令のシーケンスが与えられるので、移動後のロボットの位置のセルの色を返す。

各命令ごとにロボットの向いている方向と一の座標を更新していき、最後にそのセルの色を返すというストレートなアプローチです。500点問題にしては簡単ですね。

class CubeWalking {
public:
  string finalPosition(string movement)
  {
    string color[3][3] = {{"RED", "BLUE", "RED"}, 
			  {"BLUE", "GREEN", "BLUE"}, 
			  {"RED", "BLUE", "RED"}};
    int walk[4][2] = {{0, 2}, {1, 0}, {0, 1}, {2, 0}};
    int x = 1, y = 1;
    int dir = 0;

    for (int i=0; i<movement.size(); i++)
      {
	if (movement[i] == 'L')
	  dir = (dir + 1) % 4;
	else if (movement[i] == 'R')
	  dir = (dir + 3) % 4;
	else
	  {
	    x = (x + walk[dir][0]) % 3;
	    y = (y + walk[dir][1]) % 3;
	  }
      }

    return color[x][y];
  }
};

2009-08-05

SRM410 div2

00:00

ひさびさの過去問練習。ところで、今週末のSRMは飲み会後で次の日サマソニというスケジュールなので不安です。

Easy - ContiguousCacheEasy

ファイルとメモリとキャッシュがあって、メモリへ読み込むファイルの順番が与えられる。キャッシュにヒットせず、ファイルからの読み込みが何回おこるか。

与えられるキャッシュの仕組みがシンプルなので、地道にそのまま実装するだけでいいと思います。ただ、境界条件(キャッシュの内容と次に読み込むファイルに重複があるかないか)をミスってしまって、やたら時間がかかってしまいました。

class ContiguousCacheEasy {
public:
  int bytesRead(int n, int k, vector <int> addresses)
  {
    int base = 0;
    int ret = 0;

    for (int i=0; i<addresses.size(); i++)
      {
      int oldbase = base;
	if (base + (k-1) < addresses[i])
	  {
	    base = min(addresses[i] - (k - 1), n - (k-1));
	    if (oldbase + (k-1) < base)
	      ret += k;
	    else
	      ret += (int)abs(base - oldbase);
	  }
	else if (addresses[i] < base)
	  {
	    base = max(0, addresses[i]);
	    if (base + (k-1) < oldbase)
	      ret += k;
	    else
	      ret += (int)abs(base - oldbase);
	  }
      }

    return ret;
  }
};

Medium - AddElectricalWires

ノードの集合がある。初期状態でどのノード同士がつながっているかが与えられる。また、特別なノードgridConnectionsが与えられる。gridConnections同士は直接・間接につながってはいけない。この条件のもと、できるだけ多くのノードをつなぎたい。最大いくつのノードのコネクションを追加できるか。

まず初期状態で、各ノードがgridConnectionsのどのノードのグループに位置するかをラベル付けします。次に、まだどこにも属していないノードを、先ほどラベル付けしたグループのうち、最も数の多いグループに加えます。こうすることでアークの数を最大化できます。次に各グループごとに、combination(グループのノード数, 2)を計算し、全てのグループの計算結果を総和します。これが最大のつなぎ方をしたときのアークの数になります。最後に初期状態で既につながっていたアークの数を計算結果から引きます。

それほど複雑なアルゴリズムではないんですが、コードは長くなってしまいました。もっとすっきり書けそうです。

class AddElectricalWires {
public:
  int com(int n, int r)
  {
    int i, j;
    int result[r+1], tmp[r+1];

    for (i=0; i<=r; i++)
      {
	result[i] = 0;
	tmp[i] = 0;
      }

    result[0] = 1;

    for (i=1; i<=n; i++)
      {
	tmp[0] = 1;

	for (j=1; j<=r; j++)
	  tmp[j] = result[j-1] + result[j];

	for (j=0; j<=r; j++)
	  result[j] = tmp[j];
      }

    return result[r];
  }

  int maxNewWires(vector <string> wires, vector <int> gridConnections)
  {
    int ret = 0;
    int already = 0;
    int label[wires[0].size()];
    memset(label, -1, sizeof(label));

    for (int i=0; i<wires[0].size()-1; i++)
      for (int j=i+1; j<wires[i].size(); j++)
	if (wires[i][j] == '1')
	  already++;

    for (int i=0; i<gridConnections.size(); i++)
      {
	stack <int> s;
	s.push(gridConnections[i]);
	label[gridConnections[i]] = gridConnections[i];

	while (!s.empty())
	  {
	    int cur = s.top();
	    s.pop();

	    for (int j=0; j<wires[cur].size(); j++)
	      if (wires[cur][j] == '1')
		if (label[j] == -1)
		  {
		    s.push(j);
		    label[j] = gridConnections[i];
		  }
	  }
      }

    int nonlabel = 0;
    vector <int> counter(wires[0].size());
    for (int i=0; i<wires[0].size(); i++)
      if (label[i] == -1)
	nonlabel++;
      else
	counter[label[i]]++;

    sort(counter.begin(), counter.end());

    counter[wires[0].size()-1] += nonlabel;

    for (int i=0; i<counter.size(); i++)
      ret += com(counter[i], 2);

    return ret - already;
  }
   

};