MM59 BookSelection

プログラミングしたくなったので参加してしまいました。TCO前にレートを上げておきたいというのもありましたけどね。いつのものことながら、最終結果が出るまでは1，2週間かかるはずなので、気長に待ちたいと思います。
暫定30位。

今回の方針

本の高さでソートして、i番目からj番目の間の幅あたりの価値が高い順に詰め込んで1段分作る。各ブロックの使う本の範囲が重ならないものについて順序を考えてDAGを作り、DPで価値の和を最大化する。

あとはちょこちょこ逐次処理でオーダーを下げたり、打ち切って定数倍高速化したり、微調整して隙間を埋めたりしました。

感想

本棚が小さかったり、本の数が少ないときは数ミリ秒で終わってしまうので、1段分作るときに貪欲にするだけでなく、DPで厳密に求める方法も入れておけばよかったかと思います。あと、xが定数だと思って、途中まで本の断面積に価値が比例すると思ってしまったのはひどかったと思います。その他、点数差が僅差で結構適当な方法でもそれなりのスコアになってしまうので、TLEで0点を出してしまうのが怖いです。もしかして、Cで書いて高速化した方がよかった?

以下最終バージョンによる出力。（時間は自宅のポンコツによる）

1 : total height = 426, value = 3145, loss = 505, time = 250
2 : total height = 1074, value = 3470, loss = 220, time = 218
3 : total height = 1082, value = 8082, loss = 4227, time = 1562
4 : total height = 262, value = 1819, loss = 1405, time = 141
5 : total height = 458, value = 2251, loss = 340, time = 78
6 : total height = 1011, value = 2604, loss = 37, time = 172
7 : total height = 397, value = 2283, loss = 563, time = 93
8 : total height = 474, value = 2835, loss = 769, time = 157
9 : total height = 333, value = 1442, loss = 635, time = 15
10 : total height = 869, value = 4189, loss = 109, time = 437
11 : total height = 1153, value = 8729, loss = 6585, time = 1500
12 : total height = 625, value = 4037, loss = 1576, time = 375
13 : total height = 1091, value = 7997, loss = 2951, time = 1703
14 : total height = 330, value = 2227, loss = 1099, time = 110
15 : total height = 1172, value = 5352, loss = 2277, time = 703
16 : total height = 1055, value = 4158, loss = 150, time = 312
17 : total height = 553, value = 2883, loss = 1322, time = 157
18 : total height = 988, value = 6380, loss = 124, time = 797
19 : total height = 1005, value = 8688, loss = 5055, time = 1375
20 : total height = 1086, value = 9798, loss = 7178, time = 2031
21 : total height = 633, value = 2601, loss = 1675, time = 172
22 : total height = 597, value = 5908, loss = 5142, time = 1343
23 : total height = 626, value = 5373, loss = 1205, time = 485
24 : total height = 950, value = 6334, loss = 240, time = 734
25 : total height = 346, value = 1613, loss = 1132, time = 78
26 : total height = 583, value = 5484, loss = 2657, time = 828
27 : total height = 244, value = 1343, loss = 772, time = 16
28 : total height = 387, value = 2604, loss = 754, time = 94
29 : total height = 716, value = 2530, loss = 427, time = 109
30 : total height = 494, value = 3344, loss = 2820, time = 328
31 : total height = 1061, value = 6107, loss = 3514, time = 922
32 : total height = 270, value = 1453, loss = 848, time = 32
33 : total height = 219, value = 1443, loss = 541, time = 31
34 : total height = 961, value = 8526, loss = 3861, time = 1625
35 : total height = 460, value = 3052, loss = 1540, time = 219
36 : total height = 1095, value = 6548, loss = 5024, time = 1172
37 : total height = 455, value = 3780, loss = 1437, time = 344
38 : total height = 678, value = 5637, loss = 2587, time = 953
39 : total height = 758, value = 8122, loss = 5862, time = 1375
40 : total height = 503, value = 3949, loss = 1071, time = 312
41 : total height = 597, value = 4830, loss = 3241, time = 656
42 : total height = 551, value = 2762, loss = 1561, time = 172
43 : total height = 592, value = 2852, loss = 453, time = 141
44 : total height = 712, value = 5570, loss = 4183, time = 1109
45 : total height = 819, value = 5285, loss = 736, time = 531
46 : total height = 307, value = 2187, loss = 2039, time = 141
47 : total height = 389, value = 1638, loss = 728, time = 47
48 : total height = 292, value = 923, loss = 45, time = 16
49 : total height = 521, value = 3681, loss = 630, time = 281
50 : total height = 972, value = 7477, loss = 2072, time = 1094
51 : total height = 996, value = 9977, loss = 4018, time = 1891
52 : total height = 460, value = 2272, loss = 156, time = 78
53 : total height = 1042, value = 5543, loss = 729, time = 687
54 : total height = 366, value = 2530, loss = 873, time = 141
55 : total height = 396, value = 3274, loss = 2159, time = 297
56 : total height = 1003, value = 7342, loss = 437, time = 953
57 : total height = 1011, value = 6046, loss = 2872, time = 719
58 : total height = 854, value = 2930, loss = 162, time = 140
59 : total height = 773, value = 4403, loss = 389, time = 360
60 : total height = 908, value = 9033, loss = 4144, time = 1688
61 : total height = 598, value = 1920, loss = 401, time = 94
62 : total height = 454, value = 2106, loss = 424, time = 62
63 : total height = 306, value = 1679, loss = 1328, time = 47
64 : total height = 671, value = 4077, loss = 1706, time = 343
65 : total height = 511, value = 4976, loss = 3436, time = 610
66 : total height = 1117, value = 5010, loss = 3971, time = 641
67 : total height = 933, value = 6971, loss = 4137, time = 1328
68 : total height = 318, value = 2132, loss = 1043, time = 156
69 : total height = 375, value = 3858, loss = 2210, time = 282
70 : total height = 430, value = 3638, loss = 1997, time = 281
71 : total height = 486, value = 3008, loss = 2230, time = 250
72 : total height = 325, value = 2926, loss = 2144, time = 296
73 : total height = 308, value = 1478, loss = 98, time = 16
74 : total height = 1084, value = 9510, loss = 4821, time = 1532
75 : total height = 275, value = 1683, loss = 882, time = 62
76 : total height = 1112, value = 7774, loss = 4791, time = 1312
77 : total height = 401, value = 4007, loss = 3643, time = 516
78 : total height = 325, value = 1768, loss = 343, time = 31
79 : total height = 870, value = 4066, loss = 1880, time = 375
80 : total height = 801, value = 2497, loss = 632, time = 172
81 : total height = 900, value = 8723, loss = 6394, time = 2156
82 : total height = 459, value = 2769, loss = 838, time = 156
83 : total height = 381, value = 2330, loss = 132, time = 78
84 : total height = 986, value = 5858, loss = 653, time = 516
85 : total height = 519, value = 2456, loss = 1358, time = 109
86 : total height = 419, value = 1350, loss = 126, time = 16
87 : total height = 508, value = 4111, loss = 1298, time = 422
88 : total height = 941, value = 6569, loss = 1679, time = 985
89 : total height = 488, value = 3196, loss = 1652, time = 187
90 : total height = 350, value = 2535, loss = 836, time = 125
91 : total height = 738, value = 2044, loss = 16, time = 110
92 : total height = 509, value = 5156, loss = 4652, time = 1282
93 : total height = 1083, value = 6233, loss = 1649, time = 765
94 : total height = 560, value = 2609, loss = 30, time = 110
95 : total height = 546, value = 2828, loss = 1632, time = 172
96 : total height = 468, value = 2531, loss = 908, time = 125
97 : total height = 551, value = 3764, loss = 390, time = 234
98 : total height = 705, value = 5834, loss = 3247, time = 812
99 : total height = 447, value = 2562, loss = 481, time = 79
100 : total height = 272, value = 2190, loss = 2276, time = 218
Score = 419407.0