0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

カラカルはモンスターと戦っています。

モンスターの体力は H です。

カラカルはモンスターを 1 体選んで攻撃することができます。モンスターを攻撃したとき、攻撃対象のモンスターの体力に応じて、次のどちらかが起こります。

モンスターの体力が 1 なら、そのモンスターの体力は 0 になる
モンスターの体力が X>1 なら、そのモンスターは消滅し、体力が ⌊ X / 2 ⌋ のモンスターが新たに 2 体現れる（ ⌊ r ⌋ は r を超えない最大の整数を表す）

全てのモンスターの体力を 0 以下にすればカラカルの勝ちです。

カラカルがモンスターに勝つまでに行う攻撃の回数の最小値を求めてください。

2.制約

1 ≤ H ≤ 10¹²
入力中のすべての値は整数である。

3.入力例

入力

1000000000000

出力

1099511627775

4.初見の感想

体力が２以上ある敵をすべて分裂させ体力１にした後、全部倒していく戦略をとることになる
体力1になるまでループなのでwhile文で回す
今何体いるかをnumで数えときます
num体全員に魔法を打つのでその回数を変数ansでcountします

5.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        long H = long.Parse(Console.ReadLine());
        long num = 1;
        long ans = 0;
        while (H >= 2)
        {
            H = H / 2;
           //分裂する前に魔法をうつ回数を数える
            ans+=num;
           //２倍にモンスター数が分裂
            num *= 2;
        }
        //体力1の軍団を倒す魔法の回数を計測
        ans += num;
        Console.WriteLine(ans);
    }
}

6.最後に

本番中は意外と手間取ったんですが、この問題灰パフォなんですね…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 153 D - Caracal vs Monster