Project Euler 286

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/9iJ8
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=286
    public class Euler286 extends Sprite {
        private var _tf : TextField;
  
        public function Euler286() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(50, 20, 0.02));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        // 確率をDPで求めながら二分探索
        private function solve(N : int, R : int, P : Number) : Number
        {
        		_N = N;
        		_R = R;
        		var start : Number = N;
        		var end : Number = N + 100;
        		var mid : Number = (start + end) >> 1;
        		while(end - start > 0.0000000001){ 
        			_cache = {};
        		
        			var val : Number = rec(mid, 1, R);
//        			tr(val);
        			if(val > P){
        				start = mid;
        			}else{
        				end = mid;
        			}
        			mid = (start + end) / 2;
        		}
        		return mid;
        }
        
        private var _N : uint;
        private var _cache : Object = {};
        private var _R : uint;
        
        private function rec(q : Number, pos : uint, rest : uint) : Number
        {
        		if(pos == _N + 1)return 1;
        		var code : uint = pos * (_R + 1) + rest;
        		if(_cache[code])return _cache[code];
        		var ret : Number = 0;
        		if(rest >= 1)ret += (1 - pos / q) * rec(q, pos + 1, rest - 1);
        		if(rest + pos <= _N)ret += pos / q * rec(q, pos + 1, rest);
        		_cache[code] = ret;
        		return ret;
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}