山折り谷折り (paizaランク A 相当) を考察する

解き方は 幾つもあると思いますが、自分が実際に考察した内容を書きます。

・ 問題

（横長の）紙を、一方方向に$N$回折ったときに、紙に付いた折り目（谷・山）を答える問題。

問題ページから引用した下の図は、$2$回折ったときの『折り目』を示していて、左から『谷折り → 谷折り → 山折り』になっていることが分かります。

山折りを 1、谷折りを 0 として、答えとなる折り目を左から順に 0 と 1 からなる文字列として一行に出力するため、上の例では001が答えになります。

制約

$1 \leq N \leq 20$

・ 考察

実際の紙を、$1$回 → $2$回 → $3$回 と折ってみて、折り目の増え方（増える位置と山・谷）を観察しました。

• $0$回 → $1$回

紙の中央に谷折りができます。これは自明ですね。

• $1$回 → $2$回

中央の折り目の左右に新しい折り目が（左側に谷折りが、右側に山折りが）増えました。

• $2$回 → $3$回

左側の折り目の左右と、右側の折り目の左右に新しい折り目が増えます。
増える折り目は 先ほどと同じで、左側に谷折りが、右側に山折りが増えます。

• $3$回 → $4$回

左から偶数番目の折り目をそのままとすると、
左から奇数番目の折り目の左右に新しい折り目が増えました。
増える折り目は これまでと同じで、左側に谷折りが、右側に山折りです。

$1$回 → $2$回と、$2$回 → $3$回も同じこの規則性で説明できますので、この規則をコードに表すことにします。シンプルなコードで書けると思います。

・ コード

再帰ではなく、素直にループ処理で表現できます。

配列は0-Indexedのため、考察時とは折り目の偶奇が逆になります。
偶数番目の折り目の左右に新しい折り目を増やし、奇数番目の折り目はそのまま引き継ぎます。

計算量は$O(2^{N}N)$だと思いますが、$N$が十分に小さいので、Paizaに提出しても数ミリ秒で処理が終わりました（Swift / Python とも）。

Swift

let N = Int(readLine()!)!
var ans = [0]
for _ in 0 ..< N - 1 {
    var arr = [Int]()
    for m in 0 ..< ans.count {
        if m % 2 == 0 {
            arr.append(0)
            arr.append(ans[m])
            arr.append(1)
        } else {
            arr.append(ans[m])
        }
    }
    ans = arr
}
print(ans.map { String($0) }.joined(separator: ""))

Swift版をPaizaで見る
　

Python

N = int(input())
ans = [0]
for _ in range(N - 1):
    arr = []
    for m in range(len(ans)):
        if m % 2 == 0:
            arr.append(0)
            arr.append(ans[m])
            arr.append(1)
        else:
            arr.append(ans[m])
    ans = arr

print(''.join([str(x) for x in ans]))

Python版をPaizaで見る