読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

yukicoder No.72 - そろばん Med

問題

No.72 そろばん Med - yukicoder

イデア

上部にx個、下部にy個の珠を配置する時に、作ることの出来る状態の種類が(x+1)(y+1)なので、0始まりであることを想定すれば作ることの出来る最大の数は(x+1)(y+1)-1 = xy+x+y=x(y+1)+yとなる。x+y=nも考慮して変数をyのみにすると、(n-y)(y+1)+y=-(y-\frac{n}{2})^2+\frac{n^2}{4}+nと平方完成できるので、\frac{n}{2}が整数であるときはy=\frac{n}{2}の時が最大値を取り、整数でない時は最も近い値y=\frac{n+1}{2}y=\frac{n-1}{2}のときになる。このようにダイレクトに最適解を求められる。また、今回制約が大きいのでPythonを使った。そこで、初歩的なミスをしてしまっていたので、メモしておく。Pythonの割り算をC的に使おうとすると、普通の割り算記号/では小数点を切り捨てず、浮動小数点型で返ってくる。これがどうやらバグの原因になっていたらしい。ということでこのような場合に使うべきなのが小数点以下を切り捨てる割り算//であり、それを使うことで今回はACとなった。Pythonは今年に入ってから勉強し始めたのでまだまだ覚えるべきことが多い...

実装(Python3)

n = int(input())
y = n//2
ans = (n-y)*(y+1)+y
print(ans%1000007)