ABC 029 C Brute-Force-Attack

atcoder.jp

問題概要

'a','b','c'の３種類の文字のみを含むN文字の単語を辞書順で出力せよ

考察(TLE)

abcの3つの文字なので3進数を使って0ならa,1ならb,2ならcを出力すればいいのかと思い実装したらコードが長くなりTLEしてしまった

解答

この問題は再帰関数を用いて出力します.
普通に比較していくとTLEを起こしてしまいます(実際にやってしまいました). N = 3くらいまで実際に書いて実験してみると再帰関数ということに気づくと思います. N = 1 と N= 2の時についての出力をするとこうなります. N = 2 の方をみると一番左の文字を除けば , N = 1の a , b ,c を繰り返していることがわかります. N = 3までやるとよくわかります. N = 3 の時の出力です.一番左の文字を無視してみると N = 2の時の出力が繰り返されていることがわかります.このような時に再帰関数を用いてコードを書くことができます.

コード

• ACしました

// pos : 残りの文字数
// s : 文字列(徐々に追加していく)
    public static void Print(int pos, String s) {
        if (pos == 1) {
            System.out.println(s + "a");
            System.out.println(s + "b");
            System.out.println(s + "c");
        } else {
            Print(pos - 1, s + "a");
            Print(pos - 1, s + "b");
            Print(pos - 1, s + "c");
        }
    }

使うときは Print( N , "" );で空列を最初に指定します.再帰関数の中身では後ろに文字をどんどん追加していきます.N == 1の時に出力するようにすれば望み通りの挙動が起こります.

参考

• 公式解説