解いてみた。「Aランク：山折り谷折り」

問題

「Aランク：山折り谷折り」

コード

Javaで解いてみました。

import java.util.*;

public class Main {
    
    public static final boolean TANI = false;
    public static final boolean YAMA = true;
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int nN = sc.nextInt();

        // 初期設定
        int nSize = 0;        
        boolean[] abFolds = new boolean[(int)(Math.pow(2, nN))];

        // 谷折りをi 回開く
        for (int i = 1; i <= nN; i++) {
            if (i == 1) {
                abFolds[1] = TANI;
                nSize = 1;
            } else {
                int nOrgSize = nSize;
                nSize = nSize * 2 + 1;

                // 開いた側の折り目（元の折り目の逆の折り目になる）
                for (int j = 1; j <= nOrgSize; j++) {
                    abFolds[nSize+1 - j] = !abFolds[j];
                }
                // 中心の折り目（谷折り）
                abFolds[nOrgSize+1] = TANI;
            }
        }
        
        // 結果出力
        for (int i = 1; i <= nSize; i++) {
            if (abFolds[i]) {
                System.out.print("1");
            } else {
                System.out.print("0");
            }
        }
        System.out.println("");
    }
}

解説

標準入力からの数値の読み取り

Scanner インスタンスを作り、nextInt()メソッドで数値を取得しています。

初期設定

• 折り目の本数を０にする
• 折り目を格納する abFolds[] 配列を作成する。この時、サイズは $2^N-1 $であるが、0番目を使用しないため、+1 している

i 回開く

1　回目

• 中心の折り目（谷折り）をつける
• 折り目の本数を 1 にする

k回目（１以外）

折り目は、以下の通りになる。

• 左から nOrgSize(本) の折り目は、そのまま維持される
• 開いた側の 1, .., nOrgSize(番目) の折り目は、開いた折り目（谷折り）を中心として、開いた側の外側から 2nOrgSize+1, 2nOrgSize, .., nOrgSize+1 番目の折り目として、逆（山折りなら谷折り、谷折りなら山折り）にコピーされる
• 開いた折り目 nOrgSize+1 番目の折り目は谷折りになる
• 折り目の本数を、2nOrgSize + 1 にする

結果出力

abFolds[] について、以下をprint()メソッドで表示する。

• true:山折り → 1
• false:谷折り → 0

最後に改行（println()メソッド）を表示する。