ABC 029 C - Brute-force Attack

atcoder.jp

Brute-force Attack 総当り攻撃が題材の問題。

初手の方針

a,b,cの組み合わせの文字列を全て列挙するということで先日bit全探索を覚えたこともあって真っ先にそれを使えないかなと考えた。 a,bの2種類の文字列であれば0=a,1=bとして全列挙可能だが文字列が三種類だったのでどうしようかなと考えて、 全列挙した2つのvectorを重ね合わせて強引に全列挙する感じになった。 例えばn=2で各vectorの要素がそれぞれ(1,0),(1,1)だった場合に(2,1)を生成する的な具合に1&1->2,1&0->1,0&0->0と解釈する。

Submission #9302079 - AtCoder Beginner Contest 029

ただ下に書いてあるスマートなやり方と比べると相当いけてない、 v3の要素をソートしてユニークにするという操作が追加で必要になるし何より文字の種類が増えたときの拡張性がなさすぎる。

計算量的には v1,v2の生成にn2ⁿ sortにnlogn uniqueにlast-first-1 結構無駄が多い。。。

正答

解説では2通りの方法が提示されていた

1. n=1~8まで場合分けしてfor loopを回す -> 計算量は3ⁿ

2. 再帰的関数呼び出しする -> 本題はこちら

自分的に気づきとしては

• charのincrement for(char c = 'a'; c <= 'c'; c++) の部分。 charをincrementできるの知らなかったのでこの書き方が新しかった。

ただ可読性的にはこっちでいいかなとも思った。

char abc[] = "abc";
for(int i=0; i<3; i++) {
  abc[i];
}

• 再帰実装

フィボナッチ数列を再帰的に求めるのは大学のときに説明を受けた記憶はあるが競プロで使ってるのは初めてみた。 解説にもあるようにn=2の結果からn=3の場合を列挙できるというのが肝でここに気づくと再帰的な実装（あるいは帰納的）も思い浮かぶかもしれない。競技プログラミングにおいて再帰的,帰納的というのは重要な考え方でその目線で問題を見れると今後捗りそうだと思った。 ちなみにn=2の場合コードを追いかけるとこうなる。

f(1, 'a')
f(0, 'aa')
f(0, 'ab')
f(0, 'ac')

f(1, 'b')
f(0, 'ba')
f(0, 'bb')
f(0, 'bc')

f(1, 'c')
f(0, 'ca')
f(0, 'cb')
f(0, 'cc')

Submission #9304630 - AtCoder Beginner Contest 029