ABC 153 D - Caracal vs Monster

問題

思考のアプローチ

言われたとおりに実装すると以下のケースで TLE になる。

そこで考え方を変える必要がある。
そんな時は手を動かして法則性を探す。

汚い字で申し訳ない、以下のような感じで書き出した。

ここまで書き出すことで、2で割り切れるまでカウント値は変わらない事が分かりました。
しかも回答は 2^(n+1)-1 のようです。
これが分かれば後はコードに落とすだけ。

abc153d.cpp

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main() {
	long long H,cnt=0; cin >> H;
	long long ans=1;

	if(H!=1){
		for (int i = 1; i < 1000; i++) {
			if (pow(2, i) == H) {
				cnt = i;
				break;
			}
			else if (pow(2, i) > H) {
				cnt = i - 1;
				break;
			}
		}
		ans = pow(2, cnt + 1) - 1;
	}
	
	cout << ans;
	//while (1) {}
	return 0;
}

再帰的に書くとシンプルになりました。

abc153d.cpp

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int rec(long long H,int n) {

	if (H == 1)
		return n;

	int cnt = rec(H / 2, n + 1);
	return cnt;
}

int main() {
	long long H, cnt = 0; cin >> H;
	long long ans = 1;
    if(H!=1){
		cnt = rec(H,0);
		ans = pow(2, cnt + 1) - 1;
	}

	cout << ans;
	//while (1) {}
	return 0;
}

もっと説明用に文章と図を入れた方がいいのかな～
只のメモになってしまった。。。
ま、いっか(笑)