iwamotのブログ : アルゴリズム

深さ優先探索に続き、幅優先探索を勉強している。今回も「頻出典型アルゴリズムの演習問題としてよさげなやつ」に載っている問題から、2題解いてみた。

それほど悩まずに解けた。無限ループを避ける工夫をしている。

こちらもそれほど悩まなかった。スタートとゴールを変えてN回探索している。

という感じで、このくらいの問題は解けるようになってきた。残りの問題はまた今度。

これは難しかった。単純に探索するだけでは TLE (Time Limit Exceeded) してしまう。他の回答を参考に工夫したら、格段に早くなった。発想が大事なのだと改めて感じた。

それだけでなく、右上と左下のカードが入れ替えられるバグがあることに気づかず、WA (Wrong Answer) も出してしまった。簡単な問題が解けたせいで慢心していたのかもしれない。

単純な幅優先探索では解けないのではないかと、だいぶ悩んでしまった。結局、特に工夫のないコードを Submit してみたら、あっさり通った。案ずるより産むが易しだ。この辺の、計算量の感覚がまだつかめない。

『プログラミングコンテストチャレンジブック [第2版]』において、「すべての基本」とされているのが「全探索」である。全探索アルゴリズムの典型は「深さ優先探索」と「幅優先探索」であり、まずは前者を理解したいと思った。

そのためには、本を読むだけではなく、多くの問題を解く必要があるだろう。「頻出典型アルゴリズムの演習問題としてよさげなやつ」には、深さ優先探索で解けそうな問題が6問挙げられている。

1問目の「Ball」は、さほど悩まずに解けた。

2問目の「Sum of Integers」には、けっこう時間がかかってしまった。再帰関数の終了条件が、Ballとくらべて複雑なのが原因だろう。独力の解答でも間違いではなかったのだが、他の解答例を参考に直してみた。こちらのほうが終了条件がわかりやすい気がする。

実はこれらの2問、以前AIZU ONLINE JUGDEにトライしていたときには解けなかったものだった。できなかったことができるようになるのは楽しい。3問目以降にも挑戦しよう。

3問目の「The Number of Island」、4問目の「Block」、6問目の「Property Distribution」も解けた。

3問目は前掲書籍の例題とほぼ同じ内容。4問目も似た内容だが、RubyのArrayの使い方を理解できておらずハマってしまった。

6問目も似ているが、再帰だとスタックオーバーフローになってしまった。スタックを使う方式で書き換えて、なんとか解けた。

5問目の「Sergeant Rian」は難しそうなのでまた今度。

iwamotのブログ