読者です 読者をやめる 読者になる 読者になる

Codeforces Round #317 Div1 A: Lengthening Sticks

問題

codeforces.com

解法

合計lだけ長くした時、辺の組み合わせは全部で(l+2)*(l+1)/2通りになる。このうちhalf=(a+b+c+l-1)/2とした時に、辺の長さがhalfを超える場合三角形にならないので引けばいい。

コード

import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int[] abc = new int[3];
		int sum = 0;
		for (int i = 0; i < 3; i++) {
			abc[i] = scanner.nextInt();
			sum += abc[i];
		}

		int L = scanner.nextInt();
		scanner.close();

		long ans = 0;
		for (int l = 0; l <= L; l++) {
			// 長さをl追加する場合を考える
			long all = sum + l;
			long half = (all - 1) / 2;
			if (abc[0] > half || abc[1] > half || abc[2] > half) {
				continue;
			}

			// まずは分配の仕方を足す
			ans += (long) (l + 2) * (l + 1) / 2;
			for (int i = 0; i < 3; i++) {
				if (abc[i] + l > half) {
					// lの分配の仕方によっては三角形を作れないパターンもある
					// よってabc[i]+l>halfとなるパターンについて引き算する
					long remainer = abc[i] + l - (half + 1);
					ans -= (remainer + 2) * (remainer + 1) / 2;
				}
			}

		}
		System.out.println(ans);

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}