ABC222 参加記録
コンテスト中AC:A〜E
D - Between Two Arrays
以下のDPを考えます。
がである整数列の総数
遷移を考えると、のとき、をにできるので、
となります。
これをについて計算していると、
というワーストケースを例として計算量はは超えてくるので、計算量を改善する必要があります。
番目でできる整数列について、以下のように累積和を計算しておきます。
そうすると、遷移の際に和をとる部分が全てのについてで計算できるようになり、ワーストケースでも計算量は程度になり、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を赤に塗ったとすればは+3されます。
このように考えると、数列の和を2分割し、とに割り当てる問題となります。
和の2分割は、部分和DPが使えます。
部分和DPでは、数列の要素の総和をとすると、の連続とは限らない部分列のうち、要素の和がとなるものが何通りあるかをについて、で計算できます。
ここで、
とおき、これをすべてのについて計算すれば、あり得るすべての和の2分割と、それが何通りあるかを得られます。
あとは、を満たすようなものを合計すればそれが答えです。
計算量を考えます。
辺を何回通るかというのは、BFS+経路復元で求められます。BFSは今回なので、回実行すると、くらいです。
部分和DPはですが、仮に1000個の辺を100回通ったとしても、程度となり、これ以上にはならないので、間に合います。
提出コード:https://atcoder.jp/contests/abc222/submissions/26465104