ABC 134 C "Exception Handling"

内容

• ABC 134 C(300点) "Exception Handling"を解きました。

問題

https://atcoder.jp/contests/abc134/tasks/abc134_c

考えたこと

• 自分より左の区間のmaxと、自分より右の区間のmaxを比べて大きい方を出せばいい。

ポイント

• 左から見ていく場合の最大値と、右から見ていく場合の最大値の二つを用意する。

実装

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

right = [0] #自分より左の最大値を管理
left = [0] # 自分より右の最大値を管理

for a in A:
    left.append(max(a, left[-1]))

for a in reversed(A):
    right.append(max(a, right[-1]))

#　ans=max(自分より左の最大値、自分より右の最大値)
for i in range(N):
    print(max(left[i], right[N-i-1]))

提出2

• segment treeのライブラリを描いたばっかりだったので、seg木でもやってみた。

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class SegmentTree():
  
    def __init__(self, _n, func, init=float('inf')):
        self.n = 2**(_n-1).bit_length()
        self.inf = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        self.data[k+self.n-1] = v

    def build(self):
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        L = l+self.n
        R = r+self.n
        ret = self.inf
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N = int(input())
A = [int(input()) for _ in range(N)]

Seg = SegmentTree(N, max, init=0)
# seg木に値をset
for i, a in enumerate(A):
    Seg.set(i, a)
# seg木を一斉更新
Seg.build()

#　答えを求めていく
for i in range(N):
    print(max(Seg.query(0, i), Seg.query(i+1, N)))

終わりに

• 回答に乗ってた、二番目に大きい数を計算する方法、頭良さそうと思った。