Python3で解く AtCoder Regular Contest 109 B - log

長さ $n+1$ の丸太を買って、短い方から丸太を作れるだけ作って、残りは買う。 $n$ -（作れるだけ作った数）+ 1が答え。作れるだけ作った数をどうかんがえるかがポイント

概要

長さ $1$ から $n$ の $n$ 種類の丸太がほしい。
長さ $1$ から $n+1$ が各 $1$ ずつ、各1円で売ってる。
自由に切ってよい。例えば長さ $5$ の丸太を長さ $2$ と長さ $3$ としていい。
余ったものは捨ててよい。
このとき、 $n$ が与えられたときに、長さ $1$ から $n$ の $n$ 種類の丸太を用意する最小の金額は？

解くときに考えた内容

長さ $n+1$ の丸太を買って、短い方から丸太を作れるだけ作って、残りは買う方針でいく。これが最小なのは自明ではないが、証明はしない。
$n+1$ から作れるだけ作るときに長さ $1, 2, ... k$ の $k$ の最大値を求める必要がある。
$1, 1+2, 1+2+3, ... 1+2+3+..+k$ のような数列と $n+1$ を比較して、最大の $k$ を求めたい。
等差数列の和の数列なので、 $\frac{k(k+1)}{2}$ のリストを制約分作ってもいいけど、作ると終わらない。
bisectはリストが無いとできないので、ここでは使えない。
ここでは、リストがない状態での二分探索を行う必要がある。（これまで、なぜわざわざこのような実装しているのかわからないときがあったが、このような状況のときに有効ということがわかった。）

普通の二分探索の実装で、 $n+1$ とmidの値と比較するべきところを $n+1$ と等差数列の和として $\frac{mid(mid+1)}{2}$ を比較するようにして、探索していくようにする。

コード

def log_cut(n):
    l = 0
    r = n
    while r - l > 1:
        mid = (l+r) // 2
        # ここの比較がポイント
        # リストも与える二分探索だとlist[mid]とn+1を比較するが
        # 今回はリストではなく、mid自体の値を使って、等差数列の和と比較する。
        if mid * (mid+1) // 2 <= (n+1):
            l = mid
        else:
            r = mid 
    return l
    n = int(input())
# これが作れる分のkの最大値
max_log = log_cut(n)
# n - max_log（買う分）+ （1, 2, ... , kは１本）
ans = n - max_log + 1
print(ans)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

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

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