Educational Codeforces Round 182

A. Cut the Array

全探索すればよいです．

総和が $3$ の倍数であることが必要で，そのときどう切っても大丈夫．という解法もあると思います．

? がひとつならば埋めておきます．? は $0$ 個または $2$ 個以上です．

先頭，末尾から不要な項を除いていきます．これで残った部分はすべて必要コストにできます．

ここに ? が $1$ 個ではないことを使います．

$i=0,1,2,\ldots$ 順に，選ぶ・選ばないを決めていく単純な dp でできます．

$x=2,\ldots,\max(A)+1$ でのコストを求めます．$2\leq max(A)$ のときは上限は $\max(A)$ でよいです．

計算は $2$ パートあります．$1$ パート目は，$\lceil a/x\rceil$ の総和です．

$x$ と商 $k$ の組が $O(A\log A)$ 個であることから計算します（頻度列の累積和テーブルを利用）．

$2$ パート目は，タグの再利用回数です．これも，$x$ と $k=\lceil a/x\rceil$ の組を全探索します．

$a$ は元の値段です．$(x,k)$ に対して対象となる $a$ が $m$ 個あるとき，$m$ と $k$ の頻度の $\min$ を再利用回数に足すというようにします．

左右から見てはじめて $\max(A)$ を選ぶまでのところを計算します．reverse して $2$ 回解くというタイプの実装が有効です．

列全体の $\max$ の列を予め計算しておきます．各項の扱いは，

のどれかです．prefix max ごとの数え上げの列を考えると，遅延セグメント木で実装できることが分かります．

あとは，左右からの計算結果を合わせて答を得ます．$\sum_{i=j}L_iR_j+\sum_{i<j}L_iR_j\cdot 2^{j-i-1}$ というような計算に帰着されます．

$s_i$ のうちで “()” があるとき不可能です．

そうでないとき，$k=2$ がいつでも可能です．”((((()))))” と “()()()()()” を考えると，両方の部分文字列になっているものは “(“, “)”, “()” だけだから，この $2$ 種を使えばよいです．

なので，$k=1$ でできるかを判定するのがメインテーマということになります．

Trie + Aho-Corasick を使えばよいです．suffix に $s_i$ のどれかを含むノードは通ることが禁止されていて，あとは例の累積和の条件に気を付けながら trie 上の walk を作るという dp になります．

計算量は $O(k\cdot \sum |S_i|)$ にできますが，制約がいろいろかなり小さいので多少計算の悪い実装でも大丈夫だと思います．