Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-09-29

CactusCount

| 01:12 | CactusCount - TopCoder煮ブログ を含むブックマーク はてなブックマーク - CactusCount - TopCoder煮ブログ

DIV2 で5人しか答えられなかった CactusCount にチャレンジ。答えを導くコードは書けたものの、O(n^2) ぐらいで n=200 のときに時間かかりすぎ。

諦めて答えをみて勉強中。全体3位の人のソースが読みやすかったので読解。

「ループを探すにはDFS(深さ優先探索)で経路を記録すればよい」

なるほど。BFS(幅優先探索)でやろうとして破綻してた。DFS と BFS の性質を体で理解せねば。