Fまで六完。
コンテスト後のツイート
F DP[ind][time]をあるT[i]までをtime日に出荷し終えたときの不満度、としてダイクストラっぽく計算したら4TLE→ChatGPTでRUSTに直してもらいAC。
— titia (@titia_til) October 5, 2024
G SCCしてUnion-findでごちゃごちゃやったらサンプルは合ったが半分くらいWA。
G - Only One Product Name
解説放送・解説を見て、けんちょんさんの記事も参考にAC。
SCCして、DAG の最小パス被覆に帰着、という解法はちゃんと勉強していれば思いつけそう。（コンテスト中、自分も一瞬フローでは？ とは思ったので。その後違う方向に行ってしまったけど）
ただ、実装が難しい。SCCで頂点と頂点とを同一視できても、そこから出ている辺は同一視できない、というあたりが混乱を招く。
たとえば、AとBには両向きの辺があり、CとDには両向きの辺がある。さらに、AからCへ、BからDへそれぞれ辺があるとき、この二つの辺は区別しないといけない。
このあたりに注意するのが非常に難しく、たくさんのWAを重ねてしまった。解法を詰めてからやればできるのかもしれないけど、解法の概要が思い浮かび、細かいところは実装しながら詰めよう、とすると非常に難しい気がした。
0 件のコメント:
コメントを投稿