みんなのプロコン 2018 C問題
https://yahoo-procon2018-qual.contest.atcoder.jp/
C問題を解けなかったというメモでございます。
競技中に考えたこと
問題を一通り読んだときの特徴は
「x,c,vが非常に大きいので計算時間にこれらが関係してしまうと即アウト」
「N <= 18が小さく、また半端な数。Nの(次数が高めの)多項式、もしくは2^Nあたりの計算時間かな」
互いに「自分がこの手を出したらその後の得点がどうなるかを考えてから自分の手を決定する」という状態である。再帰構造、DPの構造に似ている。集合に対するDPだとするとビットDPである。蟻本を持ってきてビットDPの項目を読む。
高橋くんの売り方は一定なので、所持金は商品の要素数に応じて自動的に決まるところがコツである。
DP[S]を、高橋くんの手番で買える商品の集合がSであるときに、その後両者最善を尽くした場合の得点と定める。定義より問題の解答はDP[1,2,...,N]である。またDP[$\phi$] = 0である。
例えばDP[1,2,3]を求めるにはどうすればよいか。
- 高橋くんが財宝を売却することに決めると、得点はDP[1,2], DP[1,3], DP[2,3]のいずれかになる。しかし、青木くんはこのうちの最小になるように選ぶのでmin{DP[1,2], DP[1,3], DP[2,3]}となる。
- 高橋くんが商品を購入することに決めると、実行可能な買い方の価値のうち最大のものが得点となる。これをbuy[1,2,3]としよう。
- 以上より答えはmax{min{DP[1,2], DP[1,3], DP[2,3]}, buy[1,2,3] }となる。
buyの計算量を考えなければ、計算量は$O(N 2^N)$である。(一つの状態での得点を計算する際に、最大N個の数を参照せねばならないので、最初にNを掛けている。) N=18のときこの値は約471万 < 10^7。よって間に合うのでめでたし……ではない。
buy[1,2,3]を素直に計算すると「8通りの部分集合に対してコスト合計と価値の合計を計算して、コストが所持金以下となる組み合わせの中で価値最大のものを選ぶ」という方法になる。計算時間は$2^3$であり、一つのDP[...]を計算するときに最大で$2^N$の時間がかかってしまう。
というわけで計算時間の合計は$N\cdot2^N\cdot2^N$ か(正確な計算量は後述)……アカン。これでは間に合わない。
buy[1,2,3]とbuy[1,2]では後者のほうが所持金が多いことに注意する必要がある。極端な話、buy[1,2]では商品1と商品2の2つとも買えるが、buy[1,2,3]では所持金が減ったので何も買えない、といった事態も起こりうる。したがってbuyのほうはDPで計算できなさそうだし、かと言って全通り探索は時間が足りないのでここで手詰まり、試合終了。
上記方法の計算量について
実は、上記の解法で解いたときの計算量は$2^N \times 2^N$よりも少ない。
2^N個のマス目があるDPテーブルの各要素は、高々N個の前要素を参照して計算できる。よってDPテーブルを全て計算するのに掛かる時間のうち、buyの計算を除いた部分は高々N * 2^Nである(厳密に計算しても良いが、その結果の値はこの半分である)。
さてbuyのほうのテーブルの計算だ。テーブルのマス目は全部で2^N個である。あるマス目の要素数がk個ならば計算量は高々N*2^k。要素数がk個となるマス目は${}_N C_k$個あるから、合計は
\sum_{k=0}^N N\cdot {}_N C_k \cdot 2^k
= \sum_{k=0}^N N\cdot {}_N C_k \cdot 2^k 1^{N-k}
= N(2+1)^N = N3^N
二項定理とか超久しぶりに使ったな……全体の計算量も、$O(N 3^N)$である。
正解は
buyテーブルの求め方を解説文を参考に書く。
buy[{1,2,3}, M]を、Mの金を持っていて商品1,2,3を買おうとするときの価値の最大値とする。
- 全部の商品を買えるならば全部買うのが最適解。
- そうでない場合、買わない商品が1つ以上あるのでこれはmax{buy[{1,2}, M], buy[{1,3}, M], buy[{2,3}, M]}に等しい。
計算量について。
Mを1つ固定した場合、buy[X, M]を求めるためには2^|X|個のテーブルを埋めれば答えが出る。そしてMは(高橋くんの各手番での所持金の)N通りある。高々$N\cdot2^N$の計算量となる。(もう一つNが掛かるかも?)
DPを求めるときには「所持金は商品の要素数に応じて自動的に決まる」を利用して要素数を削減していた。しかしbuyテーブルを求めると金は、所持金・商品要素数の組み合わせのうち実際には起こり得ないものまで考えなければいけない。一度上手く利用できた条件を逆転して考えなきゃいけないわけで、だいぶ難しいと思った。
おしまい。