LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

　Eまで五完。Gを考えていたが、Gは惜しくなかった。

コンテストへのリンク

コンテスト後のツイート

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263） Eまで五完。
C dfs
D 左右からいくつずつ減らせるかの累積を持ち、その累積minを取る
E そのマスへ至る確率と、期待値/確率を持ってDPした。双対セグ木を二本立てた

— titia (@titia_til) August 6, 2022

F - Tournament

　解説AC。

　DPだとは思ったが、どういうDPにすれば良いか組み立てられなかった。完全二分木なので、各段ごとにDPしていくというのは自然なのだけど、その後どう立式するかが難しい。

　勝者以外のもらえるお金を持つというのは、言われてみれば分かるけど思いつきにくい。

G - Erasing Prime Pairs

　解説AC。

　問題を見たとき、まずフローを疑ったのに、グラフの作り方を思いつかずその方針を追わなかったのはひどい。1がなければ、偶数と奇数で二部グラフになるのね、なるほど。

　実際にACしたのは、頂点を倍加し、i→j+Nに、A_i+B_iが素数のときに無限の流量を流す、という方法でACした。この解法の正当性が話題になっていたが、noshiさんのツイートに証明が書いてあった。