bit操作と深さ優先探索の全列挙を比較する
問題
http://abc045.contest.atcoder.jp/tasks/arc061_a
解き方
全列挙できるか
全ての数字と数字の間に対して、「+」を入れる場合と入れない場合で全列挙。文字列の長さがNの場合、「+」を入れることができる箇所は全部で(N - 1)個。それぞれの箇所に「+」を入れるか否かの2通りを行うので計算量はO(2N - 1)。 今回のNの最大値は10であり、210は1024なので全列挙は可能。
深さ優先探索を用いた全列挙
まずは深さ優先探索を用いた全列挙を考える。
再帰関数を作るにあたり以下のポイントを抑える。
- 求めたいもの: 出来上がった計算式の和
- 深さのパラメータ: 与えられる文字列のindex (indexが0であれば文字列の先頭の文字)
- 深さが変わる度に変化するもの: どの文字の間に「+」を入れるか (booleanの配列で「+」を挿入する箇所を管理)
以上から関数を作ると以下のようになる。
面倒なのは、どこに「+」を挿入しているかを表現するための配列contained
を深さの階層ごとに状態を保たなければならないので、再帰する度に配列を深いコピーをしなければならない。
bit操作を用いた全列挙
次にbit操作を用いた全列挙を考える。
「+」を挿入するか否かを0と1で表現し全列挙を行う。具体的に考える。S = 125
の時、「+」を挿入できる場所は1と2の間と2と5の間の2箇所。よって以下のように2桁の2進数で表現する。
このようなbit操作による全列挙するにあたり、以下の2つのポイントを抑える。
- 全てのパターンを覆うように2進数を列挙
- それぞれの桁を見てフラグのチェック
以上のポイントを抑えて関数を作ると以下のようになる。
後は、フラグがある時と無い時で処理内容を変えてあげれば良い。bit操作の良い所は全列挙が簡単な所である。しかしbit操作に馴染みがない人にとって可読性は悪い。
ソースコード
bit操作