ベスパリブ

ベスパもってないです。バイク買いました。

ABC140: C問題の解説 (Python3)

問題:AtCoder Beginner Contest 140: C - Maximal Value

公式解説PDF:https://img.atcoder.jp/abc140/editorial.pdf

公式解説動画:https://youtu.be/VSeggcnxwrc?t=2461

解説

ABC140のC問題の解説です。貪欲法(?)問題です。

数列  A_i を リストAsに、数列  B_i を リストBsに置き換えて考えます。AsとBsは0-originです。

Bs[i] >= max(As[i], As[i+1]) の条件を満たすようにAs[i+1] の値を貪欲的に埋めていく問題です。

最初に初期値のAs[0]とAs[1]を決めます。これはBs[0]とBs[1]の大きさを比較すれば一意に定まります。

たとえば、Bs[0]=10, Bs[1]=20のとき、Bs[i] >= max(As[i], As[i+1]) より、As[0] =10, As[1] = 10 と求まります。

    # 初期値を決める
    As = [0] * N
    if Bs[0] <= Bs[1]:
        # As:  ?   ?   →   As: 10  10
        # Bs: 10  20   →   Bs: 10  20
        As[0] = As[1] = Bs[0]
    else:
        # As:  ?   ?   →   As: 20  10
        # Bs: 20  10   →   Bs: 20  10
        As[0], As[1] = Bs[0], Bs[1]

あとは Bs[i] >= max(As[i], As[i+1]) の条件を満たすようにAs[i+1] の値を貪欲的に埋めていけばOKです。

数列の最後のAs[N-1] だけ例外で、これは必ずBs[N-2]になります。

    # 貪欲法
    for i in range(1, N-2):
        if Bs[i] > Bs[i+1]:
            # As:   ■    ?  →  As:   ■    0
            # Bs: 153    0  →  Bs: 153    0
            As[i+1] = Bs[i+1]
        else:
            # As:   ■    ?  →  As:   ■  153
            # Bs: 153  160  →  Bs: 153  160
            As[i+1] = Bs[i]
    As[N-1] = Bs[N-2]

コーナーケース

  • N == 2 の場合、答えは必ず Bs[0]*2 になる

実装

# -*- coding:utf-8 -*-
import sys

"""
Bs[i] >= max(As[i], As[i+1]) を満たす条件で、

sum(As)の最大値を求める問題
"""

def solve():
    N = int(sys.stdin.readline())
    Bs = list(map(int, sys.stdin.readline().split()))

    if N == 2:
        print(Bs[0]*2)
        return

    # 初期値を決める
    As = [0] * N
    if Bs[0] <= Bs[1]:
        # As:  ?   ?   →   As: 10  10
        # Bs: 10  20   →   Bs: 10  20
        As[0] = As[1] = Bs[0]
    else:
        # As:  ?   ?   →   As: 20  10
        # Bs: 20  10   →   Bs: 20  10
        As[0], As[1] = Bs[0], Bs[1]

    # 貪欲法
    for i in range(1, N-2):
        if Bs[i] > Bs[i+1]:
            # As:   ■    ?  →  As:   ■    0
            # Bs: 153    0  →  Bs: 153    0
            As[i+1] = Bs[i+1]
        else:
            # As:   ■    ?  →  As:   ■  153
            # Bs: 153  160  →  Bs: 153  160
            As[i+1] = Bs[i]
    As[N-1] = Bs[N-2]

    print(sum(As))


if __name__ == "__main__":
    solve()

計算量は、 O(N)

リスト As を作っていく方式だが、最大値のみを求めればよいので、別にリストAsはつくらなくても良い。その場合は計算時間と使用メモリを少し小さくできる。