Preliminaries Problem: "maximum repeated substring problem"
Write a program which maximizes the total length of repeated substrings for given
string.
for 111001110011100111001001, answer is 11100,11100,11100,11100.
for 001011000000101100001011001011, answer is 0010110000,0010110000.
Finals Problem: "Sport scheduling"
Write a program which decides the home-away allocation(ref. fig3)
for all-teams' league tournament, minimizing the total cost of whole teams transportations
given a cost matrix(ref. fig2).
| 1 2 3 4 5 6 | A B C D
-+------------------ --+----------------
A| C D B D B C A| 0 15 15 10
B| D C A C A D B| 5 0 21 8
C| A B D B D A C| 15 21 0 12
D| B A C A C B D| 10 8 12 0
(team A fights team C on 1st day) (transportation cost between team A and B is 15)
fig1. Time Table fig2. cost matrix
| 1 2 3 4 5 6
-+-------------------------
A| +C +D -B -D +B -C
B| -D +C +A -C -A +D
C| -A -B +D +B -D +A
D| +B -A -C +A +C -B
+: home, -: away
fig3. home-away allocation
According to the above allocation, the total cost of team A is
5(day2day3)+8(day3day4)+10(day4day5)+15(day5day6)+15(day6home)=53.
Results:
total cost is 21840 with 33.9seconds
cost matrix data of the final
| A B C D E F G H
-+-------------------------------
A| 0 13 27 556 440 246 207 204
B| 13 0 35 567 452 259 220 216
C| 27 35 0 571 419 264 187 222
D| 556 567 571 0 129 859 388 747
E| 440 452 419 129 0 651 258 628
F| 246 259 264 859 651 0 438 42
G| 207 220 187 388 258 438 0 396
H| 204 216 222 747 628 42 396 0
Winner
team Lunatic
(Senior High School at Otsuka, University of Tsukuba)
|
