ferinの競プロ帳

競プロについてのメモ

2017-09-28から1日間の記事一覧

AOJ 2429 marukaite

問題ページ marukaite | Aizu Online Judge 考えたこと 解説を見た。 最小費用流を流すところは書けたが操作の復元に手間取った…最小費用流を行ったあと、容量が0の辺が存在すればその辺には流れたといえる。つまりR_iからC_jへの辺の容量が0であれば(i, j)…

SRM 712 div2 med RememberWordsEasy

考えたこと O(max(d_1,d_2)max(w_1,w_2))で愚直にDPするのは無理。考察の方針が思い浮かばなかったのでとりあえず手で試してみる。区間の端を0単語とすると1~d1までの和の単語数までは全て実現することが可能そう。区間の端を決め打ってその区間で実現でき…