問題一覧 > 通常問題

No.1867 Partitions and Inversions

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : CyanmondCyanmond / テスター : ForestedForested ぷらぷら shiomusubi496shiomusubi496
4 ProblemId : 7356 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-04 23:50:30

問題文

整数 $N$ と $(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ が与えられます。$k = 1, 2, \cdots , N$ について次の問題を解いてください。

あなたは $P$ に対して次の操作を $1$ 度だけ行います。

  1. まず、次の条件を満たす長さ $k+1$ の整数列 $A = (A_1, A_2, \ldots, A_{k+1})$ を作る。

    • $1 = A_1 < A_2 < \cdots < A_{k+1} = N+1$

  2. その後、各 $i = 1, 2, \ldots, k$ について、 $P_{A_i}\ , P_{A_i + 1}\ , \ldots, P_{A_{i+1} - 1}$ を昇順に並び替える。

操作を終えた後の $P$ の転倒数としてあり得る値のうち最小となるものを求めて下さい。

ここで、各問題は独立であり、操作は他の問題には影響しないことに注意してください。

  • 転倒数の定義 (クリックで展開します)
    •

    長さ $N$ の数列 $P$ に対して、以下をすべて満たす整数組 $(a, b)$ の個数を転倒数と定義します。

    • $1 \leq a < b \leq N$
    • $P_a > P_b$

    入力

    $N$
$P_1$ $P_2$ $\cdots$ $P_N$
    • 入力は全て整数
    • $1 \leq N \leq 3000$
    • $P$ は $(1, 2, \ldots, N)$ の順列

    出力

    $N$ 行出力してください。$i$ 行目には、$k = i$ の場合の答えを出力してください。

    サンプル

    サンプル1
    入力
    5
2 4 3 5 1
    出力
    0
1
3
4
5

    $k=3$ の場合を例として挙げます。
    $A = (1, 2, 3, 6)$ とした場合、最終的に $P$ は $(2, 4, 1, 3, 5)$ になります。この $P$ の転倒数は $3$ です。この選び方は最適なものの $1$ つです。

    サンプル2
    入力
    6
1 2 3 4 5 6
    出力
    0
0
0
0
0
0

    始めから $P$ の転倒数は $0$ であり、どんな $k$ に対しても答えは $0$ となります。

    サンプル3
    入力
    15
7 13 6 2 12 11 10 4 8 15 9 14 5 3 1
    出力
    0
6
17
22
23
31
38
44
46
49
54
57
60
62
63

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。