E - Bounding Box Editorial by enjapma


部分点解法

この問題で求めるべき最適値の式が、(最大値 \(-\) 最小値)の形になっていることに注意すれば、この問題の答えは以下の問題の答えと同じになります。

問題E’: \(N\) 点の中から \(K\) 点を選び、さらにその中から \(4\)\(p_0, p_1, p_2, p_3\) を定める(これらは重複していても構わない)。このとき、\(\sum c_i\) \(+\)\(p_0\)\(x\) 座標)\(+\)\(p_1\)\(y\) 座標)\(-\)\(p_2\)\(x\) 座標)\(-\)\(p_3\)\(y\) 座標) の値の最大値を出力せよ。

よって、以上の問題を解くような動的計画法を適用すれば良いです。具体的には、 「\(dp[i][j][p_0][p_1][p_2][p_3]\) := \(i\) 個目までの点の中から \(j\) 個選んでいて、\(p_0, p_1, p_2, p_3\) を選んだ or 選んでいない(Bool値)ときの値」のような DP テーブルを定義し、更新すれば良いです。

計算量は、定数倍に \(3^4\) などがかかる \(O(NK)\) です。


満点解法

部分点解法で定義した DP テーブルに注目すると、\(p_0, p_1, p_2, p_3\) として選ぶ \(4\) 点以外は、\(c_i\) の値が上位の順に選んでいけば良いことが分かります。

よって、\(c_i\) の値を降順に並べた上で、部分点解法と同じような動的計画法を行えば良いです。ただし今回は、\(c_i\) の上位 \(K - 4\) 個を必ず選ぶことにして、これらについては個数に数えないことで、dpの第二引数の上限を \(4\) に抑えられます。

計算量は、ソートする部分が最も重く、\(O(N \log N)\) です。

posted:
last update: