プログラミングの学習を始めたばかりで何から手を付ければ良いか分からない方は、まずは「practice contest」の問題 A「Welcome to AtCoder」をお試しください。言語毎に解答例が掲載されています。

この解説では、

• A 問題「119×2^23+1」の TLE 解法
• A 問題「119×2^23+1」の AC 解法
• どのような考察ステップで解法に至るか？
• サンプルコード

の 4 つを紹介します。

---

1. 解法 1（実行速度が遅い TLE 解法）

まず、\((a, b, c) = (0, 0, N)\) のとき明らかに「\(N=a \times 2^b + c\)」を満たすので、\(a + b + c \leq N\) であることが分かります。

そこで、非負整数の組 \((a, b, c)\) を \(a + b + c \leq N\) の範囲内で全探索することを考えます。自然に実装すると、次のようになります。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	// Step #1. 入力
	long long N;
	cin >> N;

	// Step #2. 答えを求める
	// 注意：(1 << i) は 2 の i 乗を意味します
	long long Answer = N;
	for (long long a = 0; a <= N; a++) {
		for (long long b = 0; a + b <= N; b++) {
			if (a * (1LL << b) > N) {
				// オーバーフローを回避するための break 文（long long 型では 9×10^18 程度までの整数しか表せない）
				break;
			}
			for (long long c = 0; a + b + c <= N; c++) {
				if (a * (1LL << b) + c == N) {
					// min(x, y) 関数は x と y のうち小さい方を返す
					Answer = min(Answer, a + b + c);
				}
			}
		}
	}

	// Step #3. 出力
	cout << Answer << endl;
	return 0;
}

残念ながら、このプログラムを提出すると、実行時間超過（TLE）となってしまいます。

最大ケースである \(N = 10^{18}\) の場合を考えてみましょう。そのとき、そもそも

• a = 0, b = 0 の状態

だけを考えても、\(3\) 重目のループでは \(c = 0, 1, 2, \cdots, N\) までループが回っているため、\(10^{18} + 1\) 回以上の演算を行っていることが分かります。

しかし、AtCoder では \(1\) 秒間に \(10^8 \sim 10^9\) 回程度しか計算を行えないため、本問題の実行時間制限である \(2\) 秒以内で実行が終わらないのです。

では、どうすれば良いのでしょうか。

---

2-1. 解法 2（実行速度が速い AC 解法）

\(b = 60\) の時点で \(2^b > 10^{18}\) となることに着目して、\(b\) の値を全探索することを考えます。つまり、

• \(b = 0\) で適切に \((a, c)\) を決めた場合、\(a + b + c\) の最小値はいくつか？
• \(b = 1\) で適切に \((a, c)\) を決めた場合、\(a + b + c\) の最小値はいくつか？
• \(b = 2\) で適切に \((a, c)\) を決めた場合、\(a + b + c\) の最小値はいくつか？
• \(:\)
• \(b = 60\) で適切に \((a, c)\) を決めた場合、\(a + b + c\) の最小値はいくつか？

といった感じで、いくつかの部分問題に分解することを考えます。

そこで、\(b\) が決まった後は \(a\) が条件を満たす中で最大になるようにすると、つまり

\[ a = \lfloor N \div 2^b \rfloor, c = N - \lfloor N \div 2^b \rfloor \times 2^b \]

にすると、\(a+b+c\) の値が最小になります。（\(\lfloor x \rfloor\) 記号についてはこちらを参照のこと）

このようなアルゴリズムでは、高々 \(60\) 回程度のループでプログラムの実行が終了し、余裕を持って実行時間制限に間に合います。（詳しくはサンプルコードを参照のこと）

---

2-2. 解法 2 の具体例

上の説明だけでは分からない読者がいるかもしれないので、\(N = 23\) の場合の具体例を載せておきます。

まず、\(b = 0\) のとき、以下のようになります。

部分問題
\(N = a \times 2^0 + c\)、つまり \(a + c = 23\) となる中で \(a+b+c\) の値を最小化したい。

考察
明らかに \(a + c = 23\) であるため、\(a + b + c\) の最小値は \(23\) である。

次に、\(b = 1\) のとき、以下のようになります。

部分問題
\(N = a \times 2^1 + c\)、つまり \(2a + c = 23\) となる中で \(a+b+c\) の値を最小化したい。

考察
\((a, c) = (11, 1), (10, 3), (9, 5), (8, 7), (7, 9), (6, 11), (5, 13), (4, 15), (3, 17), (2, 19), (1, 21), (0, 23)\) が条件を満たす。
そこで、\(a\) が \(1\) 減るごとに \(a+b+c\) の値が \(1\) 増えるので、\(a\) が最大の場合（\((a, b, c) = (11, 1, 1)\)）が最適である。
そのときの \(a+b+c\) の値は \(13\) である。

