Hatena::Grouptopcoder

じじいのマラソン反省会@TopCoder

ニコニコ生放送:red.cliff.jp
TopCoderでプログラムしてみた(Algorithm Single Round Match専用):http://red.cliff.jp/topcoder.html
 | 

2011-06-29

反省点

00:56

目標が間違ってる

そもそも「計算量をギリギリまで使ったアルゴリズム」が高得点とは限りません。欲しいのはスコアです。大きく勘違いしてます。

スコア分析がだめ!

これ、すごく重要で、初回のマラソンでは出来てたのですが・・・。この問題を「正n角形で、できるだけnが大きい多角形をたくさん作ろう!」と考えているようではダメです。もうちょっと細かくみていかないといけません。例えば、6角形1個は36点、3角形4個も36点です。大きい多角形を無理してつくるよりは、多くの小さい多角形をつくったほうが良い場合も十分考えられますよね。スコアについて、ほんとによく考えたほうがいいです。

計算時間あたり・頂点数あたりなど、単位を意識した考察ができていない。

6角形1個つくるのに1秒、3角形1個つくるのに0.1秒だったら、断然3角形をつくったほうが、時間あたりの得点が高いです。同じように、頂点数あたりの得点なんかも考慮するべきでした。今回の自分のアルゴリズムでは、計算時間あたりの得点について全く考慮していません。単位を統一して考えるのは、アルゴリズム以前の重要な問題です。これがちゃんとしてないと、そもそもアルゴリズムの良し悪しの比較ができなくなってしまいます。仕事では、めっちゃ注意しているのですが(T T)

「頂点数Nに依存しにくいアルゴリズム」にする必要はない。

別にNによってアルゴリズムを変えるのは全然構いません。Nに依存しないアルゴリズムは、裏をかえせば「Nが小さいときの有利さを生かせない」アルゴリズムでもあります。(ただ、複数のアルゴリズムを用意するのは、実装の時間はかかるので、1つに統一するメリットもあります。)

実装時間も考えて計画をたてよう。

誰でも思いつくようなケースをほとんど試さなかった。

特に、時間がかからずに実装できるものは、絶対試したほうがいいです。仮に全然結果がでなかったとしても、その後のヒントになる可能性もありますし、条件によっては使えるかもしれません。今回、自分の考えたのは実装時間がかかるため、それが外れ方針なのに気づくのに時間がかかってしまいました。

 |