Saiko~ No Contesuto #02 : すごろくチキンレース

しょうもないミスを繰り返した。
https://www.hackerrank.com/contests/camypapercon02/challenges/sugoroku-chicken-race

問題

Nマスピッタリ進むと終了の双六がある。
この双六はM面のサイコロを用いる。各面の値はA[i]である。

各面の値を(正の整数の範囲で)変化させ、目がどういう風に出ても必ずピッタリNマスの地点を通るようにしたい。
各目の変化の絶対値の総和の最小値を求めよ。

解法

どの目が出てもNマスの地点を通るようにするには、結局すべてを同じ目にし、かつそれがNの約数でなければならない。
よって各目をNの約数にする場合の変化の絶対値の総和を順次計算していくと良い。

総和の計算は愚直に一つずつ計算していくと、約数が多いNの場合にTLEする。
よって累積和等使い総和の計算を高速化しよう(高速化さぼったら1TLEした)。

ll N,M;
ll A[404040];
ll S[404040];

ll dodo(ll v) {
	int x=lower_bound(A,A+M,v)-A;
	return (S[M]-S[x]-v*(M-x))+(v*x-S[x]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>A[i];
	sort(A,A+M);
	FOR(i,M) S[i+1]=S[i]+A[i];
	
	ll ret=1LL<<60;
	for(ll a=1;a*a<=N;a++) if(N%a==0) {
		ret=min(ret,dodo(a));
		ret=min(ret,dodo(N/a));
	}
	cout<<ret<<endl;
}

まとめ

本番、上記TLEの他にも、目の値を減らすことしかできないと勘違いしてWAした。