Problem:


ぬいぐるみの整理 (Plush Toys)

問題

ある JOI 関係者は，おもちゃ屋で働いている．今日は，店内にあるぬいぐるみコーナーの整理をすることになった．

ぬいぐるみコーナーの棚には，N 個のぬいぐるみが左から右に一列に並べられている．棚は仕切りにより N 個の区画に区切られており，1 つの区画に 1 個のぬいぐるみを置く．このおもちゃ屋は合計 M 種類のぬいぐるみを売っており，それぞれ 1 から M までの番号が付けられている．棚に並べられた N 個のぬいぐるみは，それぞれこの M 種類のうちのいずれかである．また，それぞれの種類のぬいぐるみは，少なくとも 1 個は存在する．

見栄えを良くするため，同じ種類のぬいぐるみが全て連続して棚に置かれるように，ぬいぐるみを並べ替えたい．次のような方法で，ぬいぐるみを並べ替えることにした．

N 個のぬいぐるみのうちいくつかを選び，棚から取り出す．取り出さなかったぬいぐるみの位置は動かさない．

取り出したぬいぐるみを，好きな順に棚の空いている区画に戻していく．

並べ替えた後，同じ種類のぬいぐるみが全て連続して棚に置かれていなければならない．
並べ替えるために取り出すぬいぐるみの個数の最小値を求めるプログラムを作成せよ．

入力

入力は 1 + N 行からなる．

1 行目には 2 個の整数 N, M (1 ≦ N ≦ 100000, 1 ≦ M ≦ 20) が空白を区切りとして書かれており，ぬいぐるみが N 個あり，種類が M 種類あることを表す．

続く N 行のそれぞれには，1 以上 M 以下の整数が書かれている． N 行のうちの i 行目 (1 ≦ i ≦ N) に書かれた整数は，棚の左から i 番目の区画に置かれたぬいぐるみの種類を表す．各種類について，少なくとも 1 個のぬいぐるみが存在していることが保証される．

出力

並べ替えるために取り出すぬいぐるみの個数の最小値を 1 行で出力せよ．

入出力例

入力例 1

7 2
1
2
2
2
1
2
1

出力例 1

2

入力例 2

12 4
1
3
2
4
2
1
2
3
1
1
3
4

出力例 2

7

入力例 1 においては，最初に置かれているぬいぐるみの種類は左から順に 1， 2， 2， 2， 1， 2， 1 である．並べ替えるために取り出すぬいぐるみの個数を最小にするには，左から 1 番目と 6 番目のぬいぐるみを取り出し，左から 1 番目に種類 2 のぬいぐるみを，左から 6 番目に種類 1 のぬいぐるみを配置すればよい．このとき，取り出すぬいぐるみの個数は 2 個である．

情報オリンピック日本委員会作 『第 16 回日本情報オリンピック JOI 2016/2017 予選競技課題』



Sample input:
7 2
1
2
2
2
1
2
1


Sample output:
2

Submission status: Accepted

Solution code:
def main():
  INF = 10 ** 20
  def minimum_cost(rest, h, init, dic):
    if h in dic:
      return dic[h]
  
    if not h:
      return 0
  
    ret = INF
    for nex in rest:
      accnex = acc[nex]
      cumsnex = cums[nex]
      nex_init = init + accnex
      nex_rest = rest[:]
      nex_rest.remove(nex)
      nex_h = h - 2 ** nex
      tmp =  minimum_cost(nex_rest, nex_h, nex_init, dic) +\
                     accnex - (cumsnex[nex_init] - cumsnex[init])
      if ret > tmp:
        ret = tmp
    dic[h] = ret
    return ret
  
  n, m = map(int, input().split())
  acc = [0] * m
  cums = [[0] for _ in range(m)]
  for _ in range(n):
    acc[int(input()) - 1] += 1
    for i in range(m):
      cums[i].append(acc[i])
  
  dic = {}
  h = sum([2 ** i for i in range(m)])
  print(minimum_cost([i for i in range(m)], h, 0, dic))

main()

Submission status: Accepted

Solution code:
import sys

n, m = map(int, raw_input().split())
cnt = [0 for _ in range(n)]
cntS = [[0 for _ in range(n)] for _ in range(m)]

for i in range(n):
  k = input()-1
  cnt[k] += 1
  cntS[k][i] = 1

for k in range(m):
  for i in range(n-1):
    cntS[k][i+1] += cntS[k][i]

dp = [sys.maxint/4 for _ in range(1<<m)]
dp[0] = 0

idx = [0 for _ in range(1<<m)]
for S in range((1<<m)-1):
  for i in range(m):
    if S>>i&1:
      idx[S] += cnt[i]

for S in range((1<<m)-1):
  for k in range(m):
    if not (S>>k&1):
      if idx[S]+cnt[k] <= n:
        dp[S|1<<k] = min(dp[S|1<<k], dp[S] + cnt[k]-(cntS[k][idx[S]+cnt[k]-1]-(cntS[k][idx[S]-1] if idx[S]-1>=0 else 0)))
     
print dp[(1<<m)-1]

Submission status: Accepted

