Codeforces Global Round 2 : E. Pavel and Triangles

こういうのヒヤヒヤする。
https://codeforces.com/contest/1119/problem/E

問題

2の累乗の長さを持つ棒が多数与えられる。
３本を選び三角形を構成する、ということを繰り返すとき、最大でいくつの三角形を構築できるか。

解法

作れる三角形は、底辺が一番短い二等辺三角形か正三角形だけである。
二等辺三角形に場合、短い辺の長さはどれだけ短くても構わない。
すなわち短い順に棒を処理していけば、余った棒は底辺の構成用として長さを気にせず管理できることになる。

そこで、短い順に以下のように貪欲に処理していこう。

• より短い棒をできるだけ多く処理したいので、できるだけ二等辺三角形を作る。
• それでも今の長さの棒が余るなら、正三角形を作る。

int N;
ll A[303030];

void solve() {
	int i,j,k,r,x,y; string s;
	
	cin>>N;
	
	ll t=0;
	ll l=0;
	FOR(i,N) {
		cin>>A[i];
		
		ll m=min(l,A[i]/2);
		t+=m;
		l-=m;
		A[i]-=m*2;
		
		t+=A[i]/3;
		A[i]%=3;
		l+=A[i];
	}
	
	cout<<t<<endl;
	
}

まとめ

まぁ通ってよかったね。