Project Euler 18と67

C++ algorithm Project Euler

　三角形の行列を下にたどり，通った数字の最大値を求める．
ご丁寧に，問題18では行列が小さいからbrute forceでもいけるけど，
問題67は同じ問題だけど行列がでかいからキツイぜ，とか書いてある．


これは面白い．当然一般的な解法をここで考えて二つとも解くに限る．


　で，僕は動的計画法が得意なのでそれで解きました．


と言っても別に難しいことは無くて，例えば

01
02 03
04 05 06
07 08 09 10

という行列を考える．面倒なので問題のようにピラミッド型じゃなくて三角行列で．


上から初めて，あり得るパスの中で最大のものを保存してゆき，最終的に一番下に出てくるのが最大値候補群となる．


僕は説明が破滅的に苦手なので順を追ってみると

01
03 04
04 05 06
07 08 09 10

青の値を足したものが赤．
これは1番目の行から2番目の行まで行くルート候補の値になる．


次

01
03 04
06 08 09
07 08 09 10

青の値を赤に，緑の値を紫色に足した．
ただし，真ん中の水色の値は両方試して，大きいほうを選択する．
こうすると1番目の行から2番目の行まで行くルートの中で，値が大きいもののみが残る．


最終的に，

01
03 04
06 08 09
15 17 18 19

という行列が出来上がるので，一番下の行から最大のものを選ぶ．


というわけで,同時に2つ解きました．
コーディングは無意味なところにやたら凝ってしまい凄く時間が掛かってしまいました．

typedef unsigned long long uint64;
typedef uint64 natural ;


int index(int x, int y) // index of matrix. we don't use 0 as index
{
	if( x <= 0 || y <= 0 || y < x)
	{
		return -1;
	} else
	{
		return ((y * (y-1) / 2)) + x - 1;
	}
}

void createDPMatrix(vector<natural>& s, vector<natural>& d, int x, int y)
{
	natural source = d[index(x,y)];

	if((index(x,y+1) == -1) || (index(x+1,y+1) == -1)){ return; }
	if((index(x+1, y+1) > (int)d.size()-1) || index(x, y+1) > (int)d.size()-1){ return; }

	natural left = source + s[index(x, y+1)];
	natural right = source + s[index(x+1, y+1)];

	if(left > d[index(x,y+1)])
	{
		d[index(x,y+1)] = left;
		createDPMatrix(s, d, x, y+1);
	}

	if(right > d[index(x+1,y+1)])
	{
		d[index(x+1,y+1)] = right;
		createDPMatrix(s, d, x+1, y+1);
	}

}

natural f18()
{

	ifstream in("in.txt", ios::binary | ios::in);
	if(!in){ cout<<"Can't open file"<<endl; }

	vector<natural> inmat;
	natural buff;
	int x=0, y=1;
	natural max=0;

	while(in>> buff)
	{
		inmat.push_back(buff);

		if(y == x) { ++y; x=0;}
		else { ++x; }
	}

	
	vector<natural> dpmat(inmat.size(),0);
	dpmat[index(1,1)] = inmat[index(1,1)];

	createDPMatrix(inmat, dpmat, 1, 1);

	for(int i=1; i<=y; ++i)
	{
		if(dpmat[index(i, y)] > max)
		{
			max = dpmat[index(i, y)];
		}
	}

	return max;
}


Project Eulerにて初めて再帰使ったかも．ウソかも．
index()とか，別にいらないんですが，この方が考えやすいと思います．凄く無駄ですが．


三角行列みたいな可変長行列はC++とかだと作りにくくて，
フォーラム見ていると正方行列をそのまま三角行列として扱っている人がちらほらいましたが，これはindexによる擬似三角行列になってます．
偉そうに言いながら，vectorの力借りまくりですが．


あ，フォーラムで下からやっていく方法が．これは気づかなかった．


動的計画法自体の計算量は同じだけど，その方が最後に候補から選ぶ処理が無くなるので賢いですね．精進が足りん．