AtCoder Beginner Contest 189 C問題

AtCoder Python

前書き

atcoder.jp

C問題

難易度：茶色
時間：タイムオーバー

解けませんでした。何度かコードを書いてトライしましたが、いずれもTLEとなりました。

最初に書いたコード

短いように見えてやってることは3重ループ。
(10**4)*(10**4)の全探索（O(n**2)）な上、最小値min（O(N)）を挟んでいるので、3重ループ。
そりゃTLE吐くわ。

import itertools
N = int(input())
A = list(map(int, input().split()))
 
Lis = [min(A[i[0]:i[1]+1])*((i[1]+1)-i[0]) for i in list(itertools.combinations_with_replacement(range(0,N), 2))]
print(max(Lis))

2番目に書いたコード

これも3重ループ。
でも区間最小値を求めて、区間長と区間最小値の積の最大を求めようとしているので、筋は合っている。
ただアルゴリズムの問題。

import itertools
import numpy as np
 
N = int(input())
A = np.array(list(map(int, input().split())))
 
ans = 0
for i in range(0,N):
  for j in range(i,N):
    ans = max(ans, min(A[i:j+1]*(j+1-i)))
print(ans)

正解

区間最小値はまずLを固定します。
その後Rを探索しますが、この時点でmax()やmin()は二択をとるようにします（計算量を節約するために）。

しかもこれをpythonで実行するとTLE。。。
Pypyで実行するとACになります。なんやそれ・・・

unidayo.com


これからはPythonで厳しいと感じたら、Pypyで実行するようにしましょう。

import itertools
 
N = int(input())
A = list(map(int, input().split()))
 
ans = 0
for l in range(0,N):
  _min = 10**6
  for r in range(l,N):
    _min = min(_min, A[r])
    ans = max(ans, _min*(r+1-l))
print(ans)