ABC056 C - Go Home

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

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

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

lcm = lambda x, y: (x * y) // math.gcd(x, y)

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


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

    N = ii()
    dist = 0

    for i in range(1, N + 1):
        dist += i
        if dist >= N:
            print(i)
            exit()


if __name__ == '__main__':
    main()

考え方

仮に、全ての時刻においてカンガルーがジャンプした場合、
数直線上の移動する座標は以下のようになる。
0 -> 1(0+1) -> 3(0+1+2) -> 6(0+1+2+3) -> 10(0+1+2+3+4) -> 15(0+1+2+3+4+5) -> 21(0+1+2+3+4+5+6) -> 28(0+1+2+3+4+5+6+7) ...

このことから、カンガルーの移動する座標は等差数列の和であることがわかる。
等差数列の和(D)がNを上回ったとき、
和とNを等しくするためには、D - N回目のジャンプを省くことで、
ちょうどNの位置に到達することができる。
（D >= Nのとき、必ずちょうどNに到達可能）
そのため、等差数列の和を求め、D >= Nとなった時点が答え。