問題一覧 > 通常問題

No.1867 Partitions and Inversions

レベル : / AI推定難易度 : 2425 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : Cyanmond / テスター : 👑 Forested ぷら shiomusubi496
お気に入りにしたユーザー ProblemId : 7356 / 自分の提出
問題文最終更新日: 2022-03-04 23:50:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 334 (順位表) の他の問題:

Problem Statement

You are given an integer $N$ and a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$. For each $k = 1, 2, \cdots , N$, solve the following problem.

You perform the following operation on $P$ exactly $1$ time.

  1. First, create an integer sequence $A = (A_1, A_2, \ldots, A_{k+1})$ of length $k+1$ satisfying the following condition.

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

  2. Then, for each $i = 1, 2, \ldots, k$, sort $P_{A_i}\ , P_{A_i + 1}\ , \ldots, P_{A_{i+1} - 1}$ in ascending order.

Find the minimum possible value of the inversion number of $P$ after the operation.

Note that the problems are independent, and an operation does not affect the other problems.

  • Definition of the inversion number (click to expand)
  • For a sequence $P$ of length $N$, the inversion number is defined as the number of integer pairs $(a, b)$ satisfying all of the following.

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

    Input

    $N$
    $P_1$ $P_2$ $\cdots$ $P_N$
    
    • All inputs are integers.
    • $1 \leq N \leq 3000$
    • $P$ is a permutation of $(1, 2, \ldots, N)$.

    Output

    Print $N$ lines. On the $i$-th line, print the answer for the case $k = i$.

    Sample

    Sample 1
    Input
    5
    2 4 3 5 1
    
    Output
    0
    1
    3
    4
    5

    Consider the case $k=3$ as an example.
    If $A = (1, 2, 3, 6)$, then $P$ finally becomes $(2, 4, 1, 3, 5)$. The inversion number of this $P$ is $3$. This choice is $1$ of the optimal ones.

    Sample 2
    Input
    6
    1 2 3 4 5 6
    Output
    0
    0
    0
    0
    0
    0

    The inversion number of $P$ is $0$ from the beginning, so the answer is $0$ for any $k$.

    Sample 3
    Input
    15
    7 13 6 2 12 11 10 4 8 15 9 14 5 3 1
    Output
    0
    6
    17
    22
    23
    31
    38
    44
    46
    49
    54
    57
    60
    62
    63

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