Solution code:
def main():
    N,M = map(int,input().split())
    a = [int(input())-1 for _ in N*[0]]
    sum = [N*[0] for _ in 20*[0]]
    cnt = 20*[0]
    ans_bit = 0
    for i in range(N):
        ans_bit = ans_bit | (1<<a[i])
        cnt[a[i]] += 1
        sum[a[i]][i] += 1
        if i-1 >= 0:
            for j in range(20):
                sum[j][i] += sum[j][i-1]
    dp = [10**9]*(1<<20)
    dp[0] = 0
    for bit in range(1<<20):
        if( dp[bit] == 10**9 ):
            continue
        v = 0
        for used in range(20):
            if( (bit>>used) & 1 ):
                v += cnt[used]
        for use in range(20):
            if( cnt[use] == 0 ):
                continue
            if( (bit>>use) & 1 ):
                continue
            w = v + cnt[use]
            not_move = sum[use][w-1]
            if( v-1 >= 0 ):
                not_move -= sum[use][v-1]
            move = cnt[use] - not_move
            dp[bit|(1<<use)] = min(dp[bit|(1<<use)],
                                   dp[bit]+move)
    print(dp[ans_bit])
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
D = [[0]*(N+1) for i in range(M)]
cnts = [0]*M
for i in range(N):
    v = int(input())
    cnts[v-1] += 1
    D[v-1][i+1] = 1
for i in range(M):
    d = D[i]
    for j in range(1, N+1):
        d[j] += d[j-1]
memo = [None]*(2**M)
memo[2**M-1] = 0
def dfs(state, idx):
    if memo[state] is not None:
        return memo[state]
    res = N
    for i in range(M):
        if state & (1 << i) == 0:
            need = cnts[i] - (D[i][cnts[i] + idx] - D[i][idx])
            res = min(res, need + dfs(state | (1 << i), idx + cnts[i]))
    memo[state] = res
    return res
print(dfs(0, 0))

Submission status: Runtime Error

Solution code:
INF = 10 ** 20
def minimum_cost(rest, init, dic):
  if rest in dic:
    return dic[rest]

  if rest == ():
    return 0

  ret = INF
  for nex in rest:
    nex_init = init + acc[nex]
    ret = min(ret, minimum_cost(tuple(i for i in rest if i != nex), nex_init, dic) +\
                   acc[nex] - (cums[nex][nex_init] - cums[nex][init]))
  dic[rest] = ret
  return ret

n, m = map(int, input().split())
acc = [0] * m
cums = [[0] for _ in range(m)]
for _ in range(n):
  acc[int(input()) - 1] += 1
  for i in range(m):
    cums[i].append(acc[i])

dic = {}
print(minimum_cost(tuple(i for i in range(m)), 0, dic))

Submission status: Runtime Error

Solution code:
def main():
  INF = 10 ** 20
  def minimum_cost(rest, init, dic):
    if rest in dic:
      return dic[rest]
  
    if rest == ():
      return 0
  
    ret = INF
    for nex in rest:
      accnex = acc[nex]
      cumsnex = cums[nex]
      nex_init = init + accnex
      tmp =  minimum_cost(tuple([i for i in rest if i != nex]), nex_init, dic) +\
                     accnex - (cumsnex[nex_init] - cumsnex[init])
      if ret > tmp:
        ret = tmp
    dic[rest] = ret
    return ret
  
  n, m = map(int, input().split())
  acc = [0] * m
  cums = [[0] for _ in range(m)]
  for _ in range(n):
    acc[int(input()) - 1] += 1
    for i in range(m):
      cums[i].append(acc[i])
  
  dic = {}
  print(minimum_cost(tuple(i for i in range(m)), 0, dic))

main()

Submission status: Runtime Error

Solution code:
import sys

n, m = map(int, raw_input().split())
cnt = [0 for _ in range(n)]
cntS = [[0 for _ in range(n)] for _ in range(m)]

for i in range(n):
  k = input()-1
  cnt[k] += 1
  cntS[k][i] = 1

for k in range(m):
  for i in range(n-1):
    cntS[k][i+1] += cntS[k][i]

dp = [sys.maxint/4 for _ in range(1<<m)]
dp[0] = 0

for S in range((1<<m)-1):
  for k in range(m):
    if not (S>>k&1):
      idx = 0
      for i in range(m):
        if S>>i&1:
          idx += cnt[i]

      if idx+cnt[k] <= n:
        dp[S|1<<k] = min(dp[S|1<<k], dp[S] + cnt[k]-(cntS[k][idx+cnt[k]-1]-(cntS[k][idx-1] if idx-1>=0 else 0)))
     
print dp[(1<<m)-1]

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
N2 = 2**N.bit_length()
D = [[0]*(N2+1) for i in range(M)]
def get(i, k):
    data = D[i]
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def add(i, k, x):
    data = D[i]
    while k <= N2:
        data[k] += x
        k += k & -k
cnts = [0]*M
for i in range(N):
    v = int(input())
    cnts[v-1] += 1
    add(v-1, i+1, 1)
memo = {2**M-1: 0}
def dfs(state, idx):
    if state in memo:
        return memo[state]
    res = N
    for i in range(M):
        if state & (1 << i) == 0:
            need = cnts[i] - (get(i, cnts[i] + idx) - get(i, idx))
            res = min(res, need + dfs(state | (1 << i), idx + cnts[i]))
    memo[state] = res
    return res
print(dfs(0, 0))