kmjp's blog

競技プログラミング参加記です

トリッキー問題コンテスト : A - 整数割り算

トリッキー問題コンテストに参加。
A,BはWAを重ねつつAC、Cは1発正答でした。
http://tricky.contest.atcoder.jp/tasks/tricky_1

問題

整数A,Bが与えられるとき、A/Bの整数部分を答えよ。
ただし両数値の範囲は-2^63~(2^63-1)である。(B!=0)

解法


C++では整数の除算でA,Bが負の場合、かつ割り切れないときの結果は未定義である。
g++の場合は、絶対値が切り捨て、すなわち数値としては切り上げになるので題意と等しい。

注意点として、Aは最小値は-2^63だが最大値は2^63-1であるため、A=-2^63、B=-1の時はそのまま計算するとおかしなことになる。

void solve() {
	int f,i,j,k,l,x,y,loop;
	int T;
	ll dead=0x8000000000000000LL;
	cin>>T;
	FOR(loop,T) {
		ll A,B;
		scanf("%lld%lld\n",&A,&B);
		if(B==-1 && A==dead) {
			char str[100];
			sprintf(str,"%lld",A);
			_P("%s\n",str+1);
			continue;
		}
		_P("%lld\n",(A/B));
	}
}

まとめ

2^63の問題は早期に気が付いたけど、負の時に切り捨てでなく切り上げになるのは問題文をちゃんと見てなくて気づくのが遅れた…。