ABCのC問題ぐらいは解けないと人権がないらしいので、頑張って解きたいと思ってます。
なので、今回も解けたからメモ。今回の問題は以下の通り。
[blogcard url=”https://beta.atcoder.jp/contests/abc102/tasks/arc100_a”]
問題読んで最初に考えたことは、「どうせソートしそうだな」ということです。ただ、単純にソートすることはできないので、ちょっと与えられた数列をいじくります。
数列を眺めてると、(A_i-(i-b)=(A_i-i)-b)ということに気がつくので、数列の入力時にiを引いてしまえばいいことがわかります。この時点で与えられた数列の順番が関係なくなるのでソートできます。
次にbの値をどうするか考えなければなりません。私は最初平均値か中央値かで迷って平均値でコード書きました。サンプルは全部通ったのですが、提出すると散々な結果になってしまいました。
とりあえず解説読んで中央値だということはわかりましたが、なぜ中央値なのか書いてなかったので証明したいと思います。
証明自体はFLLAPY@がんばれない系無職(@flappyjp)さんが考えてくれました。ありがとうございます。私は自力で証明できませんでした・・・無力なり・・・。
字は雑だし、正の範囲にしか言及してないけど多分こんな感じ？絶対値絡みならまぁ負の範囲含めても自然にこんな感じになると思ってめんどいからパスした pic.twitter.com/qDBBbWqjA5
— FLAPPY@がんばれない系無職 (@flappyjp) 2018年7月9日
[mathjax]
ここで、\(|a_1 -b|+|a_n -b|\)を考える。
(i)\(b\leq a_1\leq a_n\)の時
$$(a_1 -b)+(a_n -b)=a_n – a_1 +2(a_1 -b)$$
(ii)\(a_1\leq b\leq a_n\)の時
$$-(a_1 -b)+(a_n -b)=a_n – a_1$$
(iii)\(a_1\leq a_n\leq b\)の時
$$-(a_1 -b)-(a_n -b)=a_n – a_1+2(b-a_n)$$
\(a_1 -b\)と\(b-a_n\)は0以上であるので、(i)~(iii)の中で最小になるのは、\(b\)が\(a_1\leq b\leq a_n\)の範囲にあるときである。
同様に\(|a_2 -b|+|a_n-1 -b|\),\(|a_3 -b|+|a_n-2 -b|\),\(\cdots\)も同様である。
ここで、nが偶数のときと奇数のときで中央値の位置が変わるので場合分けをする。
nが奇数の時、中央値は\(a_\frac{n+1}{2}\)である。この時、\(\displaystyle \sum^{n}_{k=1}|a_k -b|\)が最小となるのは、\(|a_\frac{n+1}{2}-b|=0\)となるときである。
よって、\(b=a_\frac{n+1}{2}\)であり、\(b\)は数列\(a\)の中央値と一致する。
nが偶数の時、\(\displaystyle \sum^{n}_{k=1}|a_k -b|\)が最小となるのは、\(|a_\frac{n}{2}-b|+|a_\frac{n+2}{2}-b|\)が最小のときである。(i)~(iii)より、これが最小となる時、\(b\)の範囲は\(a_\frac{n}{2}\leq b \leq a_\frac{n+2}{2}\)であり、この範囲に中央値は含まれる。
以上のことから、求める\(b\)の値は数列\(a\)の中央値と一致することがわかる。
上の証明は数列の各項が正の元でやってますが、負が入っても場合分け増えるだけで証明の大筋は変わらないはず・・・。
ということで、今までのことをコードにすると、以下の様になりました。
[cpp]
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
using ll = long long;
int main(int argc, char const *argv[]) {
int n;
cin>>n;
ll a[n];
for(int i=0;i<n;i++){
ll tmp;
cin>>tmp;
a[i]=tmp-i;
}
// ll med1=0,med2=0,median=0,ans1=0,ans2=0,ans=0;
ll med1=0,med2=0,median=0,ans=0;
// bool flag=0;
sort(a,a+n);
// for(int i=0;i<n;i++){
// cout<<a[i]<<",";
// }
// cout<<endl;
if(n%2==0){
// cout<<"n/2-1="<<n/2-1<<",n/2="<<n/2<<endl;
med1=a[n/2-1];
med2=a[n/2];
median=(med1+med2)/2;
}else{
median=a[n/2];
// flag=1;
}
// if(flag){
// for(int i=0;i<n;i++){
// ans1+=abs(a[i]-med1);
// }
// cout<<ans1<<endl;
// }else{
// for(int i=0;i<n;i++){
// ans1+=abs(a[i]-med1);
// ans2+=abs(a[i]-med2);
// }
// cout<<"med1="<<med1<<",med2="<<med2<<endl;
// cout<<"ans1="<<abs(ans1)<<",ans2="<<abs(ans2)<<endl;
// cout<<min(ans1,ans2)<<endl;
// }
for(int i=0;i<n;i++){
ans+=abs(a[i]-median);
}
cout<<ans<<endl;
return 0;
}
[/cpp]
これで72msでした。その他の解答もそんな感じだったので、まあいいかなあと。
証明がキレイで、送られてきたリプを見ながら自分で書いてみて、「あーなるほどなー」ってとても感動してました。両端から潰していく発想はなかったです。
C問題埋めは夏休みにできればいいんだけど、夏休みはバイトとロードバイクで忙しいからなあ・・・時間見つけてやろう。