公式
C - ±1 Operation 1 解説 by physics0523
まず、 \(D<0\) であるケースがあると非常に扱いづらいので、以下のように \(D \ge 0\) となるよう正規化します。
- \(A=A+D \times (N-1)\) 、\(D=-D\) と(同時に)置き換える。
これは等差数列の反転に相当します。例えば、 \(A=8,D=-3,N=3\) であるとき数列 \(S=(8,5,2)\) ですが、 \(A=2,D=3,N=3\) と置き換えると \(S=(2,5,8)\) となり、数列が前後反転しただけで「良い数」の集合は変化しません。
方針1: \(X\) に最も近い \(S\) の要素を二分探索で求める
数列 \(S\) には \(0 \le k \le N-1\) なる全ての整数 \(k\) に対して \(A+kD\) が含まれますが、 \(D \ge 0\) で \(S\) が広義単調増加であるため、 \(k\) を調整する二分探索によって \(X\) に最も近い \(S\) の要素を見つけようとする解法が成立します。
実装例(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
long long x,a,d,n;
cin >> x >> a >> d >> n;
if(d<0){
long long fi=a+d*(n-1);
a=fi;
d*=-1;
}
long long st=0,fi=(n-1);
while(st<=fi){
long long te=(st+fi)/2;
if((a+d*te)<x){st=te+1;}
else{fi=te-1;}
}
long long res=8e18;
for(long long i=max(0ll,st-5);i<=min((n-1),st+5);i++){
res=min(abs(a+d*i-x),res);
}
cout << res << '\n';
return 0;
}
方針2: 場合分けで解き切る
等差数列に含まれる最小値 \(st=A\) 、 最大値 \(fi=A+(N-1)D\) とします。
- \(st \le X \le fi\) であるとき、
- \(D=0\) のとき、答えは \(0\) です。
- そうでないとき、 \(S\) には \(0 \le k \le N-1\) なる全ての整数 \(k\) に対して、 \(A+kD\) が含まれ、さらに \(A \le X \le A+(N-1)D\) が成立するため、答えは \(\min((X-A)\%D,D-(X-A)\%D)\) です。(但し、 \(p\%q\) で \(p\) を \(q\) で割った余り)
- \(X < st\) であるとき、答えは \(st-X\) です。
- \(fi < X\) であるとき、答えは \(X-fi\) です。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
long long x,a,d,n;
cin >> x >> a >> d >> n;
if(d<0){
long long fi=a+d*(n-1);
a=fi;
d*=-1;
}
long long st=a;
long long fi=a+d*(n-1);
if(st<=x && x<=fi){
long long m;
if(d!=0){m=(x-st)%d;}
else{m=0;}
cout << min(m,d-m) << '\n';
}
else if(x<st){cout << st-x << '\n';}
else{cout << x-fi << '\n';}
return 0;
}
投稿日時:
最終更新: