5
3

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

・ 問題

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

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

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

制約

$1 \leq N \leq 20$

・ 考察

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

  • $0$回 → $1$回

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

  • $1$回 → $2$回

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

origami.png

  • $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で見る

5
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
3