CODE FESTIVAL 2016 Final B – Exactly N points をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
CODE FESTIVAL 2016 Final B – Exactly N points

すわ部分和問題か?と思わせておいて、解いてみると意外と単純な構造だったな……といった感じの問題ではある。

# CODE FESTIVAL 2016 Final B - Exactly N points
# https://atcoder.jp/contests/cf16-final/tasks/codefestival_2016_final_b
# tag: 最小の最大値 二分探索 考察 高橋君

# 解いた問題の最大点が X 点の時、何点まで取れるかを
# 考えてみる。当然、その最大値は 1 ~ X 点の問題を
# 全て解いたもの、つまり (1 + X) * X // 2 点になる。

# 逆に、X 点の問題を入れた組み合わせなら、
# 適当な問題を一つ外すことで (1 + X) * X // 2 点までの
# 好きな組み合わせを作ることが可能。

# 念の為に具体例:
# 求めた最小の最大点数が 5 だとすると、
# (1, 2, 3, 4, 5) の問題セットになるが、
# これから 1, 2, 3, 4 のどれか一つを外し、
# 11 ~ 15 点の好きな点数を作成できる。
# また、10 点以下の場合は最小の最大点数は
# 4 以下になるので考慮しなくていい。

def main():
N = int(input())

# まず、最小の最大点数を求めるが、
# せっかくなので二分探索する
left = 0
right = N
while right - left > 1:
mid = (right + left) // 2
if (1 + mid) * mid // 2 >= N:
right = mid
else:
left = mid

max_point = right

# 引かなければならない点数を求める。
# これは、1 から順番に足していき、N を越えた時、
# つまり先ほど求めた最大点数まで足した時に、
# N を越えている分ということになる。
fault = (1 + max_point) * max_point // 2 - N

result = [n for n in range(1, max_point+1) if n != fault]

for r in result:
print(r)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です