くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 153 D - Caracal vs Monster

Python3で解く AtCoder Beginner Contest 153 D - Caracal vs Monster

AtCoder 競プロ ABC ABC-D パターン発見

愚直に、1~hまでどんな風になるかをリストで残そうとすると、TLEになる様な制約なので、いい感じのパターンを見つける必要がある。
どんな人数になるかがちょっとよくわからないので、とりあえず書き出す。そうするとパターンが見えてくる。

目次

概要

問題

  1. モンスターが1体いて体力は{\displaystyle h}。
  2. モンスターを攻撃する。
  3. その時にモンスターの体力が {\displaystyle 1}なら倒せる。
  4. その時にモンスターの体力が {\displaystyle 1}より大きい時は、体力が半分（切り下げ）になって、２体になる。
  5. 攻撃回数の最小となるような攻撃回数は？

解くときに考えた内容

  • サンプルをみると、1, 3, 3, 7となっている。
  • DPっぽくやるのかなとおもったけどモンスターの体力の制約が {\displaystyle h \leqq 10^{12}}なので、無理そう。
  • モンスターの体力が {\displaystyle h}が1, 3, 7, 15の時は攻撃回数も1, 3, 7, 15。 モンスターの体力が {\displaystyle h}が1, 2, 4, 8の時は攻撃回数も1, 3, 7, 15。 つまり、hが{\displaystyle 2 ^ i \leq h \leq 2 ^{i+1}-1}の範囲であれば、必要な攻撃回数は{\displaystyle 2 ^{i+1}-1}ということになる。 (画像に番目って書いてあるけどhの値だったな。。。)
    f:id:black_tank_top:20200723082157j:plain
    hが2i~2i-1のモンスターを倒すのに必要な攻撃数のイメージ
  • なので、{\displaystyle 2 ^ i \leqq h}まで調べれば良いので{\displaystyle O(logN)}

コード

h = int(input())
ans = 1
if h >= 1:
    i = 0
    while 2**i <= h:
        ans = 2**(i+1) - 1
        i += 1
print(ans)

参考になる書籍

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

７章までは別記事に残してある。 blacktanktop.hatenablog.com