2019-01-21

D - Various Sushi

ABC 貪欲

D - Various Sushi

概要

N個の寿司があり、i番目のネタはt[i], 美味しさはd[i]である。このうちK個食べたい。
食べたときの満足度は O + T となる。ただし

O = 食べた寿司の美味しさの総和
T = 食べたネタの種類の二乗

である。このとき、食べる寿司を上手く選んで満足度を最大化せよ。

感想

こういう問題は何かを固定して全探索をするのが定石で、この場合だと食べる種類数を全探索する、という方法はすぐに思いつきました。

しかし、ここで詰まります。種類数を固定しても「どのネタからいくつ取ってくる？」が決まらないからです。「あるネタから何個取ってくる」が決まれば、大きい美味しさ順に取ればいいのは明らかですが……どのネタをチョイスすべきか、これが分からない。

最適化問題なので満足度の二分探索なども考えるが、うまくいかなさそうです。DPはあるかもしれないですが、高々O(N)ぐらいまでしかできない、となると少し厳しそうでこの場合だと、どの種類までの寿司を考えたか、と、今まで何個食べたか、の情報ぐらいは必要そうだからO(N^2)はかかるんじゃないかっていうので却下しました。

となると、貪欲かなあという気持ちになりますが、どう貪欲するのかなあ……って感じです。

と、ここでたとえx種類の寿司を食べると仮定して実際はx種類以上食べていても大丈夫なんじゃないか？ということに気が付きます。
なぜならT = x^2なので過小評価することはあっても過大評価することはないからです。

というわけで次のような戦略を立てました。x = 1, 2, ...と動かしていって

各ネタの最大値を大きい順にx個取る
残りのK-x個の寿司は、各ネタの最大値以外の寿司を大きい順にK-x個取る

として求めた値をmax更新していく。

実際には残りのK-x個の寿司を取るときに、最初に取ったx個以外のネタも混じっているかもしれないので種類数はxより大きくなっている可能性はあります。
ただそのときの解は、Tは過小評価してることになるし、和のほうもよく考えると過小評価していることになって、maxを取るときの影響を与えることがない、ということが言えます。（つまり最初に取ったx個以外のネタも混じっているような解は無視してよい）

この方法でやれば寿司をソートするのに最も時間がかかるのでO(NlogN)で解くことができます。

公式解説PDFの想定解と少し違うようなので久しぶりにブログ記事にしてみました。

2018-12-06

競プロでやりがちなミス集

その他 tips 競プロ

自分がよくやりがちなミスをまとめてみました。
このようにまとめておくことで、

よくやるミスをやらかさないよう注意深くなる
解法は合っているはずなのに何故かWAする、といった場合に疑うべき場所が明確になる

という効果を期待しています。D言語特有の仕様とかも結構あるので、一般にはあまり役に立たなさそうです。

