この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 17 日目の記事です。 木クエリゴリゴリ問題です。 問題概要 頂点の木がある。頂点 の親は であり、その間の距離は である。 について、 を求めよ。 制約 解法 大体重心を求めたいという問題です。 頂点…

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 10 日目の記事です。 少し珍しいタイプの木DPの問題です。 問題概要 頂点の木がある。頂点 の親は である。各頂点 には価値 のコインが 枚ある。 あなたは木から価値の合計が最大になるよう最大 枚のコ…

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 3 日目の記事です。 ミンコフスキー和に関しての問題です。 問題概要 凸多角形 と整数 があり、 を満たしている。 凸多角形 が与えられるので、条件を満たす のうち、 の面積の和の二倍の最小値を求めて…

greed ではテストケースの情報を data という変数に格納していますが、これは C++17 から追加された std::data という関数と衝突してしまってコンパイルが通りません。 次のように変えることで衝突を防げます。 // template class ${ClassName} { public: ${…

greed ではテストケースの情報を data という変数に格納していますが、これは C++17 から追加された std::data という関数と衝突してしまってコンパイルが通りません。 次のように変えることで衝突を防げます。 // template class ${ClassName} { public: ${…

MathJax = { tex: {inlineMath: [['$', '$'], ['\(', '\)']]} }; onlinejudge.u-aizu.ac.jp $ V = \left\{ 1, \ldots, N \right\} $ とする。 $ f(S) = (S \subset V \text{に誘導される部分グラフが連結な確率})$ とおく。 実は $ 1 \in S$ しか考えなくて…

問題 atcoder.jp 概要は省略します。 求める答えを とします。 終了状態としてあり得る 個の状態を とします。 終了条件を除いて操作したとき、はじめて となるまでの回数の期待値を とします。 終了したときに となっている確率を とします。 終了するまで…