問題一覧 > 通常問題

No.2603 Tone Correction

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 39
作問者 : 👑 amentorimaru / テスター : 👑 seekworser 👑 獅子座じゃない人
お気に入りにしたユーザー ProblemId : 10210 / 自分の提出
問題文最終更新日: 2024-01-12 21:28:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 414 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。