フローの理解が深まる君 問題 n頂点のグラフがあり、最初は辺がm本ある 全ての辺は容量1の無向辺である 辺の追加と削除のクエリがq個与えられる 各操作後の頂点1から頂点nへの最大流を求めよ2 1 解法 最大流はfordfulkerson法で求めるとして計算量はO(FE) も…

最小費用流の勉強になった 問題 n個の積み木があり、i番目は1*a[i]*b[i]の直方体の形をしている これらを積み重ねてなるべく高い塔を作りたい 長さ1の辺を奥行き方向に用いて、他の2辺を横方向と縦方向に1つずつ割り当てる(どっちをどっちにしてもok) 積み上…

スーパー包除原理マン 問題 n個の整数aとn個の整数pと整数mが与えられる i番目の整数a[i]をp[i]%の確率で選ぶ、という操作を各iについて行い、0個以上n個以下の整数を選ぶ 1以上m以下の整数の中で、選ばれた整数の少なくとも1つで割り切れるものの個数の期待…

めちゃくちゃ教育的類題 creep06.hatenablog.com 問題 箱根駅伝のある中継所における「各チームの通過順位」と「前の中継所からの順位変動」が与えられる 具体的には、c[i]がこの中継所をi番目に通過したチームの前の中継所からの順位変動を表し、 c[i] = '-…