Project Euler 219

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

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

		// 0,1文字列の集合Aで、Aの要素は他のどの要素の接頭辞にもならないとする。
		// #A=10^9のとき、
		// f(x)=(x内の0の個数)+ 4*(x内の1の個数)として、
		// f(A)=Σ_[x∈A] f(x) の最小値を求めよ。
		// 
		// まず、0,1を2分木にしたとき、根からどう辿ってもかならずAの要素にブチ当たることを示す。
		// ぶち当たらないと仮定すると、その経路の途中のノードで、兄弟がAの要素となるものが必ず存在する。
		// この要素を親に置換すると、条件を満たしたまま、f(A)の値は依り小さくなるので最小性に反する。よって(ry
		//
		// つまり、根からはじめて親を子に分解する作業を繰り返すだけでf(A)の最小値が求められる。
		// 親pを子に分解すると、Aの要素数は1増え、f(A)はf(p)+5だけ増えることに注意すればOK.
		// f(p)の小さい順に分解していけばよい。
		private function solve(N : uint) : Number
        {
        		var i : uint;
        		
        		var fs : Array = new Array(1000);
        		for(i = 0;i < fs.length;i++)fs[i] = 0;
        		fs[0] = 1;
        		
        		var a : uint = 1;
        		var b : Number = 0;
        		for(var p : uint = 0;;p++){
        			if(fs[p] > 0){
        				var c : uint = a + fs[p] >= N ? N - a : fs[p];
        				a += c;
        				b += c * (p + 5);
        				if(a == N)break;
        				
        				fs[p + 1] += c;
        				fs[p + 4] += c;
        			}
        		}
        		
        		return b;
        }

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