ARC109 B - log

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()

    l, r = 0, N+1
    while l < r - 1:
        m = (l + r) // 2
        q = ((m + 1) * m) // 2

        if N+1 >= q:
            l = m
        else:
            r = m
    print(N+1-l)


if __name__ == '__main__':
    main()

考え方

必要な丸太は長さ1からnまでのn種類（n本）です。
また、お店には1からn+1までの長さn+1種類（n+1本）が売っています。

最悪のケースとして、長さ1からnまでのn種類（n本）を購入する必要があります。
ここから購入する本数を減らす戦略を考えます。

お店で売っている最も長い、長さがn+1の丸太を利用して他の丸太を作る戦略を考えると、
小さい順に作っていくのが、最も効率がよさそうと考えます。
つまり、長さn+1の丸太から、1 + 2 + ... + k <= n + 1となるk本の丸太を作ります。

1 + 2 + ... + k <= n + 1となるときの、1 + 2 + ... + kの合計は、和の公式によって求めることが出来ます。
あとは二分探索でkを探索し、和の公式の結果がn+1以下となるkを求めることで回答できます。