No.3367 Looks like a convolution
タグ : / 解いたユーザー数 14
作問者 :
cho435
/ テスター :
jupiter_68
Naru820
noya2
問題文
要素数 $N$ の配列 $A=(A_0,A_1,\ldots,A_{N-1}) ,B=(B_0,B_1,\ldots,B_{N-1})$ が与えられます。 次のように定義される要素数 $N$ の配列 $C=(C_0,C_1,\ldots,C_{N-1})$ を出力してください。 $$C_k = \sum_{i,j \geq 0 ,\ i+j = k} {\min( \min(A[i,k]), \min(B[j,k]) )}$$ ただし配列 $V$ に対して $\min(V[a,b])$ とは、 $\min(V_a,V_{a+1},\ldots,V_{b})$ であるものとし、配列は0-indexedで考えるものとします。
制約
- 入力はすべて整数
- $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) $
入力
$N$
$A_0 \ A_1 \ \ldots \ A_{N-1}$
$B_0 \ B_1 \ \ldots \ B_{N-1}$
出力
$C$ の各要素を空白区切りで一行に出力してください。
サンプル
サンプル1
入力
5 5 2 4 1 3 4 5 3 2 1
出力
4 4 7 4 5
例えば $C_2$ は $$ 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 $$ です。
サンプル2
入力
10 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
出力
1 11 111 1111 11111 21111 4111 611 81 10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。