No.3367 Looks like a convolution
タグ : / 解いたユーザー数 16
作問者 :
noya2
Problem Statement
You are given arrays $A=(A_0,A_1,\ldots,A_{N-1}) ,B=(B_0,B_1,\ldots,B_{N-1})$, each with $N$ elements. Output the array $C=(C_0,C_1,\ldots,C_{N-1})$ with $N$ elements, defined as follows. $$C_k = \sum_{i,j \geq 0 ,\ i+j = k} {\min( \min(A[i,k]), \min(B[j,k]) )}$$ Here, for an array $V$, $\min(V[a,b])$ denotes $\min(V_a,V_{a+1},\ldots,V_{b})$, and arrays are considered 0-indexed.
Constraints
- All input values are integers.
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9 \ (0 \leq i \leq N-1) $
- $1 \leq B_i \leq 10^9 \ (0 \leq i \leq N-1) $
Input
$N$
$A_0 \ A_1 \ \ldots \ A_{N-1}$
$B_0 \ B_1 \ \ldots \ B_{N-1}$
Output
Output the elements of $C$ on a single line, separated by spaces.
Sample
Sample 1
Input
5 5 2 4 1 3 4 5 3 2 1
Output
4 4 7 4 5
For example, $C_2$ is $$ C_2 = \min(\min(A[0,2]), \min(B[2,2])) + \min(\min(A[1,2]), \min(B[1,2])) + \min(\min(A[2,2]), \min(B[0,2])) \\ = \min(\min(5,2,4),\min(3)) + \min(\min(2,4),\min(5,3)) + \min(\min(4),\min(4,5,3)) = 7 $$ .
Sample 2
Input
10 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
Output
1 11 111 1111 11111 21111 4111 611 81 10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。