kmjp's blog

競技プログラミング参加記です

Codeforces #329 Div2 C. Beautiful Function

グダグダかと思ったら妙に順位が良かった。
http://codeforces.com/contest/593/problem/C

問題

2次元座標において、(0,0)-(50,50)の範囲を中心とする半径2以上の円がN個与えられる。

ここで、媒介変数tを用いた座標(f(t),g(t))を考える。
tを0~50の範囲の整数で動かすと、点が計51個出来る。
元のN個の円が、それぞれ最低1個以上の点を含むよう、f(t),g(t)の多項式を作れ。
なお、f,gはtの他0~50の整数、和・差・積・絶対値の演算を利用できる。

解法

tは不連続なので線を作ることはできないため、ジグザグに全格子点を通るようなアプローチは取れない。
t=0~(N-1)の時、ピンポイントでt番目の円を通るようf(t),g(t)を構築しよう。

t=iの時、(f(t),g(t))が(X[i],Y[i])を中心とする円の中に来るようにしたい。
ここで|t-i-1|+|t-i+1|-2*|t-i|という式を考える。
これはt==iの時は2で、それ以外の整数では0になる。

これを利用すると、f(t)=(X[i]/2)*(|t-i-1|+|t-i+1|-2*|t-i|)で構築できることがわかる。g(t)も同様。

int N;
int X[100][2],R[100];
string S[100][2];

string hoge(int i,int x) {
	char h[1010];
	sprintf(h,"(%d*((((0-abs((t-%d)))-abs((t-%d)))+abs(((t-%d)-1)))+abs(((t-%d)+1))))",x,i,i,i,i);
	return string(h);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i][0]>>X[i][1]>>R[i];
	FOR(j,2) {
		FOR(i,N) S[i][j]=hoge(i,X[i][j]/2);
		s = S[0][j];
		for(i=1;i<N;i++) s="("+s+"+"+S[i][j]+")";
		cout<<s<<endl;
	}
}

まとめ

ちょっと制限がきつくて変則的な問題。
まぁ本番解けて良かったけど。