Midnight Code Cup

本戦が 24 時間という変な３人チームコンテスト

とりあえず流れで B を担当することになった。

面白かった。

早起き等により今にも寝そうな眠気だったがなんとか役割は果たせて良かった…

B

ナップザック問題を解くプログラムが３つ与えられる。

それぞれに対して、意地悪なテストケースを作成してください。

制約：

0 < W

0 <= N

0 < w_i, v_i

ファイルサイズが 100 Byte 以下

ファイルサイズの制約がユニーク

プログラム１

素朴な枝刈り探索

「選ぶ」「選ばない」の順に試す

残り全てを選んでもbestを超えられなければ枝刈り

W=23

(1,1)*22 (99,99) みたいなケースがかなり良いのだが、1 byte だけはみ出てしまう。

このように N=24 にすると 2 桁を 2 つまでしか使えない、という絶妙な設定が効いてくる。

code:01.out

a

b c *23

d e

この形に絞って探索すると (b,c) = (1,1) が強そうなので固定して探索した。

(a,b,c,d,e) = (16,1,1,9,99) などで400点が取れる。

が、+30 ステップ出来るらしい。すごい。

プログラム２

最初に効率順でソートする

枝刈りにヒューリスティックを使う

１と同じ形で探索すると (a,b,c,d,e) = (69,1,1,59,9) で 394.02 点が取れる

プログラム３

結構工夫してそうな探索

複雑なのでまともに考察せず、探索した。

N=23 にしてでも 2 桁を使った方が良いのかと思ったけど、N=24 が結局強そうだった。

イレギュラーは 2 つくらいは欲しそうだった。

code:03.out

41

9 8

9 9

3 3 *22

400 点が取れる、と思ったらもっと行けるらしく 388.042 点