問題
あるパズルの本に、図形シリーズの最初の 3 つが載っていて、続きを考えるよう求められています。
n = 1 n = 2 n = 3
A BBB CCCCC
BAB CBBBC
BBB CBABC
CBBBC
CCCCC先を読む前によく観察して、規則を言葉にしてみましょう。正確な規則は次のとおりです。n 番目の図形は 2n − 1 行の正方形で、各行は空白なしの 2n − 1 文字です。行と列に 0 から番号を付け、中心を位置 n − 1 とします。r 行 c 列のマスには、アルファベットで A から d 文字後ろの文字が入ります。ここで d = max(|r − (n − 1)|, |c − (n − 1)|) は、そのマスが中心から何周外側にあるかを表します。つまり、中心が A、そのまわりの 1 周が B、いちばん外側の縁が n 番目の文字になります。
decode_the_pattern(n) を実装してください。
入力
n: 作る図形の番号(最大 26 なので、文字が Z を超えることはありません)。
出力
2n − 1 行を上から順に返してください。n が 0 のときは空のリストを返してください。
制約
0 ≤ n ≤ 26
例
入力:
n = 2
期待される出力:
expected = ["BBB", "BAB", "BBB"]
入力:
long long n = 2;
期待される出力:
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
入力:
long n = 2;
期待される出力:
string[] expected = new string[] {"BBB", "BAB", "BBB"};
解説
中心 (1, 1) だけが 0 周で、それ以外のマスはすべて 1 周外側です:["BBB", "BAB", "BBB"]。
入力:
n = 4
期待される出力:
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
入力:
long long n = 4;
期待される出力:
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
入力:
long n = 4;
期待される出力:
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
解説
縁のマスは 3 周外側(D)で、3 行目が真ん中の行です:["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
各例の正方形の中心に印を付け、そこから離れるにつれて文字がどう変わるかを見てみましょう。
ヒント 2
同じ周にあるマスは同じ文字です。何周目かは、中心からの行方向と列方向の距離のうち大きい方で決まります。
ヒント 3
任意の n で作る前に、n = 3 の例で自分の規則を確かめましょう。
目安の計算量
時間 O(n^2)、追加メモリ O(n^2)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。