← 返回题目列表

AtCoder · joiopen2022_b

B. 长颈鹿

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

キリン (Giraffes) - 原题 PDF 第 1 页
原题PDF第1页
キリン (Giraffes) - 原题 PDF 第 2 页
原题PDF第2页
キリン (Giraffes) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                  JOI Open Contest

                                                                                      July 3, 2022


                                                                            giraffes

                    キリン(Giraffes)



  IOI 動物園はキリンで有名な動物園である.この動物園ではN 頭のキリンが飼育されており,身長の低

い順に1 からN までの番号が付けられている.N 頭のキリンの身長は相異なる.また,一列に並べられ左

から順に1 からN までの番号が付けられたN 個の檻に,それぞれのキリンが1 頭ずつ分かれて生活してい
る.檻i にはキリンPi が生活している.
  IOI 動物園の園長であるAPIO 氏は,動物園のレビューに「キリンの見栄えが悪い」という理由で低評価

が多く付けられていることが気になった.具体的には,IOI 動物園の来場者がキリンの写真を撮るとき,あ

る整数l, r (1 ≦l ≦r ≦N) に対して檻l, l + 1, . . . , r のキリンが写るようにするが,以下の条件を両方とも満

たすとき,見栄えが悪くなるという.

    • 写真の両端のキリンのどちらよりも身長が高いキリンが写っている.つまり,Pl < Pk > Pr を満たす
   整数k (l < k < r) が存在する.
    • 写真の両端のキリンのどちらよりも身長が低いキリンが写っている.つまり,Pl > Pk < Pr を満たす
   整数k (l < k < r) が存在する.

 ここでAPIO 氏は,来場者がどの整数l, r (1 ≦l ≦r ≦N) を選んで写真を撮っても見栄えが悪くならない

ように,キリンの配置を変えることにした.ただし,キリンを別の檻に移動させるには手間がかかるので,

移動させるキリンの数をできるだけ少なくしたい.もちろん,キリンの移動が終了した状態でも,1 つの檻

に1 つのキリンがいなければならない.

 現在のキリンの配置の情報が与えられるので,最少で何頭のキリンを移動させる必要があるかを求めるプ

ログラムを作成せよ.なお,APIO 氏はキリンを無秩序に配置したので,Pi (1 ≦i ≦N) はランダムに生成

されると考えてよい(詳しくは入力の生成方法の項を参照せよ).


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N

      P1 P2 · · · PN


出力

 標準出力に,最少で何頭のキリンを移動させる必要があるかを1 行で出力せよ.





                        キリン– 1 / 3

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                  JOI Open Contest

                                                                                      July 3, 2022


                                                                            giraffes



制約

    • 1 ≦N ≦8 000.
    • 1 ≦Pi ≦N (1 ≦i ≦N).
    • Pi , Pj (1 ≦i <  j ≦N).
    • Pi (1 ≦i ≦N) はランダムに生成される(詳しくは入力の生成方法の項を参照せよ).


小課題

    1. (10 点) N ≦7.

    2. (22 点) N ≦13.

    3. (27 点) N ≦300.

    4. (41 点) 追加の制約はない.


入力の生成方法

 この課題では入力例を除いて,小課題1, 2, 3, 4 の制約を満たす入力ケース,小課題2, 3, 4 のみの制約を満

たす入力ケース,小課題3, 4 のみの制約を満たす入力ケース,小課題4 のみの制約を満たす入力ケースがそ

れぞれ10 個ずつある.入力例と合わせると全部で44 個のテストケースが採点に使用される.この課題に

おける44 個の入力ケースはすべて,以下の方法で生成されている.

    1. まず,N を各小課題の制約の範囲内で指定する.
    2. その後,制約を満たす(P1, P2, . . . , PN) の組み合わせN! = 1 × 2 × · · · × N 通りの中から等確率でラン
   ダムに1 つ選ぶことによってP1, P2, . . . , PN を生成する.


入出力例

  入力例1              出力例1

   6                              2

   5 4 6 1 3 2

  IOI 動物園には6 頭のキリンがおり,左の檻から順に番号5, 4, 6, 1, 3, 2 のキリンが生活している.この状

態では,例えばl = 2,r = 5 を選んで写真を撮ると見栄えが悪くなってしまう.なぜなら,以下のように見

栄えが悪くなる条件を満たすからである.




                        キリン– 2 / 3

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                  JOI Open Contest

                                                                                      July 3, 2022


                                                                            giraffes


    • 写真の左端(= 檻2)のキリンと写真の右端(= 檻5)のキリンよりも,その間にある檻3 のキリン

   の方が身長が高い.

    • 写真の左端(= 檻2)のキリンと写真の右端(= 檻5)のキリンよりも,その間にある檻4 のキリン

   の方が身長が低い.

 ここで,キリン1 を檻4 から檻1 に,キリン5 を檻1 から檻4 に移動させると,どのl, r を選んで写真を

撮っても見栄えが悪くならない.このように,2 頭のキリンを移動させることで目的を達成でき,これが最

少であるため,2 を出力する.

 この入力例はすべての小課題の制約を満たす.


  入力例2              出力例2

   4                              0

   4 1 3 2

  IOI 動物園には4 頭のキリンがおり,左の檻から順に番号4, 1, 3, 2 のキリンが生活している.この状態で

は,既にどのl, r を選んで写真を撮っても見栄えが悪くならないため,キリンの配置を変える必要はない.

よって0 を出力する.

 この入力例はすべての小課題の制約を満たす.


  入力例3              出力例3

   7                              2

   3 1 6 7 4 2 5

 例えば,左から順にキリン3, 5, 6, 7, 4, 2, 1 が並ぶようにすると,どのl, r を選んで写真を撮っても見栄え

が悪くならない.このように,2 頭のキリンを移動させることで目的を達成でき,これが最少であるため,

2 を出力する.

 この入力例はすべての小課題の制約を満たす.


  入力例4                出力例4

   13                               6

   8 5 6 13 4 2 11 3 9 1 10 7 12

 この入力例は小課題2, 3, 4 の制約を満たす.





                        キリン– 3 / 3