こんにちは、こんばんは。現役茶色コーダーのRuteです。
今回は、ARC119のA問題「119 × 2^23 + 1」の解説を行います。
問題URL
概要：
整数$N$が与えられる。
$N = a×2^b + c$を満たす非負整数の組$(a,b,c)$における、$(a+b+c)$の最小値を出力せよ。
制約：
- $1 \leq N \leq 10^{18}$
- $N$ は整数
考え方
ステップ1:前提知識
まず、コンテスト本番でこれを考えていた方は少ないと思いますが、
前提として条件の式を満たす組は必ず$1$つ以上存在します。
理由として、$2^0 = 1$であることから、$(a,b,c) = (N,0,0)$の組が条件の式を見たすのは自明だからです。
このとき、$a+b+c$の値は$N$になります。
$(a,b,c) = (0,0,N)$の場合でも同様に$a+b+c = N$となります。
ステップ2:TLE解法
次に、これ以外の条件を満たす$(a,b,c)$の組を考えます。
$c$を全探索する、という考え方を行うと、最大でで$10^{18}+1$通りの$c$を考える必要があります。
コンピューターで$1$秒間に一度に計算できる回数は高速に動作する言語であっても$10^8$回程度なので、(ここの解釈は少々著者によって異なりますが)
実行時間制限の$2$秒以内には計算が終了せず、TLE(実行時間制限超過)となります。
また、$c$を全探索したところで、結局、$c = N -a × 2^b$という形になっていないと意味がなく、無駄な探索をしていることが分かります。
ステップ3:AC解法
では、ステップ2の解法から計算回数を少なくするためにはどうすればよいでしょうか。ここでは、指数関数的に増えている$2^b$に関して考えます。
以降$b$の値に対して、$a = \lfloor {N÷2^b} \rfloor ,c = N - a × 2^b$とします。
(今回の目的は$a+b+c$の最小化です。
このとき、$c$の値は、$N$から貪欲的に$2^b$を引いていったあまりにするのが今回の目的において適切です。)
例えば、$N = 998244353$の場合に、$b$の値を$0$から$1$ずつ動かして$(a,b,c) , a+b+c$を計算すると
[必読]$(a,b,c)$の値を動かした時のシミュレーション
$b = 0の場合:(a,b,c) = (998244353,0,0) , a+b+c = 998244353$
$b = 1の場合:(a,b,c) = (499122176,1,1) , a+b+c = 499122178$
$b = 2の場合:(a,b,c) = (249561088,2,1) , a+b+c = 249561091$
・
・
$b = 22の場合:(a,b,c) = (238,22,1), a+b+c = 261$
$b = 23の場合:(a,b,c) = (119,23,1), a+b+c = 143$
$b = 24の場合:(a,b,c) = (59,24,8388609), a+b+c = 8388692$
$b = 25の場合:(a,b,c) = (29,25,25165825), a+b+c = 25165879$
$b = 26の場合:(a,b,c) = (14,26,58720257), a+b+c = 58720297$
・
・
と続きます。
$2^b$は指数的に増加するので、いつかは$N$以上になることも考えられ、その場合は
$b = 29の場合:(a,b,c) = (1,29,461373441) , a+b+c = 461373471$
$b = 30の場合:(a,b,c) = (0,30,998244353) , a+b+c = 998244383$
$b = 31の場合:(a,b,c) = (0,31,998244353) , a+b+c = 998244384$
と、$a$の値が$0$になり、$N$を$2$で割った時のあまりの値が$b \geq 1$の場合に変わらないことから$a+b+c$が$b$の差分である$1$ずつ増えていくようになります。
また、制約に関連して、
$2^{59} = 576460752303423488 < 10^{18}$
$2^{60} = 1152921504606846976 > 10^{18}$
であることから、
$b=60$以降の$b$においては、$2^b>N$であることが確定するので、それ以上$b$を大きくしたところで、$a+b+c$の値は$N + b$であることが分かります。
これは、ステップ1より、最小値には絶対になりません。
したがって、ここまでで分かったこととしては
- 考える数の範囲から$c$よりも$b$に着目する
- $b$の探索範囲は$(0,60)$で良い
ということになります。
これらを元に、$b$について全探索を行うことにより、$60$回程度のループでこの問題を解くことが出来ます。これは明らかに$N \geq 61$の場合で計算回数が少なくなっており、$N$が大きくなればなるほど計算量削減の効果は絶大です。
Python3での解答例
N = int(input())
ans = 10 ** 18
#最小値なのでansを適当に大きくしておく
for B in range(0,61):
C = N
A = N // (2 ** B)
C -= A * (2 ** B)
if A + B + C < ans:
ans = A + B + C
print(ans)
類題紹介
この問題のように、「考える値の範囲を狭めることが出来るか」ということを考察することで簡単に解ける問題をいくつかご紹介します。
AtCoder Regulae Contest 106 A問題「106」
AtCoder Regular Contest 108 A問題「Sum and Product」
AtCoder Beginner Contest 193 C問題「Unexpressed」
いずれも、点数は$300$点で、今回の問題と同じ点数です。この記事を読んだ後に、解いてみることをおすすめします。
以上で、ARC119のA問題「119 × 2^23 + 1」の解説を終了したいと思います。 (文章が若干拙いかもしれないです。公式解説の方が分かりやすいかも...)
この記事に関して質問等がある場合はコメントで教えて下さい。