Fまで六完。Gも解法はあっていた。惜しかった。
コンテスト後のツイート
G 二部グラフの最大独立集合だと思い、https://t.co/xw3a3nUvRfを参考に実装したが答えが合わず終了。
— titia (@titia_til) February 14, 2026
この前のARCでこの話が流れてたから思いつきやすかったけど、実装していなかった。
G - Knight Placement
フローした後、最大独立集合を求めるために色を塗るところで、色を塗った後間違ってもう一回初期化してた（塗った色を消していた）のが敗因だった。一行消したらバグは取れ、そのままだとTLEしたけどfloat("inf")を1<<63に直したりしたらACした。
（ただし、1<<30にしたらもっと早くなるかな？ と投げてみたらTLEしたので、運が良かっただけみたい。コンテスト中のACは厳しいかも？）
惜しかった……。
0 件のコメント:
コメントを投稿