長さNの数列Aが与えられる。また、{1, 2, ..., N}が含まれる集合Xを考える。Xの空でない部分集合Tについて、次のf(T)を定める。
f(T) := Tの空でない部分集合を{t_1, t_2, ..., t_i}とする。A[t_1]+A[t_2]+...+A[t_i]==Sになるような部分集合の数。
Tは $2^N-1$ 通りあるが、すべてのTについてのf(T)の合計を求めよ。ただし、大きくなることがあるので $998244353$ で割ったあまりを答えよ。

制約：　1 <= N, S <= 3000, 1 <= A[i] <= 3000

ACするまで

1. 制約はO(NS)を想定している。普通のナップサックでちょうど間に合う。
2. ある部分集合でSを作れるのならば、そのサイズがkならば、トータルで2^(N-k)回数えられたことになる。->サイズをどうにかして持ちたい！
3. サイズを普通に持たせてDPすると、O(N^2*S)になってTLEする。
4. サイズの代わりに、ナップサックの漸化式で持たせられる値でなんとかならないか？を考える。
5. 最初に2^N通りとして、1つの要素を追加で持たせたときに/2すれば、ナップサックでできる！->AC!

考察

ひとまず、ある集合Pを添え字に持つ要素の和がSになるとき、それは答えにどれぐらい寄与するのだろうか？
すべての部分集合の部分集合を数え上げるので、実質「Pを部分集合に持つ集合の個数」だけ数えられることになる。
つまり、 $2^{N-|P|}$ だけ寄与することになる。

というわけで、「dp[i][j] := i個目まで見て、和がjの時の場合の数」のナップサック問題の亜種に個数を持たせて、次のDPテーブルが思いつく。
dp[i][j][k] := i個目まで見て、和がjの時に、k個の要素をすでに持った時の数

しかし、この遷移式はO(N^2*S)の計算量になるので、TLEしてしまう。遷移式にも工夫のやりようがない。

DPテーブルで落とせなさそうな次元を考えてみる。「i個目まで見て」と「和がj」の2つは、どうしても外せないとわかる。となると、なんとかして「k個の要素をすでに持っている」を外すしかない。つまり、普通のナップサックのような遷移式で、いい感じに値を定めて伝播させるしかない。

ここで、答えに寄与する分は $2^{N-|P|}$ だったが、|P|は数を1つ採用するたびに、 *何を採用したのにかかわらず* 、1だけ増える。(寄与する分は、そのたびに半分になる)
つまり、細部を無視して一般化できる、というパターンである。

ならば、最初にdp[0][0] = 2^Nとして、1つ採用するごとに/2していけば、普通のナップサックの遷移式で値を伝播させることができる！
素数MODなので、あらかじめ2の逆元を計算すれば、割り算が可能なのでこれはO(NS)でとけた。

ちなみにこの「何を採用したのにかかわらず」の性質で落とせるのは、DEGwerさんの数え上げPDFにも書かれている(ARC059-F)。

一言

実質初の全完なので、うれしくて書いちゃった。

2020-05-27

AGC - 044 - A - Pay to Win

AGC スカスカ DP 要反省メモ化探索実装オーバーフロー

atcoder.jp

概要

最初にx=0という数字を持っている。あなたは、次の操作のうち任意のものを任意の順番で、任意の回数回だけ行える。

(操作1)xを2xで置き換える。
(操作2)xを3xで置き換える。
(操作3)xを5xで置き換える。
(操作4)xを+1もしくは-1する。

操作1~4をするには、それぞれ1回あたりコストA, B, C, D円かかる。
あなたは最終的にx=Nにしたい。それに必要なコストの合計の最小値を求めよ。

制約：　1 <= N <= 10^18, 1 <= A, B, C, D <= 10^9

2020-05-23

Codeforces Round #642 (Div. 3) - F. Decreasing Heights

Codeforces 良問経路数決め打ち DP

codeforces.com

概要

H*Wの盤面が存在していて、それぞれのマス(i, j)ごとにはa[i][j]という高さがある。
Senくんははじめ(1,1)にいて、(H, W)まで行きたい。(i, j)にいるとき、次に行ける場所は(i+1, j)と(i, j+1)のうち、高さが(i, j)よりちょうど1だけ高い場所である。
実際に行く前に、ナマズに頼んで任意のマス目の高さを1だけ減らすことができる。これによって1円かかる。高さが負になってもよい。
少なくとも1つのルートで(1,1)から(H,W)に行けるようにするためには最低何円かかるか？

制約：　1 <= H, W <= 100, 1 <= a[i][j] <= 10^15

ACするまで

1. それぞれのマスに(1,1)からの距離を補正した値を考えると、いくつかのマスは自身自体の高さを減らさない限り採用できなさそう。
2. ある経路を考えると、(1,1)の高さをどこまで減らすべきか？という問題は簡単な証明する。
3. 基準となる高さがどこかを持ちながらDP->遷移が重そう・・・ $O(H^3 W^3)$ になりそう
4. 逆に考えるんだ・・・最小値を決めてDPで経路を見たらいいと・・・・
5. AC!

考察

配列は0-idx、マス目番号は1-idx。

b[i][j]=a[i][j] - i - jとする。このように距離で補正したb[i][j]によって、a[0][0]の高さをpとしたときに経路上のコストは次の式で表せる。(このb[i][j]を使うことで、各所での高さを(1,1)の高さに換算できる。)ここで、p>b[i][j]ならば、(1,1)を高さpにして通れないということである。
$\sum_{(i,j)∈通るマス}^{} b_{ij}-p$
これの最小化をするとき、p<=b[i][j]という条件から、 $p=\min(経路上のb_{ij})$ にするべきであるとわかる。

さて、どうやって最小を持ちながらDPするのだろうか？

dp[i][j][k][l] := (i,j)まで行って、最小値を(k, l)にしたときの最小コスト

として考えてみる。しかし、遷移を配るDPでやってももらうDPでやっても[k][l]の部分で遷移に $O(HW)$ かかりそう・・・(たぶんできるけどつらい)

しかし、ここで「最適なルートにおける基準となるb[i][j]を全部試せばよくない？」

$O(HW)$ でpにするb[i][j]を全探索して、それぞれの条件下で(i, j)を必ず通るような経路での最小コストを計算すればよい！

(i, j)を必ず通る経路を計算するときに、以下のコードのように実装するとわかりやすい。

//必ず通るマスを(mi, mj)とする。
for(int i = 0; i < mi; i++)for(int j = 0; j < mj; j++){
dp[i + 1][j] = ...
dp[i][j + 1] = ...
}

for(int i = mi; i < H; i++)for(int j = mj; j < W; j++){
dp[i + 1][j] = ...
dp[i][j + 1] = ...
}

ACソースコード：
Submission #80910480 - Codeforces

最後に

大学B2になってから課題が多い。消化に移管がかかってなかなかかけないし競プロもできてない。

Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

ABC167 - F - Bracket Sequencing

概要

ABC171 - F - Strivore(自分用)

概要

Android開発 for Kotlin　自分向けのメモ帳　静的な部分

Android開発 for Kotlin　自分向けのメモ帳　動的な部分

ABC169 - F - Knapsack for All Subsets

概要

ACするまで

考察

一言

AGC - 044 - A - Pay to Win

概要

Codeforces Round #642 (Div. 3) - F. Decreasing Heights

概要

ACするまで

考察

最後に