longにすべきところをintにしてオーバーフローさせてしまう
10^^12と書いてオーバーフローさせてしまう(正しくは 10L^^12)
1<<60と書いてオーバーフローさせてしまう(正しくは 1L<<60)
while (a.front < x) のように書いてしまいRE（正しくはwhile (!a.empty && a.front < x), 空配列でないことを逐一チェックする必要がある)
BinaryHeapをminが出てくると勘違いしてしまう(BinaryHeap!(Array!T, "a < b")()みたいに書くので）
尺取り法が上手く実装できない
境界条件があやふや
中央値を求めるときにソートし忘れる
infを十分大きな値にしていない
BFSするときに頂点を見たときに距離を書かなきゃいけないのに、頂点を訪れたときに距離を書いてしまう
空チェックをせずに、a.lowerBound(x).frontと書いてRE
bitwise orをxorと勘違いしてしまう

なにかまた思いついたら更新します。

2018-12-04

No.752 mod数列

yukicoder クエリ累積和平方分割

No.752 mod数列 - yukicoder

問題

数列
$a_i = P \% i (i = 1, 2, 3, \dots)$
が与えられる。

$Q$ 個のクエリ $(L_j, R_j)$ に対して
$\sum_{i = L_j}^{R_j} a_i$ を求めよ。

制約

$1 \leq P \leq 10^9$
$1 \leq Q \leq 10^5$
$1 \leq L_j \leq R_j \leq 10^9$

解法

まずおなじみの累積和テクニックの考え方から

$\sum_{i = L_j}^{R_j} a_i = \sum_{i = 1}^{R_j} a_i - \sum_{i=1}^{L_j - 1} a_i$

が成り立つので、任意の $R$ に対して

$\sum_{i = 1}^{R} a_i$

を求めるにはどうすればよいか？を考えることにします。

ここで $R \leq 10^5$ 程度までであれば単純に累積和でやればいいんですが、今回は $R \leq 10^9$ ですので一筋縄ではいかなさそうです。まずいきなり和を考えるのではなくて、数列 $a_i$ がどのようになっているかを考えてみることにします。自明ではあるが重要なこととして、 $i > P \Rightarrow a_i = P$ となっていることが分かります。よって $i \leq P$ だけで考えてみることにします。

こういうのは小さな具体例から考えてみるとよいので、 $P = 24$ として $a_i$ がどのようになるかを見てみます。

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
$a_i$	0	0	0	0	4	0	3	0	6	4	2	0	11	10	9	8	7	6	5	4	3	2	1	0

すると一つ分かりやすい法則が見えます。 $i = 13, 14, 15, \dots$ となるにしたがって $a_i$ は一つずつ減っていくことが分かります。このことを式で表すと $P > i > P / 2 \Rightarrow a_i = P - i$ となるということが分かります。さらに $i = 9, 10, 11$ にも着目するとここでも規則性が見えて、 $a_i$ が2ずつ減っていくことが見て取れます。これも式で表すと $P/2 > i > P / 3 \Rightarrow a_i = P - 2i$ となることが分かります。

ここまで分かると一般化することが出来て、最初の自明な事実 $i > P \Rightarrow a_i = P$ も合わせると、

任意の $k = 0, 1, 2, \dots$ に対して $P / k > i > P / (k + 1) \Rightarrow a_i = P - ki$

と表せることが分かります。ここで $k = 0$ のとき $P / 0 = \infty$ と考えることにするとつじつまが合います。

そしてこれが分かると、 $k$ を固定したときの区間 $(P/(k+1), P/K)$ に含まれる $i$ に関する $a_i$ の総和というのは簡単に分かります。 $P$ は単に区間の長さ倍すればよく $ki$ の部分はおなじみの $\sum_{i = 1}^{N} i = N(N-1)/2$ という公式を使えばよいからです。

さて、この事実が分かると何がよいのでしょうか？
任意の $k = 0, 1, 2, \dots$ に対して $P / k > i > P / (k + 1) \Rightarrow a_i = P - ki$ で、この区間に対して $a_i$ の和は $O(1)$ で求められます。なので $k = 0, 1, 2, \dots, P$ と回せばいいわけですが、 $P \leq 10^9$ までなのでこれでは計算量の削減になっていません。
しかし、 $k = 1, 2, \dots, 9999$ までやるとしてみましょう。すると $i > P / 10^4$ の部分に対してはこれで求められて、残りの $i \leq P / 10^4$ の部分は累積和で求めてやることにすると計算量が良い感じに収まることが分かります。
後は和の上限が指定した $R$ を超えないように適宜区切ったりなんやかんやする必要がありますが、大筋のアイデアはこんな感じで計算量は今回は適当に $10^4$ とかにしましたが一般には $\sqrt{P}$ くらいにするのがいいので $O(Q + \sqrt{P})$ に出来ます。

感想

計算量にルートが出てくる問題ってあまり無い気がして面白かったので久々に書きました。