Codeforces #171 Div2. A. Point on Spiral, B. Books

さてCF#171。Div2なので練習のみ。
http://codeforces.com/contest/279/problem/A
http://codeforces.com/contest/279/problem/B

A. Point on Spiral

原点から初めて、格子点を結んでらせん状に線分をつなげていく。
ある格子点の座標が与えられたときに、何回線分を曲げた時点でそこに到達するか答える。

座標はさほど大きくないので、実際に与えられた格子点を辿るまでらせんを作ればよい。

int X,Y;

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	X=GETi();
	Y=GETi();
	if(X==0 && Y==0) {
		_P("%d\n",0);
		return;
	}
	
	x=y=0;
	FOR(num,500) {
		l=1+(num/2);
		FOR(j,l) {
			if(num%4==0) x++;
			if(num%4==1) y++;
			if(num%4==2) x--;
			if(num%4==3) y--;
			if(X==x && Y==y) {
				_P("%d\n",num);
				return;
			}
		}
	}
	
	return;
}

B. Books

N冊の本が並んでおり、各本を読むのにかかる時間が与えられる。
ある本から読み始めたとき、次は隣の本を順々に読まなければならない。
与えられた時間で読める本の最大数を答える。

これは実際に各本から読み始めた場合に何冊読めるか計算すればよい。
ただ、毎回何冊読めるか計算するとO(N^2)かかって時間が苦しい。
そこで、読み始め位置を１個ずらした場合に読み終わりを何個ずらせるかを計算しておくことで、O(N)に押さえることができる。

int N;
int A[100001];
ll T;

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	N=GETi();
	T=GETi();
	FOR(i,N) A[i]=GETi();
	
	ll tot=0;
	x=0;
	FOR(y,N) {
		tot+=A[y];
		while(tot>T) {
			tot-=A[x];
			x++;
		}
		ma=max(ma,y-x+1);
	}
	
	_P("%d\n",ma);
	return;
}

まとめ

Bのように、数値配列におけるある範囲内での合計値を求めるときに、始点・終点をずらしながら計算する処理は覚えておかないとな。