2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) - E. Getting Deals Done

概要

n個の仕事がある。整数m, x, tがありこれらの仕事を前から順に次のルールで行う。

かかる時間がx以下ならば行う。そうでないなら飛ばす。
mこの仕事を終えたら、そのmこの仕事にかかった時間のぶんだけ休む。
時間がtをぎりぎり超えない時点でのこなせた仕事の数をf(x)と定める。

f(x)の最大値を求めよ。
これはcこのテストケースからなる。

制約：1 <= c <= 5 * 10^4, 1 <= n, m <= 2 * 10^5　すべてのテストケース内での仕事数はたかだか2*10^5である。 1 <= t <= 4 * 10^10 1 <= 仕事当たりかかる時間 <= 2 * 10^5

ACするまで

1. f(x)をxの関数としてみなせば明らかに凸関数。三分探索かぁー
2. f(x)、広義単調増加と広義単調減少なんだよなぁ。。。

3. 広義単調の整数を引数にとる関数は、探索する点をうまく選ぶことで広義を消すことができる！ by Chinese Blog
4. その考えで実装してみるとあら不思議、無事にAC。何だこのテク(驚愕)

考察

komiyam.hatenadiary.org

この記事に書かれているような差分で二分探索を使う。一般的な三分探索で数列の極値を探すとき、広義単調を含んでしまうとお手上げである。
しかし、差分で二分探索をする場合、少し条件が緩い次の場合でも可能である
「極値の左右のいずれかが狭義単調増加or減少」であるとき

なぜならば、本来は傾き0はどっちの区間に属するかを判断できないが、これの仮定の下ならば、極値より左か右かを判断することがd系る。

さて、この問題の解法について。

2通りの解法があり、いずれも2分探索を使用する。
解法１：
f(x) := x分以内の課題を全部やるのにかかる時間　と定める。次のように、これは単峰性関数である。
この関数は、x=uで極値をとるとする。　x < uの時、xを増やすと、やれる仕事の数は広義単調増加する。uを超えると、t分以内ですべてのx分の仕事が終わらない可能性があるので、xを増やすにつれて、時間tの制限があるので、やれる仕事数は広義単調減少する。
凸性がありますので、三分探索をしたい気持ちになります。しかし、このままでは極値の左にも右にも傾き0の区間が存在する可能性があり、三分探索ができません。
ところで、数列上の三分探索は、差分を取ってそれを二分探索する(微分係数を求める的なことをする)ことができます。(整数列ならば、こっちの方がやれることが多い)
そして、差分で考えるとき、「極値の左or右の一方に傾き0の区間が存在しない」のならば、普段判断に困る傾き0はどちらの区間に属すべきかを一位に決められます。
今回の場合、f(x)は、明らかにx=(それぞれの仕事にかかる時間)を境に変化します。よって、探索するxを整数域ではなく、(それぞれの仕事にかかる時間)のうちのどれか(それをソートして、これの何番目かを二分探索)でやればよい。

解法２：
解法１の関数f(x)をy=f(x)のようにxy平面で考える。さきほどはxが単峰性があるとしてやっていたが、今回はy=aを動かしていく二分探索を考える。
単純に「x個を取ることができるか？」で二分探索をしてみる。ソートをすればいくつより下のものは取るべきだとわかるので、丁寧に書けば判定関数を実装可能。ちなみに、これはy=f(x)の0<=x<=uの部分の逆関数を二分探索してることにもなる。

二分探索の対象を入れ替えて(逆関数の二分探索をやってみるとか)みると実装量が変わることがある。

解法2で解くのが賢明だと思うが、解法1のこの考えも応用が利く。~~中国秘伝の香辛料って感じ。~~

ちなみにこの問題、セグメント木で殴ることもできるらしい。

ACソースコード(解法１)：
Submission #67329153 - Codeforces

ACソースコード(解法２)：
Submission #67329153 - Codeforces