日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392）F,G問題メモ

比較的全完しやすい回だった。

F - Insert

空の配列 $A$ があります。 $i=1,2,\ldots,N$ の順に以下の操作を行います。
数 $i$ を、 $A$ の前から $P_i$ 番目の位置になるように挿入する。
- より正確には、「 $A$ の $P_i-1$ 項目まで」「 $i$ 」「 $A$ の $P_i$ 項目以降」をこの順に連結したもので $A$ を置き換える。

以下の例で考えてみる。

i   1 2 3 4 5 6
P   1 2 2 1 3 2

■A の作られ過程
1   1
2   1 2
3   1 3 2
4   4 1 3 2
5   4 1 5 3 2
6   4 6 1 5 3 2

わかりやすいところでは、例えば最後の $i=6$ は、挿入後、（最後なので当然）自身の前に割り込む要素がないので、最終状態でも $P_6=2$ の示す通り、先頭から2番目の位置に置かれている。

$i=5$ は、挿入後、 $i=6$ という1つの要素に割り込まれるので、最終状態では $P_5+1=4$ 番目に置かれている。
基本的には $i$ が大きい方が、自身の処理後に割り込む候補となる数が少ないので、考えやすそうである。

$i$ の大きい方から処理することを考えると、以下のような問題に言い換えることができる。

i   1 2 3 4 5 6
P   1 2 2 1 3 2

6   _ 6 _ _ _ _
5   _ 6 _ 5 _ _
4   4 6 _ 5 _ _
3   4 6 _ 5 3 _
2   4 6 _ 5 3 2
1   4 6 1 5 3 2

SortedSetなど、「 $i$ 番目の要素を取得する」「要素 $x$ を消す」という2つの処理を行えるデータ構造で実現できる。
最初、 $S=\{1,2,...,N\}$ としておいて、 $i$ ごとに以下をすればよい。

整数 $A,B,C$ ( $A \lt B \lt C$ ) が $B-A = C-B$ を満たす時、 $(A,B,C)$ を良い三つ組と呼びます。
$N$ 要素からなる正整数の集合 $S=\{ S_1,S_2,\dots,S_N \}$ が与えられるので、 $A,B,C \in S$ なる良い三つ組の個数を求めてください。

仮に以下が分かっていたとすると、

$B$ を固定したときの良い三つ組の個数は、 $P[2B]$ で取得できる。

そして $P$ は畳み込みで求められる。

$F$ 同士を畳み込んだ数列を $G$ とすると、 $G[i]=2P[i]+\alpha$ となる。
$\alpha$ は、 $i=2B$ となる $B$ が $S$ に含まれる場合 $1$ 、それ以外は $0$ となる変数とする。

（ $(A,C),(C,A)$ で2回数えられる分と、 $(B,B)$ 自身が1回数えられている分）

ここから $P$ が求められる。