Codeforces #732 Div1 : D. AquaMoon and Wrong Coordinate

これまたへんてこな問題。
https://codeforces.com/contest/1545/problem/D

問題

N人の人が走る。
i番の人は初期位置X[i]におり、時速V[i]で走る。その結果、時刻TにはX[i]+T*V[i]にいることになる。

この問題では、X,Vは明に与えられない。
時刻0～(K-1)のそれぞれにおいて、各人の座標が与えられる。
ただし、返された座標が、N人の誰のものかは毎回シャッフルされたものとする。

ここで、与えられた座標のうち1個だけ誤りがある。
誤りのある時刻と、正しい値を求めよ。

解法

各人の座標の和を取ると、sum(X)+T*sum(V)となる。
よって、時刻毎にその値を取ると等差数列になるはずであり、3要素間の値を比較すれば誤った時刻がわかる。

時刻はわかったとして、次は誰の座標が誤っているかを求めなければならない。
座標の和と、座標の2乗和を取り、誤った時刻の値と、他の時刻から推測した正しい値を比較すれば、誤った座標と正しい座標を求められる。

int M,K;
ll X[1010][1010];
ll S[1010];
ll S2[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>K;
	FOR(y,K) {
		FOR(x,M) {
			cin>>X[y][x];
			S[y]+=X[y][x];
			S2[y]+=X[y][x]*X[y][x];
		}
	}
	map<ll,int> D;
	FOR(y,K-1) D[S[y+1]-S[y]]++;
	ll SV;
	FORR2(a,b,D) if(b>=2) SV=a;
	int inval=-1;
	for(i=1;i<K-1;i++) {
		if(S[i]-S[i-1]!=SV&&S[i+1]-S[i]!=SV) inval=i;
	}
	
	ll SV2=0;
	FOR(i,K-2) {
		if(inval<i||i+2<inval) {
			SV2=(S2[i+2]+S2[i]-2*S2[i+1])/2;
			break;
		}
	}
	
	ll add=(S[inval+1]+S[inval-1]-2*S[inval])/2;
	ll add2=(S2[inval+1]+S2[inval-1]-2*S2[inval])/2-SV2;
	ll sum=add2/add;
	ll ret=(sum+add)/2;
	cout<<inval<<" "<<ret<<endl;
	
	
}

まとめ

これはいろいろ解法がありそう。