趣味悠遊自適生活DAY2: Problem 18

2012年3月17日土曜日

Problem 18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

つーか、正攻法でいかないとしんどいっしょｗ

全部列挙とか逆にめんどくさい。

$a_1_1\\ a_2_1\ a_2_2\\ \dots\\ a_n_1\ a_n_2\dots\ a_n_n$

n=2に於いて

$a_1_1\\ a_2_1\ a_2_2$

ここで最大になるのはa21>a22の時、a11-a21のときである

n=k+1に於いて

$a_1_1\\ a_2_1\ a_2_2\\ \dots\\ a_{k+1,}_1\ a_{k+1,}_2\dots a_{k+1,}_{k+1}$

この場合

$a_k_1\\ a_{k+1,}_1\ a_{k+1,}_2$

ak+1,1>ak+1,2の場合

ak1-ak+1,1が最大になりうる

これは他の

$a_k_m\\ a_{k+1,}_m\ a_{k+1,}_{m+1}$

にも同じことが言える

今、

$a_{k+1,}_m\geq a_{k+1,}_{m+1}$

の時

$a_{k+1,}_m+a_k_m=s_k_m$

なるsを定義する

$a_{k-1,}_m\\ s_k_m\ s_k_{m+1}$

においても同様にsを定義していく

この時、s11はa11からakxまで、最大の経路をとったことになるので最大になる

故にn=2,n=k+1において、s11が最大の経路をとった時の値と示されたので

数学的帰納法より、

$a_1_1\\ a_2_1\ a_2_2\\ \dots\\ a_n_1\ a_n_2\dots\ a_n_n$

の場合、s11が常に最大の経路をとった時の和になることが証明された？

うまい説明ができないけどこんな感じだろうね

つまりはこのs11を求めていくようにプログラムを組んでいきます。

        static void Main(string[] args)
{
string text = "";
if(args.Length == 1)
{
try
{
using (StreamReader sr = new StreamReader(
args[0], Encoding.GetEncoding("Shift_JIS")))
{

text = sr.ReadToEnd();
}
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}

int lineCount = text.ToList().Where(c => c.Equals('\n')).Count() + 1;

int[,] a = new int[lineCount,lineCount];

using (StreamReader sr = new StreamReader(
args[0], Encoding.GetEncoding("Shift_JIS")))
{

for(int i = 0; (text = sr.ReadLine()) != null; ++i)
{
for (int j = 0; j <= i; ++j)
{
a[i,j] = int.Parse(text.Substring(j*3,2));
}
}
}


for (int i = lineCount - 1; i >= 1; --i)
{
for (int j = 0; j < lineCount-2; ++j)
{
if (a[i, j] >= a[i, j + 1])
{
a[i - 1, j] += a[i, j];
}
else
{
a[i - 1, j] += a[i, j+1];
}
}
}

Console.WriteLine(a[0, 0]);
}
}

これできちんと正答出来ましたので、problem67もおまけで解きました。

趣味悠遊自適生活DAY2

2012年3月17日土曜日

Problem 18

0 件のコメント:

コメントを投稿