CF #286のDiv2C/Div1AとDiv2E/Div1Cのwriterをしていました
せっかくなのでこの2問について解説を書きます
Div2C/Div1A
想定より難しかったようです。ごめんなさい。
M=島の数=30001とします。
O(M^2)解
dp[i][j]: 今番号iの島にいて、前回距離jジャンプを行った。ここから取れる最大のジェムの数(ただしi番目の島のジェムはまだ取っていないとする)
とし、メモ化再帰or動的計画法を行います。
if (i >= M) dp[i][j] = 0
else if (j == 1) dp[i][j] = (the number of gem in i-th) + max(dp[i+j][j], dp[i+j+1][j+1])
else dp[i][j] = (the number of gem in i-th) + max(dp[i+j-1][j-1], dp[i+j][j], dp[i+j+1][j+1])
という漸化式で答えは計算可能。
i, jの範囲は共にO(M)、漸化式の計算はO(1)ゆえ、計算量はO(M^2)
O(M^1.5)解
M^2では明らかに時間もメモリも足りない、そのためもうすこし考える。
実はM^2解におけるdpのjが取り得る値は、d±250(250=O(sqrt(M)))の範囲に収まります。
なぜならば
d + (d+1) + (d+2) + … + (d+250) >= 1+2+…+250 > 30000
またd > 250の時、
d + (d-1) + (d-2) + … + (d-250) >= 250+249+…+1 > 30000
が成り立つから。
よって、dp[i][j]: 今番号iの島に居て、前回距離*j - (d - 250)*のジャンプを行った
と置けば、jの取り得る範囲は0 ~ 500しかない。
これで計算すれば間に合います。
C++でいうmap,unordered_mapを使っただけのメモ化再帰は落とすつもりでした。
これに枝刈りとかを入れられると流石に落とすのは難しく、それで通るならいいかなくらい。
Div2E/Div1C
想定より非常に難しかったようです。ごめんなさい。
まずはともあれ二分探索をします。
これで、全部の竹を最終的に高さX以下に抑えられるかという問題になります。
i番目の竹は、少なくともceil((h[i] + m*a[i] - X) / P)回叩かなければいけません。
ですが、実はこの回数より多く叩いても意味は無いです。
なので、全ての竹をそれぞれちょうどこの回数だけ叩くと仮定します。
そして、全ての竹に付いて、竹がその1本だけ、かつk=無限だと仮定して、"この日より前にi回目を叩くと、最終的にかならず長さがX以上になってしまう"という日(逆締め切りと呼ぶ)を求めます。
そして実は、全ての竹の全ての叩きに付いて、この逆締め切りを守るように叩けば必ず全ての竹は長さX以下になります。逆締め切りをどこかで守れないならどれかの竹の長さは必ずX以上になります。
これがevimaさんの解法、hogさんはこちらの方がわかりやすいと言うのですが残念ながら僕には証明が出来ませんでした(悲しい)(だれか証明出来たら教えて)。
僕の解法も書きます。
二分探索は同じで、二分探索した後逆再生を考えます。
すると、
最初すべて長さXの竹が、毎日a[i]縮んでいく。
kitayutaは毎日k回までどれかの竹をPだけ伸ばす事が出来る。最終的に全ての竹を長さh[i]以上に出来るか。ただしどれかの竹がどこかで長さ0未満になったらその時点で失敗。
ただし、"叩く->伸びる"をm回繰り返すのではなく"縮む->叩く(伸ばす)"の繰り返しになる事に注意
という問題になります。本来の問題での長さが全てX以下となるのと同じように叩けば必ずこの問題も長さh[i]以上になりますし、逆もまた然りです。なんでかはそこまで難しくないので考えてみてください。
こちらの問題を解くには、priority_queueに長さが0未満になる日が速い(本来の問題で言うm日目に近い)順に入れてどんどん叩いていけば良いです。長さ0未満になるような竹がなくなったらh[i]に足りない竹を適当に叩けばOK。
非常にお気に入り問題なんですけど出しどころをミスった感はある、悲しい。
