ヒューリスティック問題のHに手をつけた後、部分点集めを頑張った。Dは解きたかったね。
コンテスト後のツイート
F s,tにワープがあるときのx,yの最短距離はO(1)で求まる（20点）
— titia (@titia_til) March 29, 2022
G 小課題1は[l,r]でオイラー路になるか判定。小課題2は、地点xから出発した後、今後xを何度通るかを足していく
H 利益/距離で大きい順にソートして、道が重なることのないよう一つ仕事を終えたら次の仕事へ、とした。これで180点ちょい
D - 試験作り
ソートしてDPだとは思ったが、ソートの仕方を詰められなかった。
DP[Aで要した時間] = (Bより何問お得か, Bがかかった総時間) として、DPを更新する際、Aについては全部を見るので、Bについてどうソートするかが重要。Bの数が小さい順に問題は解かれるので、Bを小さい順にソートしておけばOK。
コンテスト中はAについてソートしていたので部分点しかもらえず。どういう理由でソートするのかちゃんと考えなくてはいけなかった。
0 件のコメント:
コメントを投稿