TopCoder SRM 802 : Div1 Hard QuadraticJumping

これも予想はついても自信をもって出すの厳しそう。
https://community.topcoder.com/stat?c=problem_statement&pm=16832&rd=18537

問題

1次元の無限に続く数直線を考える。
今原点にコマが置いてあり、i回目の移動ではi^2だけ左右どちらかに移動できる。
正整数Nが与えられる。Nでちょうど停止するようなiが存在すれば、その最小値を求めよ。

解法

まず、数手の移動で座標0,1,2,3に停止できる。
そこから、右左左右と移動すると常に4だけ移動できるので、どの点も十分大きな処理回数があれば到達可能である。

あとは、到達可能な最小値を求める。
移動回数kを1からインクリメントしてみよう。
1^2～k^2の和であるS=k*(k+1)*(2k+1)/6として、以下を満たさなければならない。

• SはN以上
• Sの偶奇はNと一致する
• Sの余剰分の半分、すなわち、(S-N)/2だけちょうど左に移動できればよい。

上二つは容易に確認できる。
3つ目だが、異なる平方数の和で(S-N)/2を表現できるか？という問題になる。
これはある程度大きい(S-N)/2だと常時成り立つ。小さいケースだけDPで総当たりして確認しておこう。

int ok[10101];

class QuadraticJumping {
	public:
	long long jump(long long goal) {
		
		ZERO(ok);
		ok[0]=1;
		int i,j;
		for(i=1;i<=100;i++) {
			for(j=10000-i*i;j>=0;j--) ok[j+i*i]|=ok[j];
		}
		
		for(i=1;i<=10000000;i++) {
			ll sum=1LL*i*(i+1)*(2*i+1)/6;
			
			if(sum>=goal&&(sum-goal)%2==0) {
				ll dif=(sum-goal)/2;
				if(dif>=10000||ok[dif]) return i;
			}
		}
		return 0;
		
	}
}

まとめ

「これはある程度大きい(S-N)/2だと常時成り立つ」に確証持つのしんどくない？