愚直なDPを考えてみる。 f(i, j, k) = 「i人目まで確定して、前の人がj円払った時、合計金額がk円である場合の数」 これでは間に合わない。 とりあえず、最初の人の募金額を0~Sの範囲で総当たりして固定し見てよう。先の人も含めて、少なくともその額を支払…

まずは簡単な例外的な組合せから数えてみる。以下、解をanswerと表記する。どの友達もリュックに入れることができないならばanswer+=1。また、すべての友達をリュックに入れることができるならばanswer+=1。 それ以外の場合を数える。とりあえずリュックに入…

隣接要素同士の交換しかできないのだから、もし白または黒のみであれば、最小の操作回数は転倒数に等しい。 この問題では、白と黒の２色の並び方ごとに操作回数が異なる。しかし、白と黒の並びが定まれば、操作回数は一意に定まる。なぜなら、各並び方につい…

素朴に考えると dp[i][j] := i個の要素を使って、前の部品のprofit factorがjのときの最大profit のようなDPを得る。 例えば、サンプルの入力で6, 8を使うと dp[2][8] = 6*8 のようになる。 この方法には問題が3つあるが、どれも対処できる。 (1) profit fac…

気づき 操作はkの降順だけ考えれば良い。 vに対して整数k1で操作したあとk2で操作したとする。 k1 <= k2を仮定する。 vをk1で割った余りv'は v' < k1 を満たす。 k1 <= k2より v'をk2で割った余りもv'である。よってk2による操作で値が変わらず、 k2の操作が…

すべての頂点iについて(a[i], i)を終点候補として優先順位度付きキューに突っ込んおく。(u[i], v[i]) 間をコスト2w[i]の無向辺で接続したグラフでダイクストラ法っぽいことをする。 まず往復についてであるが、往路と復路の最短経路の長さが等しいことは明ら…

dp[i][d]:= 「i番目の台からd∈{左, 右}に落ちたとき最後にボールが行き着くx座標」とする。 iをyの昇順に決定することでこのDPを解ける。よって、事前にソートしておくことでi<=j ⇔ y[i]<=y[j]とする。台iの端dからボールが落ちたとする。このとき、x[i][d]…

蛍光灯が途切れずに照らしている範囲を左端から右端へ伸ばしていこう。 最適解では、手前で使った蛍光灯をi、次の蛍光灯をjとすると、l[i]<l[j] が成り立つ。なので、事前に蛍光灯をlの昇順にソートしておく。 dp[x] = 0からxまでが途切れずに照らされているときの最小コスト とする。dp[L]が解。 はじめ dp[0] = 0である。 蛍光灯をソートされた順にみよう。いま、i番目の蛍光灯の使用を考る。dp[r[i]]が更新されるかもしれない。 蛍光灯は[l[i], r[i]] の範囲を照らすので、 前の範囲 => (重複) => [l[i], r[i]] のようになっていれば、左端からr…</l[j]>

p(T)を 読み上げられたカードの集合がTであるときのパターン数とする。 p(Φ) = 1 p(T(!=Φ)) = Σ[i ∊ T] ( p(T-{i}) ) で簡単に求まる。 e(T)を読み上げられたカードの集合がTであるときの 期待値 と パターン数の積とする。 E[K] * P[N,K] = Σ[T⊆読み札, |T|…

エディトリアル見て書いたコード。コメントつき /* エディトリアルのとおりの解法 */ /* 重さ1, 2のsouvenirだけを使ったとき、重さの和がiとする。 このときdp[i]=(x,y,z)は以下の意味。 xはコストの和の最大値 yは重さ1のsouvenirをいくつ使ったか。 zは重…

上図は3番目の入力例の文字列t="abcab"にダミーの1文字を加えたt+'#'="abcab#"に対してKMP法のDFAを描いたもの。!はその他の文字を表す。tはオーバーラップしてもよいので、最終状態からの遷移もほしい。そこで、末尾にダミーの文字を加えた。これにより、最…

事前に1~max(a[1],a[2],...,a[n])の約数を求めておく。次に、約数qをもつ数を数えてcnt[q]のように表す。部分列のgcdをgとしたときq|gを満たす空でない部分列を数えよう。これは簡単で、qを約数にもつ数すべてについて、部分列に含むかどうかを考えてcnt[q]^…

dp[i][j][fs][sc] =i番目まの問題まで確定していて、j回カンニングしている。１人目に対して直前にしたカンニングの左端はiからfs個左、2人目に対して直前にしたカンニングの左端はiからsc個左とする。ただし、fs,scはK以上はすべてKの1値で表す。このとき最…

解法 f(n)を文字列にしたものをS(n)とする。|S(n)| = 2|S(n)| + (n^2の桁数)更に|S(4)| = 16 = 2^4なので|S(60)|>2^60 が成り立つ。よってR<|S(60)|であり、K>60の場合は、K=60と見なしてよい。以下、1<=K<=60とする。f(n)の各桁の値d(0~9)の出現数をcnt[n][…

X[i]の値を具体的に求めていこう。 各文字S[i]についてそれぞれX[i]を求める。S[i]がある回文に含まれる場合、S[i]と一致するようなもじS[j]がある。ただし、i=jでS[i=j]が奇数長回文の中心である場合も含む。iとjを総当りで固定した場合、それだけでO(N^2)…

http://codeforces.com/blog/entry/49911?#comment-344869 ↑の理解 |patterns|<=5なのでこれの最大ケース|patterns|=5の場合だけ考えてみよう。以下のような愚直なDPはすぐに思いつく。 dp[i][p[0]][p[1]][p[2]][p[3]][p[4]] := Sのi番目まで確定していて、p…

p[i]<=1000に注目する。p[i]/2000 <= 1000/2000 = 1/2 (1) i = 0,1,2,...,Tターンたったときに全種類そろっている確率をf[i]とし、これをすべて求めてl[i] = (p[i]-ε)/2000 の値で二分探索すればいい。ただし、(1)よりf[T]>=1/2でなければならない。そのよう…