yukicoder No.72 そろばん Med

問題

問題概要

そろばんの一列でいくつ数得られる? 下の制約強化版

mmxsrup.hatenablog.com

解法

そろばんの上の玉がy、下がxとすると、数得られる数は、
(x + 1)y + x　-(1)　という式で表されて、 条件から、 x + y = n -(2)　という式も導かれるので、 yを消去すると求める答えは、下の式が最大となる時である。 (x + 1)(n - x) + x = -x² + xn + n
最大をxに対して全探索していると、TLEとなるので、 これを平方完成して、-(x - n / 2) + n² / 4 + n
となり、最大となるのはx = n / 2となる。ただし、xは整数しか取れないので、その周りを調べれば良いということになる。

ミス

特になし

コード

n = input()
mod = 1000007
x1 = n / 2
x2 = n / 2 + 1
ans = 0
ans = max(ans, -(x1 * x1) + (x1 * n) + n)
ans = max(ans, -(x2 * x2) + (x2 * n) + n)
print ans % mod