きろく

特筆すべき記録のまとめ

Tenka1 Programmer Contest 2019:D - Three Colors

問題

atcoder.jp

解法

a の和を sum とすると max({R, G, B}) < sum / 2 が成り立っていれば三角形を構成出来る.なので,R, G, B のどれかが 1 つでも sum / 2 以上の値であるとき,三角形は構成できない.

ここで,塗り分ける場合の数全体から三角形を構成できない場合の数を引くことを考える.具体的には,U を全体集合とし n(P) を P であるような場合の数とすると,

n(U)

 - (n(R >= sum / 2) + n(G >= sum / 2) + n(B >= sum / 2))

 + (n(R >= sum / 2 かつ G >= sum / 2) + n(R >= sum / 2 かつ B >= sum / 2) + n(G >= sum / 2 かつ B >= sum / 2))

 - n(R >= sum / 2 かつ G >= sum / 2 かつ B >= sum / 2)

が答えになる.

n(U) = 3^N

n(R >= sum / 2) = n(G >= sum  / 2) = n(B >= sum / 2)

n(R >= sum / 2 かつ G >= sum / 2) = n(R >= sum / 2 かつ B >= sum / 2) = n(G >= sum / 2 かつ B >= sum / 2)

n(R >= sum / 2 かつ G >= sum / 2 かつ B >= sum / 2) = 0 (∵ このとき R + G + B > sum となるから)

であるので,

3^N - 3 * n(R >= sum / 2) + 3 * n(R >= sum / 2 かつ G >= sum / 2)

を求めればよい.n(R >= sum / 2) と n(R >= sum / 2 かつ G >= sum / 2) は「dp(i, j) := i 番目の数字までを使って,和が j となるような場合の数」と DP を考えれば求まる.後者は DP で計算する際,B に割り振ることを考える必要がないことに注意する.O(N^2 * max(a)).

解答

atcoder.jp

f:id:babcs2035:20190421135246p:plain