ABC247 Cの答えは、S1 = [1]を基底にし、n ≥ 2ではSn = Sn-1 + [n] + Sn-1として列を作ることです。入力の制約は1 ≤ N ≤ 16なので、S1から順に作れば、公式の入力形式に沿ってSNを空白区切りで出力できます。
問題の定義、制約、入出力はAtCoder ABC247 Cの問題文で確認できます。
ABC247 Cの数列の定義
ABC247 Cでは、S1 = [1]を基底（再帰を止める最初の定義）にします。S0の定義は問題文にないため、[0]を基底にはしません。
n ≥ 2のときは、ひとつ前の列を左右に置き、その中央へnを入れて、Sn = Sn-1 + [n] + Sn-1を作ります。ここで+はリストをつなぐ操作です。
小さい列を順に追跡する
まずS1を一度決めると、同じ形を左右へ置く操作だけで次の列を作れます。S2では、[1]の左右に2を入れるので[1, 2, 1]になります。さらにS3では、その列を左右に置いて中央へ3を入れるため、[1, 2, 1, 3, 1, 2, 1]です。
| 列 | 作り方 | 長さ |
|---|---|---|
S1 |
[1] |
1 |
S2 |
S1 + [2] + S1 = [1, 2, 1] |
3 |
S3 |
S2 + [3] + S2 = [1, 2, 1, 3, 1, 2, 1] |
7 |
この追跡例では、S2がS3の左と右にそのまま現れ、中央だけが3に変わります。コードでも、この「ひとつ前の列を一度作り、左右へ再利用する」形をそのまま書きます。
公式サンプルで入出力を確認する
入力では整数Nが1つ与えられ、出力では作ったSNを空白区切りで並べます。公式サンプルは次のとおりです。
| N | 公式の出力 | 長さ |
|---|---|---|
1 |
1 |
1 |
2 |
1 2 1 |
3 |
4 |
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 |
15 |
N=4では、S3を左へ置き、4を中央へ入れ、同じS3を右へ置きます。したがって、表の出力は追跡例の規則と一致します。
基底を取り違えないための確認
S0 = [0]から始めると、N=1で[0, 1, 0]となり、公式の出力[1]と一致しません。N=0も公式の制約に含まれないため、実装の停止条件はn == 1にします。
再帰をそのままPythonに写す
関数build(n)は、ひとつ小さい列を先に作り、それを左右へ再利用します。
def build(n):
if n == 1:
return [1]
previous = build(n - 1)
return previous + [n] + previous
N = int(input())
print(*build(N))if n == 1の行は、公式のS1 = [1]をそのまま表しています。
previous = build(n - 1)では、ひとつ小さい列を一度だけ作ります。続くprevious + [n] + previousは、同じpreviousを左と右へ使い、中央のnと連結する処理です。
int(input())で入力Nを整数として読み、print(*build(N))で列の要素を空白区切りにして出力します。リストの結合はPython公式ドキュメントのシーケンス演算、入力と出力の呼び出しはPython公式ドキュメントの組み込み関数に対応します。
再帰コードが正しい理由
このコードの返り値が定義どおりになることは、nの小さい値から順に確認できます。
- 基底：
n=1では[1]を返すため、問題のS1と一致します。 - 帰納段階：
n-1で正しいSn-1が返ると仮定すると、コードはそれを左右に置き、中央へnを加えます。返り値はSn-1 + [n] + Sn-1となり、問題が定めるSnと一致します。
基底と帰納段階がつながるので、1 ≤ n ≤ Nの各呼び出しは正しい列を返します。
列の長さは2N - 1になる
列Snの要素数をLnとします。基底ではL1 = 1です。n ≥ 2なら、長さLn-1の列を2つと中央の1要素を連結するので、Ln = 2Ln-1 + 1になります。
L1 = 21 - 1と一致し、Ln-1 = 2n-1 - 1とすると、Ln = 2(2n-1 - 1) + 1 = 2n - 1です。
したがって、求める列SNの長さは2N - 1です。N=1、N=2、N=4の長さは、それぞれ1、3、15になります。公式の最大値N=16では、列の要素数は216 - 1 = 65535です。
このコードの計算量
previous = build(n - 1)で子の再帰呼び出しを各nにつき一度だけ行います。長さLn = 2n - 1なので、段nで行うリスト結合の大きさはO(2n)です。
- 時間計算量：
T(1) = O(1)、T(n) = T(n-1) + O(2n)よりO(2N) - リスト保持：最終列と構築中の列を合わせて
O(2N) - 再帰の深さ：
O(N)
公式解説には、式の中でSn-1を2回呼ぶ別実装も示されています。その実装は同じ子の列を2回計算するためO(N · 2N)ですが、ここで使ったコードは一度作ったpreviousを左右へ再利用するため、計算量はO(2N)です。
実装を確認するときは、N=1、N=2、N=4を入力し、公式サンプルと出力および長さを照合します。N=3は追跡表から自分で書き出すと、前の列を左右へ置く再帰の形を確認できます。
