全方位木 DP の抽象化を書いてみた。 コードと使用例のみ。(使用例はネタバレあり)気が向いたら解説を書くかもしれない、未来の自分に期待。 少しだけ書くと、rerooting_function では、子ノードの subtree_dp の累積を両側から取って、それぞれの子ノードに…

こういう問題を素早く解けるようになりたい。 リンク codeforces.com 問題概要 の 個の街がある。街 には の確率で電波塔が設置される。電波塔のパワー は自由に設定でき、距離が 未満の街に電波が供給される。街 と街 には電波が供給されず、 に重複なしで…

atcoder.jp 問題概要 '0', '1', '?' からなる長さ の文字列が与えられる。 '?' には、'0' または '1' が入れられる。 それを埋めた '0' と '1' からなる文字列の任意の連続部分列の中で '0' と '1' の個数の差が 以下となる文字列の個数を で割った余りを求…

DP は比較的すぐに浮かんだのに、復元できなくて詰んだ、反省。 リンク D. Nastya and Scoreboard codeforces.com 問題概要 上図のように数字を点灯させることができる Scoreboard がある。 個の Scoreboard の状態が与えられるが、新たに 個点灯させたとき…

atcoder.jp 問題の概要 匹のスライムが横一列に並んでいて、左から 番目のスライムの大きさは である。 隣り合う 匹のスライムを合体させて、 匹のスライムにする。 このとき、 匹のスライムの大きさを とすると、 のコストを支払う。 また、合体後の大きさ…

atcoder.jp 問題 から の番号が振られている 枚の皿があり、皿 には 個の寿司が置かれている。 すべての寿司がなくなるまで、次の操作を繰り返す。 の目が等確率で出るさいころを振り、出目を とする。皿 に寿司がある場合、皿 の寿司を 個食べる。皿 に寿司…

atcoder.jp【問題の概要】 番号1から番号Nの人がいて、トーナメントで番号1の人が優勝した。番号2から番号Nの人に関しては、どの番号の人に負けたかという情報が与えられる。この情報と矛盾を生じないトーナメントで、その深さが最小であるときの深さを出力…