問題ページ 考えたこと Q=1ならどうか？ SとTの間に重み0の辺を張ってMSTを求めればよい MSTを求めるのをQ回やったら当然TLE MST+αのやつは元のグラフのMSTを求めてそこからいじるのがよくあるパターン 元のグラフのMSTと辺を追加したグラフのMSTは何が違う…

問題ページ 部分点 たぷとたぴが連結にならないようにする→カットなので最小カットを求めればよい。N<=500ならば最大フローを求めるアルゴリズムで間に合うのでdinicなどのライブラリを貼ればよい。 満点解法 木DPをする。dp[i][j] = (頂点iの部分木でiと連…

問題ページ 解法 bitDPで数え上げる。dp[S] = (集合Sがすでにチームが決まっているときの組み合わせ数) とする。TをSに含まれない要素の集合とすると集合Tから1人、2人、3人を選んでチームとする。このチームをSに新たに加えた集合をS'とするとdp[S'] += dp[…

問題ページ 考えたこと 区間が何個取れますかなので区間スケジューリングっぽい 都市Aに行ったあと王国に帰るなら一番早い依頼をうけるべき 王国→都市→王国 と移動するのにかかる区間を列挙しておく この区間を何個取れますか？という問題になった これは区…

問題ページ 解法 各イノシシからの距離を別個で計算するのではなくまとめて計算することができる。グラフの仮想頂点としてイノシシまでの距離が0の辺を張った頂点を追加してその頂点からbfsをスタートするイメージ。イノシシからの距離をbfsで求めるのがO(HW…

問題ページ 考えたこと 1円玉が奇数枚だったら無理 10円玉が奇数枚だったら1円玉で10円分をつくらないとだめそう 100円玉が奇数枚だったら10,1円玉で100円分をつくらないとだめそう 貪欲に取っていくのを書いたら落ちた 冷静になって考えると100円玉が10^9枚…