パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 375）

 　EとGが解けず。

コンテストへのリンク

コンテスト後のツイート

F クエリを後ろから見て、ダイクストラ風に。(x,y)を基準に、xから一歩進む or yから一歩進むを更新。
G スタートとゴールからダイクストラして必要な可能性がある辺を求めたら、あとは何度も歩かせてみたら良いんじゃないか？　と思ったがWAが出るので何か間違っているよう。

— titia (@titia_til) October 12, 2024

E - 3 Team Division

　解法ツイートを見てAC。

　部分和問題に近いからDPだろうと思ったのに、どういうDPをすれば良いか見えなかった。だからといって、フローを疑ったりしていたのはダメ。

　DP[Aの和][Bの和]=そのときのペナルティ

　のようにすれば良かった。Bの総和に制約があるのも不思議なので、そこからDPを見破ることもできたはず。

G - Road Blocked 2 

　解法ツイートを見てAC。

　スタートとゴールからダイクストラして必要な可能性のある辺を求めるところまではOK。あとは橋を探せば良かった。

　何度もランダムに進ませればどの辺が必要なのかは分かるのでは？　と思ったが、片側だけ二方向に分かれていく木を考えればすごい低い確率でしか到達しない頂点は作れて、それ以外の頂点を別の一つの頂点につなげる……みたいにすれば、そこから出た辺は非常に高確率で通りますね。