TopCoder

561 ：デフォルトの名無しさん：2008/08/16(土) 18:44:41

>>558
SRM 413 Div2 Medium はO(n)で解ける。
再帰とキャッシュがわかっててもたぶん解けないと思うよ。
アルゴリズムを考えるのにひらめきを用いるのは第二段階。

>>557
Div2に限って言えば、Easyは問題をちゃんと理解できて、”整理”ができれば十分解ける。
ただ漠然と解き方を考えるだけじゃ解けない。
何事も全ての場合を考慮した方法を考えるのは難しい。なので問題の解き方を考えるときは、
「この問題ではこういう状況にしかならない。この状況だけ考えれば大丈夫なはず」
という思考が大切。これはどんなに簡単な問題もどんなに難しい問題も同じ。

＞ソートとかの基本的なアルゴリズムをしっかり勉強すれば
これは正直どうでもいい。たしかにソートなどの基本的なアルゴリズムが理解できるってことは
それなりの力がついてるってことだから力にはなると思うけど、それは本質じゃない。

こういう問題を解く上で必要なのは、オーダーという概念をちゃんと理解すること。
特にとぷこだではそれが顕著。
1. まず問題をちゃんと理解する。
2. 色んな事を整理する。
3. 次にこの問題を解く上で、最低限必要なオーダーというのを考える。
4. 次にそのオーダーに収まりそうなアルゴリズムを考えていく。

3.いれるだけで随分変わってくる。それができないと>>558みたいにひらめきが必要だという結論に至ってしまう。
ひらめきが重要なときもないわけではないが、3.ができれば経験で補うこともできる。
というか上位陣でひらめきだけで解いてるのはほぼ皆無だと思うよ。ひらめきに頼ってたら黄色以上にはなれない。
あと2.は特に重要。ここでしっかり整理できてないと絶対に問題が解けない。
これも>>558を引用させてもらうけど、O(n)で解ける問題なのにO(n^2)が最善だと結論付けてる。
これは問題がちゃんと整理できていない証拠。
今回のこの問題は値の上限が緩くて（Div1 Easy Div2 Medium だから)O(n^2)でも十分間に合うから大丈夫だけど、
もしこれが値の上限がシビアだったらO(n^2)だとこの問題は解けない。
ちゃんと問題を整理できてないとO(n)にはたどり着かない。