💧

ABC222-E: Red and Blue Tree 解説

2023/01/06に公開約600字

問題

N頂点の木グラフ, 数列A_1, ..., A_M, 整数Kが与えられます
それぞれの辺を赤か青かに塗ることを考える時,次の条件を満たす組合せの総数をmod 998244353で答えてください
駒をA_1, A_2,..., A_Mと最短経路で動かした時に 赤の辺を通った回数 - 青の辺を通った回数 がKと等しい

https://atcoder.jp/contests/abc222/tasks/abc222_e

解説

  • 次のステップに分解する
  1. 頂点A_1から頂点A_2の最短経路,頂点A_2から頂点A_3の最短経路,...,頂点A_{M-1}から頂点A_Mの最短経路を求める
  2. それぞれの最短経路の情報を元に,どの辺を何回通るかカウントする
  3. dp[i][j]: i番目までの辺を塗った時に 赤の辺を通った回数 - 青の辺を通った回数がjとなる組合せの総数
    • jが負の値をとるのでvector<map<int, modint>>を使うと便利
  4. dp[n][k]を出力

コード

https://atcoder.jp/contests/abc222/submissions/37767369

GitHubで編集を提案

Discussion

ログインするとコメントできます