Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

 | 

2009-12-20

SRM455

06:30 | SRM455 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM455 - tanakhの日記 SRM455 - tanakhの日記 のブックマークコメント

http://www.topcoder.com/stat?c=coder_room_stats&cr=22627322&rd=14179&rm=303038

なんとか致命傷ですんだ

300 149.87 AC

長方形の枠をドーナツと呼ぶ。ドーナツの中にドーナツが、という連鎖の最長を求めよ。サイズは50x50まで。

パッと見で、スコアも変則だし、めんどそうだなあという印象。とりあえずドーナツ候補はO(n^4)個あって、それぞれナイーブに調べるとO(n^5)かかるので、とりあえず適当にO(1)でドーナツ判定ができるようにしておく。でまあDAGの最長パス求めればokかなと書いてたが、DAGの辺の数最悪でO(n^8)までいくじゃん、というのに書いてから気づいて、だめぽ。わからんなあ、とか言いながら30分以上過ぎてしまう。あるドーナツの中に最大何個ドーナツ連鎖があるのかなあというのをDPで求める、という方針で考えていたが、ドーナツの中のドーナツは、そのドーナツのサイズの4乗ぐらい存在するので、うまくいかなさそう。明らかに包含されているドーナツは選ぶ必要がないので、本質的に列挙しなきゃならないドーナツはO(n^2)個ぐらいじゃないかなあと適当に考えたりするが、それでもトータルでO(n^6)かかるし、そもそも効率的な列挙がわからない。

あまりにもわからんのでトイレで一息ついてると、あれこれ、枠のサイズ1減らしていくだけじゃないかと気づく。わかってからは適当に書いて終了。40分近くかかった。ひどいスコア。

550 Opened

三角形の中に六角形が何個あるか?サイズ50万まで。


しばらく考えたが分からず。Level Threeが900なので、900開けてみることに。

900 Opened

900てことは簡単なのかもしれないが、問題文がVery hardだったので、10分ぐらい粘るが題意をつかめず。諦める。

550

nが大きいので、O(n)かO(nlogn)か。小さいのから考えて、1大きいのが求まるんじゃないかとか。サイズがnのときの解をf(n)とすると、f(n)=f(n-1)+(底辺にくっついてる六角形の数)。底辺にくっついてる部分は、nC2-n通りで、それぞれのときの上の組み合わせが単純な式になるのかなあといろいろいじるが数が合わない。どこで折り返すかの数がそれぞれO(1)で求まりそうなんで、結局数があっててもO(n^2)は必要だったかもしれず。たたみこむ方法は分からず。

Challenge Phase

300が遅くてひどい順位だったので、Challengeで頑張るしかない。自分の上に青い人が何人かいたが、(失礼ながら)さすがに全員がこの解法にたどりついたとは思えなかったので、たぶん最大ケースで落ちる人がいるはずと踏む。まず最初に開いた人がO(n^6)回してたぽいので、とりあえずでかいのを投げる。成功。次に開いてた人がよくわからなかったがO(n^5)回してるように見えたので、また投げる。失敗。これは回るのか。もう一人すごいTLEしそうな人がいたが、これはすんでのところで先を越される。二人目に落とし損ねた人のがやっぱりなんかおかしいような感じだったので、じっくり見ることにするが、どういうケースで落ちるのかうまく見極められない。もじもじしている間にほかの人に落とされる。そんなこんなで終了。

感想

私も耄碌したなあという感想。なんでこんな簡単なのがすっと出てこないかなあ。TLEの見極めは難しい。二人目は一人目が成功してたから結構勢いでチャレンジしたけど、もっと慎重に行くべきかも。リーチからの連敗記録++。6連敗か?今年分もあと一回なので、次こそは本当に赤になりたい。

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20091220
 |