次に、\(b = 2\) のとき、以下のようになります。

部分問題
\(N = a \times 2^2 + c\)、つまり \(4a + c = 23\) となる中で \(a+b+c\) の値を最小化したい。

考察
\((a, c) = (5, 3), (4, 7), (3, 11), (2, 15), (1, 19), (0, 23)\) が条件を満たす。
そこで、\(a\) が \(1\) 減るごとに \(a+b+c\) の値が \(3\) 増えるので、\(a\) が最大の場合（\((a, b, c) = (5, 2, 3)\)）が最適である。
そのときの \(a+b+c\) の値は \(10\) である。

次に、\(b = 3\) のとき、以下のようになります。

部分問題
\(N = a \times 2^3 + c\)、つまり \(8a + c = 23\) となる中で \(a+b+c\) の値を最小化したい。

考察
\((a, c) = (2, 7), (1, 15), (0, 23)\) が条件を満たす。
そこで、\(a\) が \(1\) 減るごとに \(a+b+c\) の値が \(7\) 増えるので、\(a\) が最大の場合（\((a, b, c) = (2, 3, 7)\)）が最適である。
そのときの \(a+b+c\) の値は \(12\) である。

次に、\(b = 4\) のとき、以下のようになります。

部分問題
\(N = a \times 2^4 + c\)、つまり \(16a + c = 23\) となる中で \(a+b+c\) の値を最小化したい。

考察
\((a, c) = (1, 7), (0, 23)\) が条件を満たす。
そこで、\(a\) が \(1\) 減るごとに \(a+b+c\) の値が \(15\) 増えるので、\(a\) が最大の場合（\((a, b, c) = (1, 4, 7)\)）が最適である。
そのときの \(a+b+c\) の値は \(12\) である。

最後に、\(b \geq 5\) の場合は \((a, c) = (0, N)\) しか条件を満たしませんが、\(a+b+c > N\) であるため考える必要がありません。

このようなステップで、\(N = 23\) の場合の答えが \(10\) となることが分かります。

※今回は便宜上 \(b \geq 5\) で切っていますが、実際の制約は \(N \leq 10^{18}\) であるため、\(b = 60\) まで考える必要があります。

---

3. どうやって解法を思いつくか？

これは典型なのですが、探索すべき場合の数が小さそうな変数（通常は 1～2 個）を決め打ちして全探索するというテクニックがあります。

今回の場合、各値の「考えるべき範囲」は、例えば \(N = 10^{18}\) のとき以下のようになります。

• \(a\)：\(0\) 以上 \(10^{18}\) 以下の \(10^{18} + 1\) 通り
• \(b\)：\(0\) 以上 \(60\) 以下の \(61\) 通り
• \(c\)：\(0\) 以上 \(10^{18}\) 以下の \(10^{18} + 1\) 通り

したがって、最も場合の数が少ない \(b\) を全探索（決め打ち）したうえで、最適な \(a, c\) の値が \(b\) によって決められないか考えるのが賢明です。

類題

同じようなテクニックを使う問題として、例えば以下の問題が挙げられます。

\(a \times b! = N\) となるような正整数の組 \((a, b)\) はいくつ存在するか？（制約：\(N \leq 10^{18}\)）

この問題では \(20! > 10^{18}\) より \(1 \leq b \leq 19\) であることを考慮すると、\(b\) を全探索（決め打ち）する方法が効率的です。

その他にも、

• AtCoder Beginner Contest 085 C - Otoshidama
• AtCoder Regular Contest 108 A - Sum and Product

などで同様のテクニックが使えます。

---

4. サンプルコード

まず、C++ での解答例は次のようになります。（リンク）

制約が \(N = 10^{18}\) と大きいため、long long 型など \(64\) ビット整数を扱う必要があることに注意してください。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	// Step #1. 入力
	long long N;
	cin >> N;

	// Step #2. 答えを求める
	// C++ では、整数型 a, b があったとして、a / b が「a / b の商（小数点以下切り捨て）」になることに注意
	// (1LL << i) は 2 の i 乗を意味します
	long long Answer = (1LL << 60);
	for (int i = 0; i <= 60; i++) {
		long long a = N / (1LL << i);
		long long b = i;
		long long c = N - a * (1LL << i);
		Answer = min(Answer, a + b + c);
	}

	// Step #3. 出力
	cout << Answer << endl;
	return 0;
}

他のプログラミング言語でのサンプルコードは、次の通りです。

• Python：https://atcoder.jp/contests/arc119/submissions/22629725
• JAVA：https://atcoder.jp/contests/arc119/submissions/22631998
• C：https://atcoder.jp/contests/arc119/submissions/22632583