AtCoder K2PC Hard C お気に入りの数2

http://k2pc-hard.contest.atcoder.jp/tasks/k2pc001_h3

回答

greedyに、大きい数のsqrtの道を辿ってく。
nが平方数じゃないなら-1、n<=2なら0

コメント

今見ると不要な場合分けがあるようだ。
この問題のwriterいわく、違う方法(根本的な解き方は同じように見えるが)の比較的複雑なものがwriter解のようだ。
https://twitter.com/kyuridenamida/status/236458452313063424

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#ifdef _MSC_VER
#define aut(v, x) auto v = x
#else
#define aut(v, x) __typeof(x) v = (x)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
 
int main() {
	ll n;
	ll r = 0;
	vector<ll>v;
	scanf("%lld",&n);
	if(n<=2){r = 0;}
	else if(n==4){r = 3;}
	else if(n<=8){r = -1;}
	else {
	ll i;
	for(i = 2; i*i <= n; i ++) {
		v.pb(i*i);
	}
	if((i-1)*(i-1)!=n) r = -1;
	else {
	r = 0;
	ll c = 2;
	for(i = v.size()-1; i >= 0; -- i) {
		r += (v[i] - c) + 1;
		c = i+2;
	}
	}
	}
	cout << r << endl;
	return 0;
}