paiza問題ランクA「山折り谷折り」を解いてみた & 解説

paiza×Qiitaコラボキャンペーンから、今回はランクA問題「山折り谷折り」に挑戦してみました。

問題概要

どんなブームなんですかね。

ひたすら紙を折り続けるということがマイブームとなっているあなたは、今日もひたすら紙を折り続けています。それも、折り紙のような凝った折り方ではなく、紙の右辺が上から左辺に重なるような二つ折りを、ただひたすら繰り返すだけです。

折る回数 N が与えられるので、紙を折って広げたあとの山折り谷折りの折り目を計算するプログラムを作成してください。

期待する出力は以下の通りです。

山折りの折り目を "1"、谷折りの折り目を "0" として、答えとなる折り目を左から順に "0" と "1" からなる文字列として一行に出力してください。

問題を解くポイント

この問題にはきっと規則性があるはずで、それがわかれば簡単に解けそうな気がしますね。
その通りで、規則性があります。

規則性を見つける

まずいくらか折ってみましょう。4回折った時の文字列を作ります。

N回	文字列
1	0
2	001
3	0010011
4	001001100011011

この結果から以下のことがわかります。

前の文字列結果に対し、逆の文字列かつ反転させた文字列が末尾にくっついていること ex)001->011
前文字列と末尾文字列の間は必ず0がくっついていること

例として、3回折った場合をみてみましょう。

1. 前文字列結果は001
2. 逆の文字列は110
3. 反転させた文字列は011
4. 前文字列と連結させると001011
5. それぞれの文字列の間には0がくっつくので0010011

私の解

先ほどの規則性にのっとり、コードを書きました。

// 紙を折る回数
const foldPaperCount = lines[0];
// 1回目は必ず0
let foldResultStr = '0';
// 2回目からN回分繰り返す
for (let i = 2; i <= foldPaperCount; i++) {
    // 逆文字列にして反転し連結させる
    const suffixStr = [...foldResultStr]
        .map(str => str === '0' ? '1' : '0')
        .reverse()
        .join('');
    // 0を連結させて結果を格納する
    foldResultStr = `${foldResultStr}0${suffixStr}`;
}
console.log(foldResultStr);

さいごに

いかがでしたか？
規則性がわかれば簡単な問題でしたね。