D - ありんこ / CODE FESTIVAL 2015 あさぷろ Hard
問題
考察
(！: よりシンプルな解法が記事の下のほうにあります！)
蟻本の蟻の問題を彷彿とさせる問題設定です。
この問題をややこしくしているポイントとして、各アリの速度がそれぞれ異なるというのがあります。そのため各アリごとに最初に衝突するアリが明らかではなく、状況の把握が困難です。
しかし、全体で最初に衝突するのは、最初に棒上で隣り合っているアリのペアです（元々隣り合っていなかったアリのペアだとすると、隣り合うアリが入れ替わる時点でより早い衝突が起きたことになります。下の図参照）。
なので全体で最初の衝突を考える限りは、各アリが進行方向で最近のアリに衝突すると思い込んでも問題なく、状況が把握しやすくなります。
ところで、この問題のような「何らかの最小値を最大化する問題」では、解を二分探索する方針がしばしば効果的です。この問題で解を二分探索すると「ある値 x について、K 匹以下のアリを取り除くことで最初にアリが衝突する時間を x 以上にできるか？」という問題を繰り返し解くことに換言されます。
結論から言えば、この換言された問題は動的計画法を用いて解くことができます。
DP[i] (1 ≦ i ≦ N) を、「左から i 番目までのアリだけを考えたときに、最初にアリが衝突する時間を x 以上にするために取り除く必要のある（ただしちょうど i 番目のアリは残す）アリの匹数の最小値」と定義します。DP[i] の値を、j < i なる DP[j] の値を用いて計算することが目標です。
残すアリを右から見て、i 番目のアリの次に残すアリの番号で場合分けをします。i の次に残すアリの番号が j である場合を考えます。
まず大前提として、i 番目のアリと j 番目のアリが衝突するまでの時間が x 以上である必要があります。この前提は成り立っているとき、この場合における、取り除く必要のあるアリの匹数の最小値は、「DP[j] + (i 番目のアリと j 番目のアリの間にいるアリの匹数)」になります（冒頭で述べた性質より、j 番目より左側に残すアリと i 番目のアリとの衝突は考えなくていいことに注意します）。
このような方針をナイーブに実装する（全ての j を素直に 1 つずつ調べる）と、全体で二乗の計算量がかかります。DP の遷移を高速化できないか考えてみます。
まず注目すべきなのは、「i 番目のアリと j 番目のアリが衝突するまでの時間は x 以上か？」という問いには、それぞれのアリの初期位置と速度から定まる値を比較することで簡単に答えることができる、という点です。具体的には、
a[i] = (i 番目のアリの初期位置) + x * (i 番目のアリの速度)
と定めたとき、上の問いの答えが YES になる条件は a[i] ≧ a[j] になることです（衝突時間を x 以上とおいた式を式変形すれば分かります）。
また新しく
DP'[i] = DP[i] + (N - i)
と定めると、
DP[i] = max{DP'[j] | j < i, i 番目のアリと j 番目のアリが衝突するまでの時間は x 以上} - (N - i + 1)
と、遷移のコストが j に依存しなくなり、単純な max 演算で DP[i] の値を計算できるようになります。
以上 2 つの性質を考えると、DP の遷移を高速化（1 つの i あたり O(log N)）することができます。つまり、まずあらかじめ a[i] の値が小さい順に（並び順とは別の）番号を振っておきます。そしてこの番号で添字付けたセグメントツリーに各 DP'[i] の値を載せていけば、DP[i] の値はこのセグメントツリーに対する RMQ の結果を用いて高速に計算できます。
二分探索とセグメントツリーで 2 つの log が付くので、けっこう TL がシビアです。
（！: ここから別の解法）
実は（？）こんなに面倒なことをしなくても問題を解くことができます。
まず二分探索はするとして、「アリの最初の衝突までの時間を x 以上にできるか？」を考えます。ここで、各アリ i の x 秒後の位置が p[i] だとします。すると、p が含む増加部分列に対応するアリを残した場合、x 秒後までにアリの衝突は起きないことが分かります。従って p の LIS を求めて、これが長さ N - K 以上であれば OK です。
（解法を教えてくださったすぬけさん、ありがとうございます m(_ _)m）
