人工知能と競プロやってくブログ

深層学習・機械学習・AI・atcoder・競技プログラミングについて調べてやってみたことをまとめるブログです

AtCoder 🟫茶diff Python 数学問題区間問題

入力例１のデータを元に、具体的に考えてみます。

2 5
10 12 1 2 14

数列Xを、まずはソート。

1 2 10 12 14

このXiのとなりの値との差を計算する。
この数列をDとする。

1 8 2 2

ここまでの状態を図にしてみる。

区間を表す数列Dは4個。コマの数(N)は2個。
それぞれのコマが区間を2個、1個、都合3個移動すれば条件クリア。
つまり1個の区間は省くことができる。
移動しなければいけない区間数3は、N-Mで計算することができる。

移動量をもっとも少なくする問題なので、一番大きい区間を省くのが効率的。

ゆえにDをソート。

1 2 2 8

移動しなければいけない区間数3を頭から足していく。
1 + 2 + 2 = 5
答えは5となる。