bit操作と深さ優先探索の全列挙を比較する

問題

http://abc045.contest.atcoder.jp/tasks/arc061_a

解き方

全列挙できるか

全ての数字と数字の間に対して、「＋」を入れる場合と入れない場合で全列挙。文字列の長さがNの場合、「+」を入れることができる箇所は全部で(N - 1)個。それぞれの箇所に「+」を入れるか否かの２通りを行うので計算量はO(2^{N - 1})。 今回のNの最大値は10であり、2¹⁰は1024なので全列挙は可能。

深さ優先探索を用いた全列挙

まずは深さ優先探索を用いた全列挙を考える。

再帰関数を作るにあたり以下のポイントを抑える。

• 求めたいもの: 出来上がった計算式の和
• 深さのパラメータ: 与えられる文字列のindex (indexが0であれば文字列の先頭の文字)
• 深さが変わる度に変化するもの: どの文字の間に「+」を入れるか (booleanの配列で「+」を挿入する箇所を管理)

以上から関数を作ると以下のようになる。

面倒なのは、どこに「＋」を挿入しているかを表現するための配列containedを深さの階層ごとに状態を保たなければならないので、再帰する度に配列を深いコピーをしなければならない。

bit操作を用いた全列挙

次にbit操作を用いた全列挙を考える。

「＋」を挿入するか否かを0と1で表現し全列挙を行う。具体的に考える。S = 125の時、「+」を挿入できる場所は1と2の間と2と5の間の２箇所。よって以下のように２桁の２進数で表現する。

このようなbit操作による全列挙するにあたり、以下の２つのポイントを抑える。

1. 全てのパターンを覆うように２進数を列挙
2. それぞれの桁を見てフラグのチェック

以上のポイントを抑えて関数を作ると以下のようになる。

後は、フラグがある時と無い時で処理内容を変えてあげれば良い。bit操作の良い所は全列挙が簡単な所である。しかしbit操作に馴染みがない人にとって可読性は悪い。

ソースコード

深さ優先探索

bit操作