✌️

# キーエンスプログラミングコンテスト2021 A - Two Sequences 2

2021/01/17に公開

keyence2021

キーエンスプログラミングコンテスト2021 A - Two Sequences 2

問題へのリンク

問題概要

長さ $N$ の数列 $a$ , $b$ があり、 $i$ 番目の数はそれぞれ $a_i$ , $b_i$ である。 $c_n = max_{1 \leqq i \leqq j \leqq n}a_ib_i$ を要素として持つ長さ $N$ の数列 $c$ を作る。各 $c_1, c_2, \dots, c_N$ を求めよ。

制約

$1 \leqq N \leqq 2 × 10^5$
$1 \leqq a_i, b_i \leqq 10^9$

ABC中の解答

制約 $1 \leqq N \leqq 2 × 10^5$ から単純に for を２回使って計算しては TLE となってしまうので何かしらの工夫は必要だと気づいた。けどそれが何かぱっと思いつかなかった。累積和と同じように累積Max的なものを取ればいいのかな？でも $A$ 側から使える $B$ が全部とは限らないしなと考えていた。
ノートにまとめていくと、 $c_i$ の場合 $A_i$ だけ $B_i$ のみしか考慮できないが、それより前の $A$ の値たちはすべての $B_i$ を考慮してよいと気づいたので、 $i$ より前の $A$ の最大値と $B$ の最大値をメモしておけば、最大値と $i$ 番目の値のみ考慮しそれ以外は計算しなくてよいと考えDP風に実装した。

$dp$ = [ $A$ の $i$ 番目までの最大値, $B$ の $i$ 番目までの最大値, $A_xB_y$ の最大値すなわち $c_i$ ]
とした。

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# cn = max1<=i<=j<=n aibj

dp = [A[0], B[0], A[0] * B[0]]
print(dp[2])
for i in range(1, N):
    dp[2] = max(dp[2], dp[0] * B[i], A[i] * B[i])
    dp[0] = max(dp[0], A[i])
    dp[1] = max(dp[1], B[i])
    print(dp[2])

公式解法1

$c_n$ は $c_n = max(c_{n-1}, max(a_1, a_2, \dots, a_n)b_n)$ と表すことができる。したがって、ABC中の解答でも触れたように累積Maxを計算しておけば $O(N)$ で解くことができる。

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

max_A = [A[0]]
for i in range(1, N):
    max_A.append(max(max_A[i - 1], A[i]))

C = [A[0] * B[0]]
for i in range(1, N):
    C.append(max(C[i - 1], max_A[i] * B[i]))

for c in C:
    print(c)