geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC222 参加記録

コンテスト中AC:A〜E

 

D - Between Two Arrays

以下のDPを考えます。

dp[i][j]:=c_ijである整数列の総数

 

遷移を考えると、0 \leq c_{i-1} \leq jのとき、c_ijにできるので、

dp[i][j]=dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1]+dp[i-1][j]

となります。

これをA_i \leq j \leq B_iについて計算していると、

A=\{0,0,...,0\}
B=\{3000,3000,...,3000\}

というワーストケースを例として計算量は10^9は超えてくるので、計算量を改善する必要があります。

 

i-1番目でできる整数列について、以下のように累積和を計算しておきます。

S[j]=dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1]+dp[i-1][j]
そうすると、遷移の際に和をとる部分が全てのjについてO(1)で計算できるようになり、ワーストケースでも計算量は10^6程度になり、ACできます。

 

提出コード:https://atcoder.jp/contests/abc222/submissions/26455591

 

E - Red and Blue Tree

各辺の貢献度を考えます。

入力例1を例にすると、2 →3→2→1→4と移動すると、辺1を2回、辺2を3回、辺3を1回通ります。辺1を赤に塗ったとすればRは+3されます。

 

このように考えると、数列B=\{2,3,1\}の和を2分割し、RBに割り当てる問題となります。

 

和の2分割は、部分和DPが使えます。

部分和DPでは、数列B=\{B_1,\ B_2,...,\ B_{N-1}\}の要素の総和をSとすると、Bの連続とは限らない部分列のうち、要素の和がTとなるものが何通りあるかを0 \leq T \leq Sについて、O(NS)で計算できます。

ここで、

R=T
B=S-T
とおき、これをすべてのT\ (0 \leq T \leq S)について計算すれば、あり得るすべての和の2分割と、それが何通りあるかを得られます。

あとは、R-B=Kを満たすようなものを合計すればそれが答えです。

 

計算量を考えます。

辺を何回通るかというのは、BFS+経路復元で求められます。BFSは今回O(N+N-1)なので、M-1回実行すると、O(NM)くらいです。

 

部分和DPはO(NS)ですが、仮に1000個の辺を100回通ったとしても、10^8程度となり、これ以上にはならないので、間に合います。

提出コード:https://atcoder.jp/contests/abc222/submissions/26465104