AtCoder キーエンスプログラミングコンテスト2021 A - Two Sequences 2【Python解答例】

AtCoder キーエンスプログラミングコンテスト2021のA問題の解答例を記載していきます。
KEYENCE Programming Contest 2021 - AtCoder

A - Two Sequences 2

A - Two Sequences 2

問題文

すぬけ君は長さ N の数列 a,b を持っています。 a,b の i 番目の数はそれぞれ , です。
すぬけ君は a,b を使って長さ N の数列 c を作ることにしました。 1≤n≤N を満たす n について、c の n 番目の数 は 1≤i≤j≤n を満たすような (i,j) について を計算したときの最大値です。より形式的には は=max1≤i≤j≤n で表される数です。
,,…,を求めてください。

制約

・与えられる入力は全て整数
・1≤N≤2×
・1≤ai,bi≤

解答例

n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a_max = A[0]
ans = 0

for i in range(n):
    if i == 0:
        ans = A[0] * B[0]
        print(ans)
    else:
        ans = max(ans,a_max * B[i])
        ans = max(ans,A[i] * B[i])
        print(ans)
        if a_max < A[i]:
            a_max = A[i]

解説

数列AとBから作成できる数列Cの各要素を答える問題です。

数列Cのn番目の数は、n以下を数jとすると数列Bの数と、j以下の数iとして数列Aの数を掛け合わせた数の最大値です。
を1≤i≤j≤nの範囲で全探索するとTLEとなります。
全探索以外の方法でを求めるには次のような場合分けでできます。
・数列Aのn番目の数A[n]がn番目までの数列Aの要素より大きい場合
⇒A[n]×B[n]がの可能性がある
・数列Bのn番目の数B[n]がn番目までの数列Bの要素より大きい場合
⇒数列Aのn番目の数までの最大値をa_maxとすると、a_max×B[n]がの可能性がある
・上のどちらにも該当しなければがとなる

この場合分けをループ内で判定し、最大値を求めていきます。
ループが抜けるまでcnを出力していけばACでした。

NG例

n = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 0

for i in range(n):
    if i == 0:
        ans = A[0] * B[0]
        print(ans)
    else:
        for j in range(i+1):
            ans = max(ans,A[j] * B[i])            
        else:
            print(ans)

コメント

cnを全探索で求めてTLEとなったNG例です。
がから更新されるのは2パターンしかないと気付くのに時間がかかりました。

今回 初めてARC相当の問題でACをとれてガッツポーズしちゃいました！
少しづつですが着実に前進していきたいです。