ARC074 E - RGB Sequence
(l[i], r[i], x[i])の組がM個与えられる。Nマスを赤 緑 青で塗り分ける時、[l[i], r[i]]の範囲はx[i]色になるという制限を課す。塗り分け方は何通りか。
何通りか、なのでdpで考える。
n番目まで色を塗って、一番最後に塗った色と初めて異なる色が塗られたところがp, もう一つ異なる色が塗られた場所がq(つまりp>q)とするとき、dp[n][p][q] 通りの塗り分け方があったとする。これについて次の色を塗った時 dp[n+1][p][q], dp[n+1][n][p], dp[n+1][n][q] の三通りの遷移が存在する。特に色数の制限がないときは単純に配るdpをすればよい。n番目まで色を塗った時、[l[i], r[i]=n] が x[i]色という制限があったとする。このとき、上の3通りのうち、pやqとl, rの大小関係でその範囲内にある色数が決定するので、その範囲を満たさない場合は遷移が出来ない(配るdpができない)
これを繰り返した後、dp[N][i][j]のうち、i、jを動かした総和が答え。O(N^3)。
注意点としてdp[N+1][N+1][N+1]をやると空間計算量もO(N^3)になるが、これは3000万ほどの配列であり、JavaだとMLEになる。(おそらくC++なら大丈夫なのだろうが)
そこで、dp[2][N+1][N+1]で計算する。
また、n=r[i]の制限を発見するために線形探索は絶対にしてはいけない。ハッシュでも良いが、処理計算量1000万ほどであるため、かなり高速にしておく必要がある。
