解説サブタスク1では各候補に対して他の建物をすべて調べる。時間計算量は O(∑N2)O(\sum N^2)O(∑N2) で、N≤100N\leq100N≤100、∑N≤1000\sum N\leq1000∑N≤1000 なら十分である。 全体では LX=max(A1,⋯ ,AX−1)L_X=\max(A_1,\cdots,A_{X-1})LX=max(A1,⋯,A、 とする。左が空なら 、右が空なら を使う。左の条件は 、右の条件は と同値なので、両方を満たす位置を数えれば正しい。右側の最小値を後ろから前計算し、前から走査しながら左側の最大値を更新する。同じ高さも許されるため等号を含める。時間は 、追加領域は 。保存する値は 以下、答えは 以下である。 Solution written by GPT6.1
