UTPC2013 B 13月

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_02）

うなぎ暦はy年には13 + (y - 2013)月まである。（2013年は13月、2014年は14月…）
西暦のy年m月が与えられたとき、うなぎ暦のy'年m'月に変換せよ。

制約条件

y≦10^17
m≦12
yは2013以上。

方針

まずはy mを2013年の最初から数えて何月目かに変換。
m = m + 12 * (y - 2013)

うなぎ暦y年の開始時までの月数は、
13 + 14 + ... + {13 + (y - 2013)}　（等差級数）
= 13 * (y - 2013) + (y - 2013) * (y - 2013 - 1) / 2

なので、これをyの関数として二分探索して、年数を求めればいい。
年数がわかったら、mからその年数のはじまり時点での月数を引けば月がわかる。

オーバーフローと二分探索の上限が十分かに注意しましょう（自戒）

ソースコード

int main(){
	ll y, m;
	cin >> y >> m;
	
	m += (y - 2013) * 12;
	ll lo = -1, hi = 1e18, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		double md = mid;
		if(m + 100 < 13 * md + md * (md - 1) / 2 || //オーバーフローしないかdoubleで一度計算してチェックしている
		m <= 13 * mid + mid * (mid - 1) / 2) hi = mid;
		else lo = mid;
	}
	cout << 2013 + lo << " " << m - 13 * lo - lo * (lo - 1) / 2 << endl;
	
	return 0;
}