パズルだ！！

問題概要

正の整数 $M, K$ が与えられる。 $n$ 個の正の整数 $a_1, \dots, a_n$ を用意して、

$a_1, \dots, a_n$ がそれぞれ $K$ 個ずつあるとして
それらの足し引きによって $1, 2, \dots, M$ までの整数がすべて作れる

という条件を満たすような最小の $n$ を求めよ。

制約

$1 \le M \le 10^{9}$
$1 \le K \le 10^{5}$

考えたこと

$K = 1$ の場合は結構な有名問題！！！
こういうの一見して

$a = (1, 2, 4, 8, 16, ...)$

とやると効率が良さそうに思える。実際、「足し引き」のうち「足す」のみを許容していたら、これがピッタリ。

1 = 1
2 = 2
3 = 1 + 2
4 = 4
5 = 1 + 4
6 = 2 + 4
7 = 1 + 2 + 4
8 = 8
9 = 1 + 8
10 = 2 + 8
...

という感じ。こんな風に、「任意の整数は、二冪の和で表せる」というのは、AtCoder の構築問題で非常に多く見られる典型！！！

しかし「引き」も認めると自由度が上がる。実は二冪の代わりに三冪にすると良いのだ！！！

$a = (1, 3, 9, 27, ...)$

実際こんな感じ

1 = 1
2 = -1 + 3
3 = 3
4 = 1 + 3
5 = -1 - 3 + 9
6 = -3 + 9
7 = 1 - 3 + 9
8 = -1 + 9
9 = 9
10 = 1 + 9
11 = -1 + 3 + 9
12 = 3 + 9
13 + 1 + 3 + 9

14 = -1 - 3 - 9 + 27
15 = -3 - 9 + 27
...

ちょうどいい感じに、切れ目なく作れることがわかる。実はこれは平衡三進法展開とかよばれてたと思う。それを題材にした問題も過去に TopCoder で出ている。

今回の問題

今回のように、 $a_1, a_2, \dots, a_n$ が $K$ 個ずつ作れるようになっても、ちょっとした拡張で解くことができる。具体的には

$a = (1, 2k+1, (2k+1)^{2}, \dots)$

で OK！たとえば $K = 3$ のとき

$a = (1, 7, 49, ...)$

として

1 = 1
2 = 1 + 1
3 = 1 + 1 + 1
4 = -1 - 1 - 1 + 7
5 = -1 - 1 + 7
6 = -1 + 7
7 = 7
8 = 1 + 7
+ ...
+ 24 = 1 + 1 + 1 + 7 + 7 + 7
+ 25 = -1 - 1 - 1 - 7 - 7 - 7 + 49
+ 26 = -1 - 1 - 7 - 7 - 7 + 49
+ ...

という感じ。

#include <iostream>
using namespace std;

long long M, K;
int main() {
    long long M, K;
    cin >> M >> K;
    long long wa = 0;
    long long seki = 1;
    int res = 0;
    while (wa < M) ++res, wa += seki*K, seki *= K*2+1;
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

KUPC 2019 C - てんびんばかり

問題概要

制約

考えたこと

今回の問題