No.2603 Tone Correction
タグ : / 解いたユーザー数 39
作問者 : 👑
amentorimaru
/ テスター :
👑 Problem Statement
Etowanyu is trying to process the texture of his avatar to modify its colors.
The avatar's texture consists of $N$ numbers, which are initially $A_1, A_2,\dots ,A_N$, and he eventually wants to make them equal to $B_1,B_2,\dots, B_N$.
Etowanyu can use the following tone correction operation any number of times.
- Select a tone correction range $L,R (1 \le L \le R \le N)$.
- Select an integer $x$, which may be negative.
- Replace $A_L, A_{L+1}, \dots , A_R$ with $(A_L + x) \mod M, (A_{L+1} + x) \mod M, \dots , (A_R + x) \mod M$, respectively.
He performs operations using tone correction to make $A_1, A_2,\dots ,A_N$ equal to $B_1,B_2,\dots, B_N$. Let $T$ be the number of operations used, and let $x_i$ be the $x$ chosen in the $i$-th operation. Find the minimum possible value of $\sum_{i=1}^{T} |x_i|$.
Input
$N\ M$ $A_1\ A_2\ \dots \ A_N$ $B_1\ B_2\ \dots \ B_N$
- All inputs are integers.
- $1\le N \le 2\times 10^5$
- $1\le M \le 10^9$
- $0\le A_i,B_i < M$
Output
Output the answer.
Sample
Sample 1
Input
4 256 3 5 5 8 2 2 4 8
Output
3
First, if Etowanyu selects $L=1, R=3, x=-1$, then $A=(2,4,4,8)$.
Next, if he selects $L=2, R=2, x=-2$, then $A=(2,2,4,8)$, and $A$ and $B$ are equal.
The sum of $|x|$ in this case is $3$, which is the minimum.
Sample 2
Input
3 256 0 0 0 255 255 255
Output
1
Since the values are replaced modulo $\mod M$, selecting $L=1, R=3, x=-1$ is optimal.
Sample 3
Input
10 256 69 71 116 253 128 177 184 43 187 147 168 154 1 242 219 120 4 98 171 131
Output
379
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。