AtCoderログ：0123 - ABC 153 D

---

問題

問題文

カラカルはモンスターと戦っています。
モンスターの体力は $H$ です。
カラカルはモンスターを $1$ 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。
・モンスターの体力が $1$ なら、そのモンスターの体力は $0$ になる
・モンスターの体力が $X>1$ なら、そのモンスターは消滅し、体力が $\lfloor X/2 \rfloor$ のモンスターが新たに $2$ 体現れる
（$\lfloor r \rfloor$ は $r$ を超えない最大の整数を表す）
全てのモンスターの体力を $0$ 以下にすればカラカルの勝ちです。
カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を求めてください。

制約

・$1 \le H \le 10^{12}$
・入力中のすべての値は整数である。

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#026]

回答

回答1 (AC)

体力 $X~(>1)$ のモンスターを攻撃すると、体力が $\lfloor X/2 \rfloor$ のモンスターが 2 体に変わります。ここで $\lfloor X/2 \rfloor$ が $X$ に比べてちょうど $1$ ビット小さい値であることに注意すると、$X$ が $d$ ビットであるとき、体力 $d$ ビットのモンスター $1$ 体が体力 $d-1$ ビットのモンスター $2$ 体に変わったと言い換えることが出来ます。同様に考えると、これらのモンスターは体力 $d-2$ ビットのモンスター $2^2=4$ 体に、体力 $d-3$ ビットのモンスター $2^3=8$ 体に、...、体力 $1$ ビットのモンスター $2^{d-1}$ 体に変わります。よって攻撃回数は $1+2+\ldots+2^{d-1}=2^d-1$ 回となることがわかります。コードは以下のようになりました。$H$ の最大値は $10^{12}$ なので、long long 型の変数が必要になることに注意が必要です。

abc153d-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t h;
  cin >> h;

  int d = floor(log2(h))+1;
  
  cout << (int64_t)pow(2,d)-1 << endl;
}

なお設問では攻撃に必要な回数の最小値を問われていますが、攻撃手順はいろいろ考えられるものの、攻撃回数は一定になっています。

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

漸化式を用いた解法でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0122 - ABC 150 C