SRM 552 250pt : FoxPaintingBalls

問題概要

赤、青、緑のボールがそれぞれR,G,B(<10^18)個ある。隣り合うボールの色が異なるような一辺N(<10^9)の三角形がいくつ作れるか求める問題。

考えたこと

(少し問題の解釈を間違えてサンプルが合わずに混乱していた)
ボールの置き方に自由度がほとんどないことは分かる。
とりあえず1個の三角形を作るのに各色がそれぞれいくつ必要か求めよう。
N^2だからオーバーフローするなあ。しかもサンプルにも入ってないし撃墜ポイント一つ確保。
で、1個の三角形作るのに色がいくつ必要かがパッと思いつかない。
N=7くらいまで図を書いて式らしきものを出す。
必要な色の個数がどれも一緒のときは単純に割ってminをとればよい。
必要な色の個数が違うときは、1個だけ多くなる。そのあまりをどれに押し付けるかが問題になるわけだけど…。
これはいくつ使うか決め打ちしたら考え易くなる。自明に単調性あるし二分探索か。
上限1e18だとおもったけど3e18か。自分のコードはN=1を例外処理してるから大丈夫だけどこれも撃墜ポイントになりそうだ。
二分探索は最近整理したばかりだからスマートにかけた。判定部分でオーバーフローの可能性ある箇所があったのでこれも撃墜時に留意しておこう…。
提出後、うっかりintを使ってないかとか最小ケースなどをチェックして一安心。
撃墜時は狙い通りN^2のオーバーフロー、二分探索の上限間違いで4撃墜。

反省

各色がどれだけ必要になるかは、差が高々一つしかないんだから総数が3で割りきれるかどうか調べるだけでよかった。こういう鳩ノ巣原理っぽい考えは綺麗で好きなんだけど気づけない場合が多い。

acceptされたコード

#include <algorithm>
using namespace std;

typedef long long int64;

struct FoxPaintingBalls {

	int64 theMax(int64 R, int64 G, int64 B, int64 N) {
		if (N == 1) {
			return R + G + B;
		}
		int64 num1 = 0, num2 = 0;
		if (N%3 == 0) {
			num1 = num2 = N*(N+1)/6;
		}
		if (N%3 == 1) {
			num1 = num2 = N*(N-1)/6;
			num1 += (N/3 + 1);
			num2 += (N - (N/3 + 1)) / 2;
		}
		if (N%3 == 2) {
			num1 = num2 = (N-1)*(N-2)/6;
			num1 += (N/3 + 1) + (N/3);
			num2 += (2*N - 1 - ((N/3 + 1) + (N/3))) / 2;
		}

		int64 ans = 0;
		if (num1 == num2) {
			ans = min(min(R/num1, G/num1), (B/num1));
		}
		else {
			int64 low = 0, high = int64(3.1e18);
			for (;high - low > 1;) {
				int64 mid = (low + high) / 2;
				if (R/num2 < mid || G/num2 < mid || B/num2 < mid) {
					high = mid;
					continue;
				}
				int64 res = (R - mid*num2) + (G - mid*num2) + (B - mid*num2);
				if (res < mid) {
					high = mid;
				}
				else {
					low = mid;
				}
			}
			ans = low;
		}

		return ans;
	}

};

冷静になって書き直したコード

typedef long long int64;

struct FoxPaintingBalls {

	int64 theMax(int64 R, int64 G, int64 B, int64 N) {
		if (N == 1) {
			return R + G + B;
		}
		int64 need = N * (N + 1) / 6;
		int64 extra = (N * (N + 1) / 2) % 3;
		int64 low = 0, high = int64(3.1e18);
		for (;high - low > 1;) {
			int64 mid = (high + low) / 2;
			bool ok = true;
			ok &= (R / need >= mid && G / need >= mid && B / need >= mid);
			//オーバーフローしてるけど大丈夫
			int64 res = (R - need * mid) + (G - need * mid) + (B - need * mid);
			ok &= res >= mid * extra;
			(ok ? low : high) = mid;
		}
		return low;
	}

};