競技プログラミング用 知識集積所
ABC450D - Minimize Range
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
考察問題。
まず、kを足すことのみ許されているが、実はkを引くことを許しても本質的には何も変わらない。
というのは、最終的に考えるのは最大値と最小値の「差」だけであるので、自分以外全てにkを足せば実質自分からkを引くのと同じだからである。
ということで、Aの中身全てをkで割った余りに変更して考えてよい。
というのは、最終的に考えるのは最大値と最小値の「差」だけであるので、自分以外全てにkを足せば実質自分からkを引くのと同じだからである。
ということで、Aの中身全てをkで割った余りに変更して考えてよい。
そこからいくつかにkを足しながら最大最小差を調査していくが、単純に最も小さいものにkを足すことを繰り返していけばいいことは明らか。
deque※内でソートしてシミュレーションしてもいいし、余りとして登場しない数が続く最長部分（最大から最小+kまでの調査を忘れずに）を探してもいい。
deque※内でソートしてシミュレーションしてもいいし、余りとして登場しない数が続く最長部分（最大から最小+kまでの調査を忘れずに）を探してもいい。
