円周率チャレンジ
平方根を取る or 2を足すを繰り返してπ=3.1415...に近い値を生成してくださいというゲームです。上位はスコアinfがでていますが、これはdouble型の最大値を超えてしまったためのようです。
戦略としてはTwitterでも一部言われていますが半分全列挙という手法を使うのが良いのかなと思います。最短手数がランキングからわかっているのでそれをnとおくと、x=0 から始めて2を足す or 平方根を取る という操作をn/2回繰り返した状態を生成します。次にx=πから始めて2を引く or 二乗する という逆操作をn/2繰り返した状態を生成します。そして、両者をつなげて最適解を探索します。ただし、両者の状態はdouble型のため実際には完全には一致しません。そのため、二分探索やしゃくとりなどの方法により最も近いところかその次辺りまでを試して最適なものを発見します。
計算量はO(2^(n/2))であり、n=53 ということがわかっているので、空間計算量、処理計算量ともにO(1億)といったところです。競技プログラミングの一般的な制限2秒 1024MB では計算は難しいですが、制限時間等があるわけではないので効率的なコードがかければ無理ではない範囲かと思います。
※ネタバレはどうかなとは思うのですが、ネット上ではすでにこのぐらいのネタが書いてある かつ コードを載せているわけではないのでまぁいいかなと。
