Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2010-09-15

SRM 482

| 04:18

成績・ソース(要ログイン)


24:00 Start

Room 32. eomoleさんと一緒の部屋。青い人が多くてびっくり

24:10 Easy

ある数列から、k個ごとに数字をとって消した新しい数列を作る、というのを最初の数列=[1...N]、k=2, 3, 4...でやったときに、一番最後に残る数字は何か、という問題。

N=2000000なので、厳しいけどシミュレーションでとけるかも。数列をsetで持って、eraseしていけばいい。実装。

-> Examples合う。 -> N=2000000でTLE.

一番最初の操作で奇数がすべて消されるのは自明なので、最初の数列を偶数のみにし、k=3から始めるようにして高速化。N=1のときは場合分け。

-> N=2000000で1.95sec. まあいいか、と思って提出。205.68.

しばらく他に方法がないか考えるが、思いつかない。不安を抱えたまま500へ。


24:30 Medium

ハノイの塔を解くアルゴリズムがAとBと二種類与えられて、A方式でk回円盤を動かしたときの状態になるのは、B方式で何回円盤を動かしたときになるかを答えよ、という問題。Aは典型的なやつで、Bはハノイの塔で作れるすべての状態を経由することが保証されている。

読んで、若干考えたけど、これって再帰で適当に合わせれば良くない?

とりあえずAでk回円盤を動かした状態を作る(n<=19なのでシミュレーションで余裕)。

その作った状態で、

1. sourceのところに一番大きい円盤がある -> Bの1番目の再帰の中に答えがある。

2. spareのところに一番大きい円盤がある -> Bの2番目の再帰の中に答えがある。

3. targetのところに一番大きい円盤がある -> Bの3番目の再帰の中に答えがある。

というのがわかるので、一番大きい円盤を順次消しながら再帰で答えをだす。

等号と不等号を取り違えてちょっと時間を浪費。提出。262.97.


Hard

Unopened.


Challenge

ぱっと見怪しそうなひとは居るけど、明らかにアウトな人はいない。

TLEを攻めるのも怖いし、結局challengeはなし。


Result

205.68+262.97+0.00+0.00=468.65 80位(部屋1位)

1808 -> 1913

250通ってすごく助かった。

Review

250は二分探索でできるらしい。シミュレーションでも、listを使えばもっと速かった。というか、配列でも十分。