マトロイドの定義や貪欲法の正当性についての説明は省略します．
また，自然数 \(n\) に対し \([n]\coloneqq \{1,2,\dots,n\}\) とします．

Catalan Matroid

定義

台集合 : \([2n]\)
独立集合 : 任意の \(k\in[2n]\) に対して \(2|I\cap [k]| \leq k\) が成立するような \(I\subseteq \{1,2,\dots,2n\}\)

より直感的には，各基底が長さ \(2n\)の正しいカッコ列の閉じカッコの場所に対応しているマトロイド．

マトロイドであることの証明

任意の基底 \(B_1,B_2\) と \(b_1\in B_1\setminus B_2\) について，ある \(b_2\in B_2\setminus B_1\) が存在して \(B_1-b_1+b_2\) も基底であることを示す．
// 書き中

本問題と Catalan Matroid の関係

各 \(i\in[N]\) に対し \(a_i\coloneqq 2i-1, b_i\coloneqq 2i\) とする．
\(N\) 日間の行動に対して集合 \(I\subseteq [2N]\) を以下のように作る．

\(i\) 日目に株を買う \(\Leftrightarrow a_i,b_i\not\in I\)
\(i\) 日目何もしない \(\Leftrightarrow a_i\not\in I, b_i\in I\)
\(i\) 日目に株を売る \(\Leftrightarrow a_i,b_i\in I\)

各行動に対する集合 \(I\) は明らかに台集合 \([2N]\) に対する Catalan Matroid の独立集合に含まれる．
一方で Catalan Matroid の各独立集合 \(I\) について \(S_I\coloneqq \{i\mid a_i\in I, b_i\not\in I\}\) とおくと \(I - a_S + b_S\) に対応する \(N\) 日間の行動パターンが存在する．

したがって答えは重み関数 \(w:[2N]\rightarrow \mathbb{N}\) を

\( w(a_i) = w(b_i) = P_i \)

で定めた時の基底の最大重みから \(\sum P_i\) を引いたものになる．

これはマトロイドの性質より \(P_i\) の降順に \(i\) 日目の選択を決める貪欲アルゴリズムが最適になる．
\(i\) 日目の選択が独立集合の条件を満たすかの確認は区間加算・区間最小値が行えれば実現可能で，これは遅延セグメント木でクエリあたり \(O(\log N)\) 時間で達成出来る．
提出