topcoder

kojingharangの日記

2013-02-16

Facebook Hacker Cup Round2 A - Cake Cutting

19:15 |

長さ N の数列 A が与えられる。まるいケーキがあって、A の各要素について A[i] 回折れ曲がる線でカットする。ただし折れ曲がる点はケーキ内に限定する。ケーキは最大何個の部分に分けられるか求める問題。
1≦N≦100, 1≦A[i]≦400 for i in [0, N)
図 https://www.facebook.com/hackercup/problems.php?pid=500995316613418&round=499927843385312

直ちに影響がある眠さ（朝６時）

円卓に座ったビジネスマンが握手するやつに似てるので何らかのDPかな
...
１時間くらい

各カットについて、
(1) そのカット自身だけで生じる部分 ... ((A[i]-1)*A[i]/2)
(2) すでにカットした線分の数に依存する部分 ... すでにカットした線分の数 * (A[i]+1) +1
の領域が新たに発生することにしたらサンプルが通った。証明できないしもしもっと複雑な事情であっても分からないだろうからこれでサブミット

Accepted (おー)

int main() {
	int T;
	cin>>T;
	REP(ttt, T) {
		ll N;
		cin>>N;
		VI A(N);
		REP(i, N) cin>>A[i];
		
		ll lines=0;
		ll ans=1;
		
		REP(i, N) {
			ans += lines*(A[i]+1) + ((A[i]-1)*A[i]/2) +1;
			lines += A[i]+1;
		}
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
//		break;
	}
	return 0;
}