TopCoderOpen 2019 Round2A : Easy RulerMaker

地味に難しくないですかこれ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15472

問題

正整数nが与えられるので、以下の条件を満たす整数集合Sを1つ構築せよ。

• Sのうち2要素を選んでその差を取って作成した集合をGとすると、Gには1～ceil(n*n/4)の値が最低1個ずつ含まれる。

解法

上限がO(n^2)であることから、平方分割に頭が至るとよい。
階差数列を取ったときに(1,1,1,1,...,√n,√n,√n,√n)と、1と√nがn/2個ぐらいずつ並ぶようにするとよい。

class RulerMaker {
	public:
	vector <int> placeStickers(int n) {
		vector<int> V;
		V.push_back(1);
		int i;
		if(n%2==0) {
			FOR(i,n/2-1) V.push_back(V.back()+1);
			FOR(i,n/2) V.push_back(V.back()+n/2);
		}
		else {
			FOR(i,n/2) V.push_back(V.back()+1);
			FOR(i,n/2) V.push_back(V.back()+n/2+1);
		}
		return V;
	}
}

まとめ

さっと出てこなかったし、本番のスコアみるに皆わりと苦戦したみたい？