順列

E. LISDL | AtCoder Regular Contest 091

問題Pは順列|P| = NLIS(P) = ALDS(P) = BPを求めよ(ないかも)1<=N,A,B<=3*10^5 解説 LISとLDSで重複している要素はたかだか1つなのでA + B <= N + 1Nが大きすぎると駄目で最大のケースで例えばA=2, B=3とするとN = A*B=6で3, 2, 1, 6, 5, 4のように構成でき…

E. Max History | Educational Codeforces #38

すべての順列を見ていくのは明らかに無理なので、a[j]ごとに計算していく。つまり、f[a] = f[a] + a[M(もとの配列の添字はj)] となるような順列を数える。その数えをg(j)としておく。g(j)さえ求まれば解はΣa[j]g(j) a[j]より大きい値の数えをx, a[j]以上値の…