prithivMLmods/Coder-Stat

1 2 3 4 5<h1>ぬいぐるみの整理 (Plush Toys)</h1>6 7<h2>問題</h2>8 9<p>10ある JOI 関係者は，おもちゃ屋で働いている．今日は，店内にあるぬいぐるみコーナーの整理をすることになった．11</p>12 13<p>14ぬいぐるみコーナーの棚には，N 個のぬいぐるみが左から右に一列に並べられている．棚は仕切りにより N 個の区画に区切られており，1 つの区画に 1 個のぬいぐるみを置く．このおもちゃ屋は合計 M 種類のぬいぐるみを売っており，それぞれ 1 から M までの番号が付けられている．棚に並べられた N 個のぬいぐるみは，それぞれこの M 種類のうちのいずれかである．また，それぞれの種類のぬいぐるみは，少なくとも 1 個は存在する．15</p>16 17<p>18見栄えを良くするため，同じ種類のぬいぐるみが全て連続して棚に置かれるように，ぬいぐるみを並べ替えたい．次のような方法で，ぬいぐるみを並べ替えることにした．19</p>20 21<ul>22<li>N 個のぬいぐるみのうちいくつかを選び，棚から取り出す．取り出さなかったぬいぐるみの位置は動かさない．</li>23<li>取り出したぬいぐるみを，好きな順に棚の空いている区画に戻していく．</li>24</ul>25 26<p>27並べ替えた後，同じ種類のぬいぐるみが全て連続して棚に置かれていなければならない．28並べ替えるために取り出すぬいぐるみの個数の最小値を求めるプログラムを作成せよ．29</p>30 31<h2>入力</h2>32<p>33入力は 1 + N 行からなる．34</p>35 36<p>371 行目には 2 個の整数 N, M (1 ≦ N ≦ 100000, 1 ≦ M ≦ 20) が空白を区切りとして書かれており，ぬいぐるみが N 個あり，種類が M 種類あることを表す．38</p>39 40<p>41続く N 行のそれぞれには，1 以上 M 以下の整数が書かれている． N 行のうちの i 行目 (1 ≦ i ≦ N) に書かれた整数は，棚の左から i 番目の区画に置かれたぬいぐるみの種類を表す．各種類について，少なくとも 1 個のぬいぐるみが存在していることが保証される．42</p>43 44<h2>出力</h2>45<p>46並べ替えるために取り出すぬいぐるみの個数の最小値を 1 行で出力せよ．47</p>48 49<h2>入出力例</h2>50 51<h3>入力例 1</h3>52<pre>537 254155256257258159260161</pre>62 63<h3>出力例 1</h3>64<pre>65266</pre>67<br/>68 69<h3>入力例 2</h3>70<pre>7112 472173374275476277178279380181182383484</pre>85<h3>出力例 2</h3>86 87<pre>88789</pre>90 91<br/>92 93<p>94入力例 1 においては，最初に置かれているぬいぐるみの種類は左から順に 1， 2， 2， 2， 1， 2， 1 である．並べ替えるために取り出すぬいぐるみの個数を最小にするには，左から 1 番目と 6 番目のぬいぐるみを取り出し，左から 1 番目に種類 2 のぬいぐるみを，左から 6 番目に種類 1 のぬいぐるみを配置すればよい．このとき，取り出すぬいぐるみの個数は 2 個である．95</p>96 97<br/>98<div class="source">99<p class="source">100<a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/80x15.png"/></a>101</p>102<p class="source">103<a href="https://www.ioi-jp.org/joi/2016/2017-yo/index.html">情報オリンピック日本委員会作 『第 16 回日本情報オリンピック JOI 2016/2017 予選競技課題』</a>104</p>105</div>106