AtCoder Regular Contest 093：E - Bichrome Spanning Tree

問題

https://atcoder.jp/contests/arc093/tasks/arc093_c

考え方

サンプル2から、MSTの重みが X 未満に含まれる辺はすべて同じ色で塗らないといけないことが分かる。そこで

F(y) := MSTの重みが y 以下である辺を同色でぬるときの条件を満たす塗り方

とすると、求めたい値は F(X-1)-F(X) である。MSTの重みが X-1 以下になるMSTに含まれる辺はすべて同色でぬって、そうでない残りの辺は白、黒のいずれかの色で塗ればよい。F(X) を差し引く理由は、F(X-1) でほぼ条件を満たす塗り方の個数が含まれるが、MSTの重みがちょうど X になる場合に使われる辺を同色で塗る塗り方は条件を満たさないので F(X) の個数を差し引く必要がある。

F(y) を求めたいので M つの各辺について、その辺を含む最小全域木の重み W を求めて、その個数を求めておく。これは計算量 O(M^2\ logM) で求めることができる。

F(y) を具体的に求めよう。これはMSTの重みが y 以下になる辺の個数を cnt_y とすると

{\displaystyle 
\begin{eqnarray}
  \left\{
    \begin{array}{l}
    2^M & (cnt_y=0) \\  
    2 \cdot 2^{M-n}=2^{M-n+1} & (cnt_y>0) 
    \end{array}
  \right.
\end{eqnarray}
}

となるので、実際に F(X-1)-F(X) を計算することで解を求めることができた。

Submission #4091526 - AtCoder Regular Contest 093

どこに着目して考察するべきだったか

求めたい値を関数で考えることによって見通しがよくなりそう。具体的には F(y) と定義することでまずは求めたい解が定式化される。まずMSTの重みが X 未満のMSTに含まれる辺はすべて同色で塗らないといけないことが分かる。逆にこのような塗り方はほぼ条件を満たすが、一部条件を満たさない塗り方が存在するのでその個数を差し引くという思考に至るとよかったかもしれない。

何がバグっていたか

得た知見(典型ポイント)

  • 求めたい値を関数で表現する
  • 条件を満たさない個数を差し引く

類題