AtCoderのARCのA問題が終わり、ちょくちょくABCのC問題を解いていたのですが、TLE(Time Limit Error)が頻発し、これは駄目だということでプログラミングコンテストチャレンジブック、通称・蟻本を購入しました。
競プロerのバイブルなんだとか。
ということで、今回は蟻本にも載っている全探索アルゴリズムの一つ、「深さ優先探索」を使って問題を解いてみようと思います。言語はJavaです。
というのも、蟻本で出てくるソースコードの言語はg++用に書かれたC++なので(とても読みやすいですが)、Javaでは少し違うので、Javaでの記述例を出してみることにしました(とはいえ、問題の核となるアルゴリズム自体は同じですが)。
そもそも「深さ優先探索」ってなに、という方はまずはWikipediaをどうぞ↓
補足すると、深さ優先探索の性質上、再帰関数で簡単に記述できるのがポイントみたいです。
さて、実際に問題を解いてみましょう。
部分和問題
整数a_1、a_2、…、a_nが与えられます。その中からいくつか選び、、その和をちょうどkにすることができるかを判定しなさい。
[深さ優先探索]部分和問題 ※ネストがおかしいですがご了承ください。
綺麗なコードなのかどうかは不安ですが、Javaで記述すると以上のようになりました。
できるだけ蟻本に載っているコードに忠実に書いたつもりです。
何か改善点などがあれば、コメントやTwitterで教えてくださると幸いです。
部分和問題は蟻本にしか掲載されていないので、その他、深さ優先探索を使って解ける問題を掲載しておきます(リンクはとあるブログから拝借しました)。
AOJ 0118 Property Distribution
最後に…
これはまだ序の口、初級編の始めなので、これからガンガン蟻本を進めていきたいと思います(進むといいな)
それでは。