Fまで六完。Fは未証明だったけど、この制約だと正当だったかも？（w=1や2がたくさんある場合が問題だけど、それはカバーできてそう）
コンテスト後のツイート
F CHTを使いそうだと思ったが分からず。ペナルティも含めて(v,w)を並べて、v/wが大きい順に並べた上位10000個に含まれるもの（それを1個でオーバーするなら1個は持つ）だけ使ったらACした。
— titia (@titia_til) September 28, 2024
G - No Cross Matching
解説AC。
最小費用流の方法でACした。
自分の最小費用流のライブラリはひどいと思っていたが、TLEが出たため久しぶりに見直した。多少は速くなったか。
ただ、今回のテストケースではたまたまACできただけで、簡単にTLEするケースは作れる模様。うーん。
0 件のコメント:
コメントを投稿