yukicoder No.71 そろばん 解説

問題文

解説

まず、仮に上の珠の数を $u$ 、下の珠の数を $d$ とする。
下の位は $0,1,2,...,d-1,d$ が表せる。
上の位は $0,(d+1),2(d+1),...,(u-1)(d+1),u(d+1)$ を表せる。
つまり、表せる数の最大値は $u(d+1)+d$ となる。
続いて、珠の合計数が $N$ だと $u+d=N$ という式が成り立つ。 $N<=10^6$ なので、ありえる $u$ と $d$ の組み合わせを全探索しても今回は間に合う。
実行時間は$O(N)$。
$N$ が大きいとオーバーフローするのでlong long型を使うこと。

C++での解答例

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
  ll n,ans=0;cin>>n;
  for(ll u=1;u<n;u++){
    ll d=n-u;
    ans=max(ans,u*(d+1)+d);
  }
  cout<<ans<<endl;
}