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;
}