【競技プログラミング】AtCoder Beginner Contest 336_D問題

問題

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

数列Aの各要素に対して、その位置から左側と右側それぞれで作れるピラミッド数列の最大サイズを求め、その中で最も大きな値を答えとする。

解法手順

1. 入力された数列Aを受け取る。

2. 左側からのピラミッド数列の最大サイズを求める：

   • 数列bを用意し、左から順に走査する。
   • 各位置iにおいて、min(Ai, i+1)の値をbiに格納する。
   • これにより、各位置から左側で作れるピラミッド数列の最大サイズが得られる。

3. 右側からのピラミッド数列の最大サイズを求める：

   • 数列cを用意し、右から順に走査する。
   • 各位置iにおいて、min(Ai, N-i)の値をciに格納する。
   • これにより、各位置から右側で作れるピラミッド数列の最大サイズが得られる。

4. 各位置iにおいて、min(bi, ci)を計算する：

   • これは、位置iを中心とするピラミッド数列の最大サイズを表す。

5. 手順4で得られた値の最大値を求める：

   • この最大値が、問題の答えとなる。

6. 最大値を出力する。

ACコード

ac.py

# 1. 入力された数列Aを受け取る
n = int(input())  # 数列の長さを入力
a = list(map(int, input().split()))  # 数列Aを入力

# 2. 左側からのピラミッド数列の最大サイズを求める
b = []  # 左側のピラミッド数列の最大サイズを格納するリスト
cnt = 1  # カウンター（位置）
for x in a:
    cnt = min(cnt, x)  # min(Ai, i+1)の値を計算
    b.append(cnt)  # 計算結果をbに追加
    cnt += 1  # カウンターを増やす

# 3. 右側からのピラミッド数列の最大サイズを求める
c = []  # 右側のピラミッド数列の最大サイズを格納するリスト
cnt = 1  # カウンター（位置）
for x in a[::-1]:  # 数列Aを逆順に走査
    cnt = min(cnt, x)  # min(Ai, N-i)の値を計算
    c.append(cnt)  # 計算結果をcに追加
    cnt += 1  # カウンターを増やす

# 4. 各位置iにおいて、min(bi, ci)を計算し、5. 最大値を求める
ans = 1  # 最大のピラミッド数列サイズを格納する変数
for x, y in zip(b, c[::-1]):  # bとcを同時に走査（cは逆順）
    t = min(x, y)  # 各位置でのmin(bi, ci)を計算
    ans = max(t, ans)  # 最大値を更新

# 6. 最大値を出力する
print(ans)  # 結果を出力

ピラミッド復元コード

ac.py

# 1. 入力された数列Aを受け取る
n = int(input())  # 数列の長さを入力
a = list(map(int, input().split()))  # 数列Aを入力

# 2. 左側からのピラミッド数列の最大サイズを求める
b = []  # 左側のピラミッド数列の最大サイズを格納するリスト
cnt = 1  # カウンター（位置）
for x in a:
    cnt = min(cnt, x)  # min(Ai, i+1)の値を計算
    b.append(cnt)  # 計算結果をbに追加
    cnt += 1  # カウンターを増やす

# 3. 右側からのピラミッド数列の最大サイズを求める
c = []  # 右側のピラミッド数列の最大サイズを格納するリスト
cnt = 1  # カウンター（位置）
for x in a[::-1]:  # 数列Aを逆順に走査
    cnt = min(cnt, x)  # min(Ai, N-i)の値を計算
    c.append(cnt)  # 計算結果をcに追加
    cnt += 1  # カウンターを増やす
c = c[::-1]  # cを元の順序に戻す

# 4. 各位置iにおいて、min(bi, ci)を計算し、5. 最大値とその位置を求める
ans = 1  # 最大のピラミッド数列サイズを格納する変数
max_pos = 0  # 最大のピラミッド数列の中心位置
for i, (x, y) in enumerate(zip(b, c)):  # bとcを同時に走査
    t = min(x, y)  # 各位置でのmin(bi, ci)を計算
    if t > ans:
        ans = t  # 最大値を更新
        max_pos = i  # 最大値の位置を記録

# 6. 最大のピラミッド数列を生成
pyramid = []
for i in range(1, ans + 1):
    pyramid.append(i)
for i in range(ans - 1, 0, -1):
    pyramid.append(i)

# 7. 結果を出力
print(f"最大のピラミッド数列のサイズ: {ans}")
print(f"最大のピラミッド数列の中心位置: {max_pos + 1}")
print(f"最大のピラミッド数列: {' '.join(map(str, pyramid))}")