Steps(2)

規則性を見つけよう(続き)

ポイントは解の値が増えるタイミング。

左に入力値の差(=n)、右に出力値(=x)を書き並べると

　 n　　　x

• • • • • • • -

　 0　　　0
　 1　　　1
　 2　　　2
　 3　　　3
　 4　　　3
　 5　　　4
　 6　　　4
　 7　　　5
　 8　　　5
　 9　　　5
　10　　　6
　11　　　6
　12　　　6
　13　　　7
　14　　　7
　15　　　7
　　.
　　.
　　.

となり、xが増えるタイミングは、n=1,2,3,5,7,10,13...
これを奇数番目(=n1)・偶数番目(=n2)で分けて書くと

n1 = 1, 3, 7, 13...
n2 = 2, 5, 10,...

という数列で表すことができる。それぞれを一般項で表すと、

n1 = k*k-k+1
n2 = k*k+1

であるから、これらの式にk=1,2,3...と代入していきnを超えない間はカウントを増やすコードを書けば良いことになる。

main(n,i,m){

  for(gets(m);~scanf("%d%d",&m,&n);printf("%d\n",m))

    for(n-=m,i=m=0;++i*i-i<n;m++)m+=i*i<n;

}

当初はこれを短縮してもkurimuraさんの95バイト(http://d.hatena.ne.jp/kurimura/20060217/1140172753)には及ばないかなあと思っていたが、よくよく考えてみるとこの計算方法であればk*kが出てくるので、forを使わずにsqrtで計算できる。実際に、hinoeさんがsqrtを使って94バイトコードを書いてくれたので、私はそこにちょちょっと手を加えることで92バイトコードをSubmitすることに成功したのだ。

つづく