ARC119 A問題 解説 Point:考える値の範囲を狭める

こんにちは、こんばんは。現役茶色コーダーのRuteです。
今回は、ARC119のA問題「119 × 2^23 + 1」の解説を行います。
[問題URL](https://atcoder.jp/contests/arc119/tasks/arc119_a)
##概要：
整数$N$が与えられる。
$N = a×2^b + c$を満たす非負整数の組$(a,b,c)$における、$(a+b+c)$の最小値を出力せよ。
##制約：
- $1 \leq N \leq 10^{18}$
- $N$ は整数

## 考え方
###ステップ1:前提知識
まず、コンテスト本番でこれを考えていた方は少ないと思いますが、
前提として条件の式を満たす組は<b>必ず$1$つ以上</b>存在します。
理由として、$2^0 = 1$であることから、<font color="red">$(a,b,c) = (N,0,0)$</font>の組が条件の式を見たすのは自明だからです。
このとき、$a+b+c$の値は$N$になります。
<font color="gray">$(a,b,c) = (0,0,N)$の場合でも同様に$a+b+c = N$となります。</font>
###ステップ2:TLE解法
次に、これ以外の条件を満たす$(a,b,c)$の組を考えます。
$c$を全探索する、という考え方を行うと、最大でで$10^{18}+1$通りの$c$を考える必要があります。
コンピューターで$1$秒間に一度に計算できる回数は<b>高速に動作する言語であっても</b>$10^8$回程度なので、<font color="gray">(ここの解釈は少々著者によって異なりますが)</font><br>実行時間制限の$2$秒以内には計算が終了せず、<b>TLE(実行時間制限超過)となります。</b>
また、$c$を全探索したところで、結局、$c = N -a × 2^b$という形になっていないと意味がなく、<b>無駄な探索</b>をしていることが分かります。

###ステップ3:AC解法
では、[ステップ2](https://qiita.com/rute_not_route/items/4a64c03e63d4f404cf09#%E3%82%B9%E3%83%86%E3%83%83%E3%83%972tle%E8%A7%A3%E6%B3%95)の解法から計算回数を少なくするためにはどうすればよいでしょうか。ここでは、指数関数的に増えている<font color="red">$2^b$</b></font>に関して考えます。
以降$b$の値に対して、$a = \lfloor {N÷2^b} \rfloor ,c = N - a × 2^b$とします。
<font color="gray">(今回の目的は$a+b+c$の最小化です。
このとき、$c$の値は、$N$から貪欲的に$2^b$を引いていったあまりにするのが今回の目的において適切です。)</font>
例えば、$N = 998244353$の場合に、$b$の値を$0$から$1$ずつ動かして$(a,b,c) , a+b+c$を計算すると
<details><summary>[必読]$(a,b,c)$の値を動かした時のシミュレーション</summary>
$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$
・
・
</details>
と続きます。
$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$の場合に変わらないことから<b>$a+b+c$が$b$の差分である$1$ずつ増えていくようになります。</b>

また、制約に関連して、
$2^{59} = 576460752303423488  < 10^{18}$
$2^{60} = 1152921504606846976 > 10^{18}$

であることから、
$b=60$以降の$b$においては、$2^b>N$であることが確定するので、それ以上$b$を大きくしたところで、$a+b+c$の値は$N + b$であることが分かります。
これは、[ステップ1](https://qiita.com/rute_not_route/items/4a64c03e63d4f404cf09#%E3%82%B9%E3%83%86%E3%83%83%E3%83%971%E5%89%8D%E6%8F%90%E7%9F%A5%E8%AD%98)より、<b>最小値には絶対になりません。</b>

したがって、ここまでで分かったこととしては

- <b>考える数の範囲から$c$よりも$b$に着目する</b>
- <b>$b$の探索範囲は$(0,60)$で良い</b>


ということになります。

これらを元に、$b$について全探索を行うことにより、$60$回程度のループでこの問題を解くことが出来ます。これは明らかに$N \geq 61$の場合で計算回数が少なくなっており、<b><font color="red">$N$が大きくなればなるほど計算量削減の効果は絶大です。</font></b>


<details><summary>Python3での解答例</summary><div>

```{ARC119A.py}
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)
```

</div></details>

## 類題紹介
この問題のように、<font color="red"><b>「考える値の範囲を狭めることが出来るか」</b>ということを考察する</font>ことで簡単に解ける問題をいくつかご紹介します。

[AtCoder Regulae Contest 106 A問題「106」](https://atcoder.jp/contests/arc106/tasks/arc106_a)
[AtCoder Regular Contest 108 A問題「Sum and Product」](https://atcoder.jp/contests/arc108/tasks/arc108_a)
[AtCoder Beginner Contest 193 C問題「Unexpressed」](https://atcoder.jp/contests/abc193/tasks/abc193_c)

いずれも、点数は$300$点で、今回の問題と同じ点数です。この記事を読んだ後に、解いてみることをおすすめします。

以上で、<b>ARC119のA問題「119 × 2^23 + 1」の解説</b>を終了したいと思います。<font color="grey"> (文章が若干拙いかもしれないです。公式解説の方が分かりやすいかも...)</font>
この記事に関して質問等がある場合は<b>コメント</b>で教えて下さい。