kojingharangの日記

Codeforces Round #127 Div1 A - Clear Symmetry

10:39 |

• 1 が隣り合わない and 上下左右対称 and 1 の個数が X 個になるように 0 か 1 を NxN グリッドに入れたい。最小の N を求める問題。
• X ≦ 100

• X==2 とか配置できんの？？と思ったけど真ん中の列の上下に置けばいいのか
• 真ん中を含む左上の領域を考えて、そこに１を置いて上下左右対称になるように展開すると全体として何個１が増えるかを考える。

// N==3
４２
２１

４のとこに置くと以下のように１が４つになる
１０１
０００
１０１

右上の２のとこに置くと以下のように１が２つになる
０１０
０００
０１０

// N==4
４４
４４

// N==5
４４２
４４２
２２１

• そこから 1 が隣り合わないように市松模様の黒のとこにある数字だけ抜き出す。X がその数字の和で表せたら OK。
• 黒と白で２通り試しながら N を大きくしていくといつか終わる。
• この抜き出し方でいい証明はできてない

// X==9 N==5 のばあい
　４　
４　２
　２　
→4 4 2 2 じゃ 9 にならないので skip

４　２
　４　
２　１
→4+4+1==9 なので N==5 で OK

// X==3 N==5 のばあい
　４　
４　２
　２　
→4 4 2 2 じゃ 3 にならないので skip

４　２
　４　
２　１
→2+1==3 なので N==5 で OK

• Accepted

int main() {
	int X;
	
	while(cin>>X) {
		for(int n=1;;n++) {
			//cout<<n<<endl;
			{
				int x = X;
				int n4 = (n-1)*(n-1)/2;
				int n2 = ((n-1)/2 + ((n-1)&1))*2;
				int n1 = 0;
				//cout<<n4<<" "<<n2<<" "<<n1<<endl;
				while(n4-->0 && x>=4) x-=4;
				while(n2-->0 && x>=2) x-=2;
				while(n1-->0 && x>=1) x-=1;
				if(x==0) { cout<<2*n-1<<endl; break; }
			}
			{
				int x = X;
				int n4 = (n-1)*(n-1)/2 + ((n-1)*(n-1)&1);
				int n2 = (n-1)/2*2;
				int n1 = 1;
				//cout<<n4<<" "<<n2<<" "<<n1<<endl;
				while(n4-->0 && x>=4) x-=4;
				while(n2-->0 && x>=2) x-=2;
				while(n1-->0 && x>=1) x-=1;
				if(x==0) { cout<<2*n-1<<endl; break; }
			}
		}
	}
	
	return 0;
}

ツイートする

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;
}

ツイートする