Educational Codeforces Round 181

A. Difficult Contest

すべての T を先頭に集めればよいです.

B. Left and Down

コスト $0$ では不可能.コスト $2$ があれば可能で,これは $(1,0)$ と $(0,1)$ の 2 種を使えばよいです.よってコスト $1$ で可能かを判定する問題です.最大公約数で割って最小化したものが指定の範囲に入っているかを調べます.

C. Count Good Numbers

$2,3,5,7$ で割り切れるという条件で包除原理をします.

D. Segments Covering

$\dp[i]$ を $[0,i)$ をぴったり入力区間に分割する方法とします.

区間を適当な方法でソートし(これは $[0,N)$ の分割に使われる順序と一致しさえすればよい)て,その区間まで見た時点での $\dp[i]$ を計算します.

「その区間を使わない場合」として,その時点での dp テーブル全体を定数倍する操作が発生します.双対セグメント木などで処理すればよいです.実際の dp の値とテーブルに保持している値の比が全体で共通なのでそれを管理してもよいです.

E. Sets of Complementary Sums

$N=1$ は自明なので $N\geq 2$ とします.

$a$ の最大値を $c$ とします.$s$ に対する条件は

  • $c\leq s+1$
  • $s-a_i$ たちの sum (どれも $1$ 回以上使う)で $s$ を作ることが可能.

です.特に $\sum(s-a_i)\leq s$ が必要です.この条件は $s$ が小さいほど成り立ちやすいです.何らかの $s$ がこの条件を満たすとき,$s=c+1$ がすべての条件を満たします.

よって $s=c+1$ だけを考慮すればよいことになります.さらに $b_i=c-a_i$ に関する条件として整理すれば,

  • $1\leq c\leq x+1$
  • $1=b_1<b_2<\cdots<b_n$
  • $b_1+\cdots+b_n\leq c+1$

を満たす組 $(c,b_1,\ldots,b_n)$ を数えることになります.

$b_1=1$ を除く $n-1$ 個の総和を考えて,適当に変換すると,最終的に次の計算に帰着できます:

$1,2,3,\ldots$ (上限なし)のうち互いに異なる $n$ 個を使って $x$ を作る方法を $x=1,2,3,\ldots$ で求めよ.

これは $q$ 二項係数が登場する有名数え上げです.

詳細

求めるべきは $[x^N]\prod_{i\geq 1}(1+xy^i)$ です.左辺を $F(x)$ として,$(1+xy)F(yx)=F(x)$ を用います($y$ を定数扱いして $x$ の多項式として考えている).

$F$ の係数を $F_n$ とすれば,$n+1$ 次の項の比較により $y^{n+1}F_{n+1}+y\cdot y^nF_n = F_{n+1}$ が出てきて,$F_{n+1}=\frac{y^{n+1}}{1-y^{n+1}}$ が出てきます.

結論は $F_n(x,y)=y^{n(n+1)/2}\bigl(\cdot (1-y)\cdots (1-y^n)\bigr)^{-1}$ です.

本問の場合には,$n(n+1)/2$ が大きい $n$ についての計算はしないでよいので,$1-y^i$ でひとつずつ割っていけばよいです($O(nx)$ 時間).一般には log, exp を使った計算が可能です($O(x\log x)$ 時間).

F. Timofey and Docker

$M:=N/6$ として,$0,1,\ldots,M$ 個の docker を作った場合に最大値が達成できるかをまず調べます.これは簡単.

初期状態で $m$ 個の docker がある場合,目標値は最大値を達成するような個数のうち $m$ の前後の高々 $2$ 個に限定できます.これは $1$ 文字変化させたときの docker の個数変化が $-1,0,1$ のいずれかであることから分かります.

よって,次が解ければよいです:$k$ は与えられていて,ちょうど $k$ 個の docker を作るコストを求めよ.

$\mathrm{cost}(i,j)$ を $[i,j)$ 内で docker をひとつ以上作るための最小コストとすると,これは monge 性を満たします.$\mathrm{cost}(i,j+1)>\mathrm{cost}(i,j)$ となるパターンが $[j-6,j)$ を作るパターンしかないことから簡単に分かります.

よって,Alien dp のテクニックによって解くことができます.

各 $i$ からコスト $0,1,\ldots,6$ を払う場合の最寄りの遷移先を前計算しておけば,全体で $O(N\log N)$ 時間で解くことができます.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました