まずはD問題と同じ次のようなDPを考えます。

\(DP[t][x][y] = \) 高橋君が時刻 \(t\) に座標 \((x,y)\) にいるときの、それまでに捕まえたすぬけ君の大きさの合計の最大値

このとき、遷移は以下の通りになります。
\(DP[t][x][y]=\max\{DP[t'][x'][y']\mid y'\leq y,\ |x-x'|+y-y'\leq t-t'\}+ \text{時刻 } t \text{ に座標 } (x,y) \text{ にいることで捕まえることができるすぬけ君の大きさ}\)

maxの中の条件式の2つ目は以下のように変形できます。
\(|x-x'|+y-y'\leq t-t' \Longleftrightarrow x-x'+y-y'\leq t-t' \text{ かつ } -(x-x')+y-y'\leq t-t'\)

これらはさらに次のように変形できます。
\(x-x'+y-y'\leq t-t' \Longleftrightarrow t'-x'-y'\leq t-x-y\)
\(-(x-x')+y-y'\leq t-t' \Longleftrightarrow t'+x'-y'\leq t+x-y\)

ここで \(a=t-x-y, \ b=t+x-y\) として \((t,x,y)\mapsto(a,b,y)\) と変数変換することで
\(DP[a][b][y]=\max\{DP[a'][b'][y']\mid a'\leq a,\ b'\leq b,\ y'\leq y\}+ \text{時刻 } t \text{ に座標 } (x,y) \text{ にいることで捕まえることができるすぬけ君の大きさ}\)
となり、maxを取る範囲を単純な形で表すことができました。

DPテーブルはすぬけ君が出てくる \((a,b,y)\) に関してだけを持てば十分です。したがって、\(y\) に関して平面走査を行うことで、\(2\) 次元領域のmaxクエリを高速に処理することができればこの問題を解くことができます。必要なところだけ作る \(2\) 次元セグメントツリー(セグ木onセグ木)や分割統治法などを用いてクエリあたり \(O((\log N)^2)\) で求めることができるため、この問題は \(O(N(\log N)^2)\) で解くことができます。

実装例(C++) 2D Binary Indexed Tree (BIT on BIT)

2次元セグメントツリーについて

次の問題を考えます。

\(Q\) 個のクエリを処理せよ。クエリは以下の \(2\) 種類：

• setクエリ：\((x,y)\) に重み \(w\) の点を置く。
• getクエリ：領域 \([L,R]\times[D,U]\) の内部にある点の重みのmaxを求める。

クエリ先読み＋座標圧縮により、座標の範囲は \([0,Q]\) としてよいです。
この問題は \(2\) 次元セグメントツリーを用いて解くことができます。\(2\) 次元セグメントツリーでは各ノードにセグメントツリーを持たせます。つまり、\(1\) 次元のセグメントツリーであれば各ノードが「区間 \([L,R]\) の区間max」を持つところ、\(2\) 次元セグメントツリーでは「領域 \([L,R]×[*,*]\) の領域maxを取得できるセグメントツリー」を持ちます。
そのままでは、サイズ \(Q\) のセグメントツリーを \(Q\) 個持つことになり、空間計算量が \(O(Q^2)\) となりますが、単位元でない値が入っているノードだけを作ることで、空間計算量は \(O(Q(\log Q)^2)\) になります。
setクエリでは \(O(\log Q)\) 個のセグ木を更新するので、クエリの処理は \(O((\log Q)^2)\) 時間でできます。同様に、getクエリでは \(O(\log Q)\) 個のセグ木で区間maxを計算するので、 \(O((\log Q)^2)\) の時間で処理できます。

分割統治法について

次の問題を考えます。

\(Q\) 個のクエリを処理せよ。クエリは以下の \(2\) 種類：

• setクエリ：\((x,y)\) に重み \(w\) の点を置く。
• getクエリ：領域 \([0,R]\times[0,U]\) の内部にある点の重みのmaxを求める。

もしこの問題において、全てのsetクエリが全てのgetクエリより先にあれば、クエリ先読み＋座標圧縮＋平面走査により \(O(Q\log Q)\) で解くことができます。そこで、もとの問題において、クエリ群を前半と後半の2つに分け、次のような分割統治法を考えます。

• 1.前半のクエリを(再帰的に)処理する
• 2.前半のsetクエリに対する後半getクエリを処理する
• 3.(前半のクエリは存在しないものとして)後半のクエリを(再帰的に)処理する

前半のgetクエリに対する答えは1で、後半のgetクエリに対する答えは2と3の結果を合わせることで得られます。

\(Q\) 個のクエリを処理するのにかかる時間を \(T(Q)\) とすると、\(T(Q)=2T(Q/2)+O(Q\log Q)\) となることから、\(T(Q)=O(Q(\log Q)^2)\) となることがわかります。