Codeforces Round #610 A~Cまで

A, B1, B2の3完です。終了5分後にCが通りました......

A: b-a-max(0,(min(b,c+r)-max(a,c-r)))
B: mod毎ににぶたん
C: tを昇順に並べて、必須な問題を解くのに必要な時間を求めておく。あとはt[i]-1にどれだけ問題を解けるかを全探索
番兵のdiffとtを逆にしてて一生バグらせてた
— やまけー (@yamake_cpp) 2020年10月5日

B問題は問題文が長くて読むのが大変でした。

B2とCだけ解説してみます。

B2. K for the Price of One

問題概要

$p$ 円を持っている状態で一つあたり $a[i]$ 円の商品を何個か買いたい。
$a[i]$ 円の商品を買うときに、ちょうど $k-1$ 個の $a[i]$ 円より安い商品を無料で同時に受け取ることができる。
それぞれの商品は1度しか買えない。

最大で商品を何個買えるでしょう？

解説

値段を昇順にソートして、最初から $x$ 個を一つずつ、残ったものから $k$ 個セットで買えるだけ買っていくと答えが得られます。

反省

僕は残ったものからk個セットで買えるだけ買うところを、mod毎に累積和をとって二分探索したのですが、ここは二分探索をしなくても計算量は線形になります。

まあC++のupper_bound使った方が実装も軽いのでどちらでも良いのですが、計算量的に二分探索が必須だと思ったのはちょっと弱かったです。

B1も同じコードを投げるとACできます。

C. Petya and Exam

問題文が長くて読むのだけで結構時間がかかりました。

問題概要

$T$ 分間の試験を受ける。Petya君は任意のタイミングで試験を退出することができ、Petya君が退出するまでに解いた問題数を最大化したい。
それぞれの問題は簡単、難しいとわかれている。簡単な問題は一問あたり $a$ 分、難しい問題は一問あたり $b$ 分かかる。
それぞれの問題について時間関門 $t[i]$ が設定されている。Petya君が退出する時、その時刻より前に時間関門が設定されている問題は全て解かれている状態でなければならない。
Petya君は最大で何点獲得できるでしょうか。