【Python3】山折り谷折り (paizaランク A 相当)をやってみた

# 山折り谷折り A
# utf-8

'''
N 回折ったときの折り目は N-1 回折ったときの折り目から簡単に求めることができます。
1 回折ったときの折り目は "0"、2 回折ったときの折り目は "0" + "0" + "1" = "001"、3 回折ったときの折り目は "001" + "0" + "011" = "0010011" です。
N-1 回折ったときの折り目の文字列を S、S を逆順にし、0 と 1 を反転させた文字列を S' とすると、N 回折ったときの折り目の文字列は S + "0" + S' となります。

N 回折ったときの折り目の数 2N-1 個の要素を持つ配列を用意します。
方針の通りに 1 回折ったときの折り目から順に N 回折ったときの折り目までを順に求めます。
'''

# 入力値を取得
N = int(input())

# 折り目の数 2^N - 1 を計算して配列のサイズを決定
size = 2 ** N - 1

# 折り目を表す配列を初期化。初期値はすべて False (谷折り)
paper = [False] * size

# カウント変数の初期化
count = 0

# ループで折り目を生成
while True:
    # 現在の折り目の状態を逆順にして反転させた折り目を生成
    for i in range(count):
        paper[count * 2 - i] = not paper[i]

    # 真ん中の折り目は常に谷折り (False)
    paper[count] = False

    # カウントを更新。次の折り目の位置を決定
    count = count * 2 + 1

    # N をデクリメント。N が 0 になったら終了
    N -= 1
    if N == 0:
        break

# 最終的な折り目を出力。谷折りは 0、山折りは 1 として出力
for i in range(0, size):
    print(1 if paper[i] else 0, end="")

# 最後に改行を出力
print()

解説

1. 入力値の取得

   N = int(input())
   

   • 入力から紙を折る回数 N を取得します。

2. 配列のサイズを計算して初期化

   size = 2 ** N - 1
   paper = [False] * size
   

   • 折り目の数は 2^N - 1 です。
   • これを元に paper 配列を初期化し、すべての値を False（谷折り）に設定します。

3. 折り目の生成ループ

   count = 0
   while True:
       for i in range(count):
           paper[count * 2 - i] = not paper[i]
       paper[count] = False
       count = count * 2 + 1
       N -= 1
       if N == 0:
           break
   

   • count を初期化し、折り目を生成するループに入ります。
   • 現在の折り目の状態を逆順にして反転させた折り目を生成し、適切な位置に配置します。
   • 真ん中の折り目は常に谷折り（False）です。
   • count を更新して次の折り目の位置を決定します。
   • N をデクリメントし、N が 0 になったらループを終了します。

4. 最終結果の出力

   for i in range(0, size):
       print(1 if paper[i] else 0, end="")
   print()
   

   • paper 配列の内容を出力します。False は谷折り（0）、True は山折り（1）として出力します。
   • 最後に改行を追加します。

このプログラムは、指定された回数 N だけ紙を折り、その折り目の状態を正確に出力することができます。