2次元平面上にn点が与えられている。どの2点をとってもx座標は等しくない。どの2点をとってもy座標は等しくない。Cが/の関係になっている組の数は何個あるかを計算します.これにはAより右上にあるそれぞれの点Bに対して,Bより右上にある点が何個あるかを求め,それをすべて足さなければなりません.すなわたい2重ループです.点が300000個あるので,n**2の計算はできません.これをどう解消するかがこの問題のポイントなのだと思います.それぞれの点について「自分より右上にある点の数」を保存しておく事は出来ます,これは後で使うかもしれないので念頭に置いておきます.真ん中の点を用いて数え上げる/の関係になっている3つ組全体の個数を数え上げるときにΣを2回計算しなければならないのは,左下の点について分類している為です。川が平行に並んでいて、川と川の間には直線の道路がある。川の幅は川ごとに異なる。2次元座標を適当に置くと、川はy軸に平行な帯状領域で、道路はy軸に平行な直線と思える。そのために要する最短時間を求めよ。川内では自由な方向に移動できるが、道路は細いためy軸方向のみ移動できる。道路を移動する速度はすべての道路で共通だが、川内を移動する速度は川ごとに異なる。川から道路への移動と道路から川への移動はy座標が整数の点でのみ行える。問題を簡単にするまず、道路を移動するスピードはどこでも同じなので、徒歩での移動するのは一番右端の道路でのみ行うことにします。本当にこの簡単化が効果的かはわかりませんが、とりあえずやっておきます。動的計画法なのはすぐわかるけれどdp[i][a]を、i番目の川を渡り終え、y座標がaの位置に達するのに要する最短時間とします。dp[i][*]達からdp[i+1][*]達が計算でき、また求めるべき答えはdp[N][L]なのでこのdpを更新する動的計画法で答えが求まります。問題なのはdpの更新をナイーブに行うと時間がかかってしまう点です。dp[i+1][y]は、y以下の非負整数aに対してdp[i][a]+(aからyまで川を移動する)を計算し、その最小値を取れば計算できます。この方法ではdp[i+1][*]達の計算にはO(L**2)です。Lが10**6程度なので、1回の更新だけでも制限時間を超えてしまいます。高速の高速化を考えるそこで、この更新をもっと速くできないかと考えます。自分が探した範囲だと少なくとも2通りの方法が有りました。1つ目の方法は最小値を達成できない可能性を分割統治法を用いて枝狩りし、2つ目の方法は目的関数の凸性を用いて探索範囲を狭めています。最初に挙げた自分の提出コード(と入っても他の方の回答のほぼ丸写しですが...)は前者の方法を用いています。以下ではその方法を解説します。後で良く使うので、以下の記号を用います。川の左端でy座標がaの点から、右端でbの点まで泳ぐのに要する時間。y)をaの変数と見た時の最小値です。L/2)の最小値をy=a0で達成したとします。L]の地点に泳いで移動する方法ではdp[i+1][z]の最小値を達成できない」。今L/2に到達するために泳いだ直線を横切るような泳ぎ方は最適ではありません。これの証明は後で行います。L/2]に移動する方法)も最適な経路でないことがわかります。L]の移動だけを調べれば十分となります。