Codeforces Round #127 Div1 B - Guess That Car! - kojingharangの日記

2012-06-30

Codeforces Round #127 Div1 B - Guess That Car!

10:39 |

Σy Σx Cxy * ( (4x+2 - 4px)**2 + (4y+2 - 4py)**2 ) を最小にする 0≦px≦M, 0≦py≦N とその最小値を求める問題
M, N ≦1000

縦横独立にできそう
Σy Σx Cxy * (4x+2 - 4px)**2 + Σy Σx Cxy * (4y+2 - 4py)**2
Σx (Σy Cxy) * (4x+2 - 4px)**2 + Σy (Σx Cxy) * (4y+2 - 4py)**2
(Σy Cxy) と (Σx Cxy) を予め求めておけば全 px に対して１項を計算して O(N^2) で最小値がわかる。py も同じ

Accepted

#define INF (1LL<<60)

int main() {
	int N, M;
	while(cin>>N>>M) {
		VVI w(N, VI(M));
		REP(y, N) REP(x, M) cin>>w[y][x];
		VI cx(M);
		REP(x, M) REP(y, N) cx[x] += w[y][x];
		VI cy(N);
		REP(y, N) REP(x, M) cy[y] += w[y][x];
		ll minxv = INF, minx = 10000;
		REP(px, M+1) {
			ll a=0;
			REP(x, M) {
				ll d = ( x*4+2 - px*4 );
				a += cx[x] * d * d;
			}
			if(a < minxv) { minxv = a; minx = px; }
		}
		ll minyv = INF, miny = 10000;
		REP(py, N+1) {
			ll a=0;
			REP(y, N) {
				ll d = ( y*4+2 - py*4 );
				a += cy[y] * d * d;
			}
			if(a < minyv) { minyv = a; miny = py; }
		}
		
		cout<<minxv+minyv<<endl;
		cout<<miny<<" "<<minx<<endl;
	}
	
	return 0;
}