ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Tenka1 Programmer Beginner Contest 2019 D - Three Colors

包除原理 動的計画法(DP) リベンジ

問題
提出コード

解法

まず、三角形の成立条件を思い出すと、長さx,y,zの三角形が存在するには、
x+y \gt z, y+z \gt x, z+ x\gt y
が全て成立している必要があります。
逆に、xが最長の辺かつx \geqq y+zを満たしているとき、三角形を作成することはできません。両辺にxを追加した後に2で割ると、

  • x \geqq \frac{x+y+z}{2}

という条件がでてきます。
仮にこの状況になった場合、xはx,y,zの中で最も大きい値になっているはずです。
x+y+zは\sum a_{i}で求めることができるので、x \geqq \frac{x+y+z}{2}となるような塗り分け方は、どうにかして求めることができそうな気がします。ということで包除原理を利用して、全ての塗り分け方から、三角形を作成できないようなパターンを引くことで答えを求めることにします。
xが最大であると仮定して、そのときにx \geqq \frac{x+y+z}{2}となる場合の数を求めることにします。すると、これはy,zが最大の場合も全く同じ状況になるので、3倍すればよいはずです。
場合の数を、動的計画法で求めていきます。

  • dp[i][j] = i番目までの数を割り振って、xの値がjになるようなものの場合の数

とします。これは、

  • dp[i+1][j] = dp[i][j] \times 2 + dp[i][j-a_{i}]

という遷移で数え上げることができます。
右辺の1つ目の項は、a_{i}をxに割り振らない場合で、残ったy,zのどちらかに割り振ることになるので、2倍します。 2つ目の項はa_{i}をxに割り振る場合です。
この遷移を利用して数え上げを行い、あとはsum = \sum a_{i}として、
\displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3
を求めれば、三角形にならないパターンを数え上げることができる…
はずですが、コーナーケースが存在します。
sumが偶数の場合、(x,y,z) = (sum/2,sum/2,0)となるケースが存在するかもしれません。このパターンは、上のDPをそのまま用いると重複して数えてしまいます。2つのsum/2を区別してsumA,sumBとすると、
dp[n][sum/2]には、
(sumA,sumB,0),(sumA,0,sumB),(sumB,sumA,0),(sumB,0,sumA)
の4つのパターンが含まれているはずですが、最後に全体から引く際に、xが最大という条件を外してこれを3倍するため、合計12パターンが引かれることになります。が、(sumA,sumB,0)というパターンは、3! = 6通りの並べ方しかないため、2回分引いてしまっていることになります。　
これを解消するために、これらのパターンも数え上げてしまいます。これまた動的計画法を利用します。
このパターンは、2種類のみにa_{i}を割り振ると出来上がるので、

  • dp2[i][j] = i番目までの数字をxとyのみに割り振って、x = jとなるようなものの場合の数

とすると、遷移は先ほどとほぼ同じで、

  • dp2[i+1][j] = dp2[i][j] + dp2[i][j-a_{i}]

という遷移で数え上げることができます。
先ほどの2倍をする部分だけが消えた形になります。
ということで、この遷移を行うとdp2[n][sum/2]は、(sumA,sumB,0),(sumB,sumA,0)の2パターン分だけ綺麗に数え上げられているはずです。
あとは、この部分の調整も行いつつ、

  • sumが奇数の場合
    3^{N} - \displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3

  • sumが偶数の場合
    3^{N} - \displaystyle \sum_{i=(sum+1)/2}^{sum} dp[n][i] \times 3 + dp2[n][sum/2] \times 3

を求めると、答えになります。

感想

解けるべき問題だった…？気がします。コンテスト中、似たようなDPをすることまでは思いついていたのですが、細かいところを詰められなかったのと、そもそもコーナーケースに気づいていませんでした。
雰囲気でDPを解いているのがバレる回でしたね。