Project Euler 201

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

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

        // BitmapData使用版
        private function solve2(n : uint, k : uint) : Number
        {
        		var i : uint;
        		var sup : uint = n*(n+1)*(2*n+1)/6-(k-1)*k*(2*k-1)/6+1;
        		var nrow : uint = 1 + sup / 8191;
        		var bmd : BitmapData = new BitmapData(8191, nrow * (k+1), false, 0x000000);
        		bmd.lock();
        		bmd.setPixel(0, 0, 0x000001);
        		for(i = 0;i < n;i++){
        			var delta : uint = (i+1)*(i+1);
        			var dx : uint = delta % 8191;
        			var dy : uint = delta / 8191;
        			var mat1 : Matrix = new Matrix();
        			mat1.translate(dx, dy + nrow);
        			var mat2 : Matrix = new Matrix();
        			mat2.translate(dx - 8191, dy + nrow + 1);
        			
        			var dh : uint = nrow * Math.min(i+1, k+1);
        			var d : BitmapData = new BitmapData(8191, dh, false, 0x000000);
        			d.copyPixels(bmd, new Rectangle(0, 0, 8191, dh), new Point());
        			bmd.draw(d, mat1, null, BlendMode.ADD);
        			bmd.draw(d, mat2, null, BlendMode.ADD);
        			d.dispose();
        		}
        		bmd.unlock();
        		
        		var sum : Number = 0;
        		for(i = 0;i < sup;i++){
        			if(bmd.getPixel(i % 8191, uint(i / 8191) + nrow * k) == 1){
        				sum += i;
        			}
        		}
        		return sum;
        }
        
        // 愚直にDP版
        private function solve(n : uint, k : uint) : Number
        {
        		var i : uint, j : int;
        		var s : Number;
        		var key : String;
        		// counts[使っている要素数][値]=組み合わせ(2まで)
        		var counts : Array = [];
        		for(i = 0;i <= k;i++)counts.push({});
        		counts[0][0] = 1;
        		for(i = 0;i < n;i++){
        			var delta : int = (i+1)*(i+1);
        			// IDEA BitmapDataで一気に描画？
        			for(j = k - 1;j >= 0;j--){
        				for(key in counts[j]){
        					s = int(key) + delta;
        					counts[j+1][s] = (counts[j][key] == 2 || counts[j+1][s]) ? 2 : 1;
        				}
        			}
        		}
        		
        		var sum : Number = 0;
        		for(key in counts[k]){
//        			tr(key, counts[k][key]);
        			if(counts[k][key] == 1){
        				sum += int(key);
        			}
        		}
        		return sum;
        }

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