東京大学 情報理工学系研究科 創造情報学専攻 2019年8月実施 筆記試験 第1問
Author
Description
点列
まずは、凸
(1)
(2)
(3) 任意の
C[2] = 1; C[3] = 1;
for(i=4...n)
C[i] = 0;
for(i=4...n)
for(j=0...i-3)
[ ① ]
return C[n];
次に、凸
(4) 与えられた凸

(5) 上記 (4) で得られた関係式を用いて、任意の凸
Kai
(1)
C[4]=2
, C[3]=1
, C[2]=1
C[5]=5

C[6]=14

C[7]=42

(2)
Based on the representation we can see that:
(3)
To complete the code we must add:
C[i] = C[i] + C[j+2]*C[i-j-1]
This will allow the sum to equal the equation found in (2).
(4)
Based on the assumptions:
Basically, we choose an arbitrary triangle
(5)
The following cose assumes (based on no. 4) that
minimum_cost = +infinity
for (i=1...n-2)
local_cost = E[0,i+1]+E[i+1,n-i+1]+D(0,i)+D(i,i+1)+D(i+1,i)
minimal_cost = min(local_cost, minimal_cost)
return minimal_cost
In this code we go over all possible divisions of the shape n-gon into 2 subshapes and compute the minimum for these with the addition of the dividing edge. This uses the formula acquired in (4).
The time complexity for this, assuming that the information is known as stated in (4) is