#1191910 (C++23(gcc16)) No.209 Longest Mountain Subsequence

• 問題: No.209 Longest Mountain Subsequence
• ユーザー: C
• 提出日時: 2026-10-07 23:51:16
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 19 ms / 2,000 ms
• コード長: 2,279 bytes
• コンパイル時間: 5,571 ms
• コンパイル使用メモリ: 396,036 KB
• 実行使用メモリ: 9,808 KB
• 最終ジャッジ日時: 2026-10-21 16:26:04
• 合計ジャッジ時間: 7,050 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 8

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;

using mint=modint;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

vi solve(vi a){
  int n=sz(a);
  vi ord(n);
  iota(all(ord),0);
  sort(all(ord),[&](int i,int j){
    if(a[i]!=a[j])return a[i]<a[j];
    else return i<j;
  });
  vvi dp(n,vi(n,0));
  vi ans(n,1);
  rep(p,0,n){
    vi pre;
    rrep(i,0,n){
      int h=ord[i];
      if(h<p&&a[h]<a[p])pre.push_back(h);
    }
    vi nxt;
    rep(i,0,n){
      int q=ord[i];
      if(q>p&&a[q]>a[p])nxt.push_back(q);
    }
    int h=0,mx=0;
    for(auto q:nxt){
      ll thresh=2ll*a[p]-a[q];
      while(h<sz(pre)&&a[pre[h]]>thresh){
        mx=max(mx,dp[pre[h]][p]);
        ++h;
      }
      dp[p][q]=max(2,mx+1);
      ans[q]=max(ans[q],dp[p][q]);
    }
  }
  return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

  /*
    O(N^2)
    片側だけ考える。
    dp[p][q]を「最後の2点がp,qの凸増加部分列の最大長」とする。
    h->p->q と遷移する条件は
    a[p]-a[h] < a[q]-a[p] <=> a[h] > 2*a[p]-a[q]。

    pを固定すると、qをa[q]の昇順で見るほど閾値 2*a[p]-a[q] は単調減少する。
    そこで候補hをa[h]の降順に並べ、条件を満たしたhを順に追加しながら
    max dp[h][p]だけ持つ。各hは高々1回追加されるので、一つpはO(N)で処理できる。

    右側は配列を反転して同じ処理をし、各頂点iについて l[i]+r[i]-1 を取る。
  */

    int T;
    cin>>T;
    while(T--){
      int N;
      cin>>N;
      vi a(N);
      rep(i,0,N)cin>>a[i];
      vi l=solve(a);
      reverse(all(a));
      vi r=solve(a);
      reverse(all(r));
      int ans=1;
      rep(i,0,N){
        ans=max(ans,l[i]+r[i]-1);
      }
      cout<<ans<<'\n';
    }

}