NPCA Summer Contest 2014 問6 - 蝉ヌード(Cicada Nude)

問題文 : Cicada Nude

catupper 先生から問題利用の許可を得たので去った 9 月 10 日の PCK 対策コンテストに出題していました.

ところでこの問題では $O(n^2)$ の DP が出来るのですが, 実は $n \leqq 10^5$ でも解ける問題となっています (ということを catupper 先生が言っていました).
で, 解き方を聞いてしまったのですが解説を書いている人がいない(!) のでせっかくなのでブログに載せます. catupper 先生すごい.

解法

木 $i$ から木 $j$ への移動が可能であるなら, 不等式

$$T_j - T_i \geq |A_j - A_i|$$

が成り立ちます. ここで, $|A_j - A_i| = \text{max}(A_i - A_j, A_j - A_i)$ であることを思い出すと, 上の不等式は

$$T_j - T_i \geq A_i - A_j ∧ T_j - T_i \geq A_j - A_i$$

と言い換えられることがわかります. 更に式変形をすることで, $i,\ j$ が辺々で独立な 2 つの不等式

$$T_j + A_j \geq T_i + A_i ∧ T_j - A_j \geq T_i - A_i$$

が成立しないといけないことがわかります. これは 2 次元の点 $(T_k + A_k, T_k - A_k)$ を考えた時の 2 次元 LIS の問題に帰着します. しれっと 45 度回転が出ているのがめちゃ面白い.

2 次元の LIS は片方の座標をソートした上で 1 次元で$O(n \log n)$ の LIS-DP をすると計算できるので, 全体の計算量は $O(n \log n)$ になります.

コード

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    pair<int, int> p[3000];
    
    scanf("%d", &n);
    
    int ctr = 0;
    for (int i = 0; i < n; i++){
        int a, t;
        scanf("%d %d", &a, &t);
        if (a <= t) p[ctr++] = make_pair(t - a, t + a);
    }
    
    sort(p, p + ctr);
    
    int dp[3000];
    
    fill(dp, dp + ctr, 1000000000);
    
    for (int i = 0; i < ctr; i++){
        *lower_bound(dp, dp + ctr, p[i].second) = p[i].second;
    }
    
    printf("%d\n", lower_bound(dp, dp + ctr, 1000000000) - dp);
    
    return (0);
}

今年のアドベントカレンダー, 45 度回転ネタで記事を書いてみようかなーと思います.
この問題だと結果として 45 度回転が出て来ていますが, 絶対値やマンハッタン距離が出て来た時は 45 度回転を疑うのはアリですね...