問題 問題リンク：There is No Alternative N頂点M辺の重み付き無向グラフが与えられる。最小全域木を構成するとき、どのような構成でも必ず使用するような辺の本数とそのコストの総和を求めよ。 解法 最小全域木に1つ辺を追加したとき、その辺によって作ら…

2019/7/12(金)に行われたICPC2019国内予選にチームEldoradoとして参加しました。 チームメンバーは、nicklaw、mhrb、NOSSです。 チームメンバーの参加記 - ICPC2019 国内予選 参加記 - まほろば精進日誌 結果 ICPC2019順位表 ABCD4完で順位は41位でした。学…

問題 問題リンク：ばらばら饅頭 解法 各重さの饅頭の個数を状態に持ってメモ化再帰をすることを思いつくが より、最悪 程度のパターンが存在するため厳しい。 パターンを減らすため、先に決めて損のない組み合わせを貪欲に取り除いておくことを考える。する…

問題 問題リンク 解法 訪れる順によって移動時間が変わる。一方、いままで訪れた蔵が同じであれば次に移動するときにかかる移動時間も同じである。 よって、今後どう移動するかはいままでの経路順によらないので、訪れた蔵の集合と現在地のみを状態として持…

問題 問題リンク 解法 ある区間内の山をすべて重ねたとする。このとき山の順序は変わらないので最終的にできる山の状態は、その重ねる順序によらない。 よって、区間を決めれば操作順を無視できるので、その最小コストのみが分かっていればよい。また、ある…

ICPC模擬国内予選2019にチームEldoradoで参加しました。 ABCD4完で順位は参加資格有17位でした。 順位表：2019/Practice/模擬国内予選/順位 コンテスト中の動き Aをmhrbさん、Bをニクローさん、Cを僕が読む。 Aをmhrbさんが一瞬で通す。Bの考察が完了してい…