Problem:


 連鎖 

問題

次のようなゲームがある．

あるキャラクターが縦 1 列に N 個並んでいる．これらのキャラクターの色は赤，青，黄のいずれかであり，初期状態で同じ色のキャラクターが4つ以上連続して並んでいることはない．プレーヤーは，ある位置のキャラクターを選び他の色に変更することができる．この操作により同じ色のキャラクターが4つ以上連続して並ぶとそれらのキャラクターは消滅する．キャラクターが消滅することにより新たに同じ色のキャラクターが4つ以上連続して並ぶとそれらのキャラクターも消滅し，同じ色のキャラクターが4つ以上連続して並んでいる箇所がなくなるまでこの連鎖は続く．このゲームの目的は，消滅しないで残っているキャラクター数をなるべく少なくすることである．

例えば，下図の左端の状態で，上から6番目のキャラクターの色を黄色から青に変更すると，青のキャラクターが5つ連続するので消滅し，最終的に3つのキャラクターが消滅せずに残る． 

初期状態における N 個のキャラクターの色の並びが与えられたとき， 1箇所だけキャラクターの色を変更した場合の，消滅しないで残っているキャラクター数の最小値 M を求めるプログラムを作成せよ．

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

1行目はキャラクター数 N (1 ≤ N ≤ 10000) だけからなる．続く N 行には 1, 2, 3 のいずれか1つの整数が書かれており， i + 1 行目 (1 ≤ i ≤ N) は初期状態における上から i 番目のキャラクターの色を表す（1 は赤を，2 は青を，3は黄を表す）．

N が 0 のとき入力の終了を示す．データセットの数は 5 を超えない．

出力

データセットごとに, 消滅しないで残っているキャラクター数の最小値 M を１行に出力せよ．

入出力例

入力例

12
3
2
1
1
2
3
2
2
2
1
1
3
12
3
2
1
1
2
3
2
1
3
2
1
3
0

出力例

3
12

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
12
3
2
1
1
2
3
2
2
2
1
1
3
12
3
2
1
1
2
3
2
1
3
2
1
3
0


Sample output:
3
12

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if not n:
        break

    puyos = []
    pre = int(input())
    cnt = 1
    for _ in range(n - 1):
        p = int(input())
        if pre != p:
            puyos.append((pre, cnt))
            pre = p
            cnt = 0
        cnt += 1
    puyos.append((pre, cnt))
    lp = len(puyos)

    min_puyo = n
    for i, puyo in enumerate(puyos):
        color, num = puyo
        if num > 1:
            continue
        tn, j = n, 1
        while True:
            if i - j < 0 or i + j >= lp:
                break
            tp_c, tp_n = puyos[i - j]
            up_c, up_n = puyos[i + j]
            if tp_c != up_c:
                break
            dp = tp_n + up_n + int(j == 1)
            if dp < 4:
                break
            tn -= dp
            j += 1
        if min_puyo > tn:
            min_puyo = tn
    print(min_puyo)

Submission status: Wrong Answer

Solution code:
INF = 100000
while True:
  n = int(input())
  if not n: break
  lst = [int(input()) for _ in range(n)]

  def check(x):
    c1 = c2 = lst[x]
    l = r = x
    b = 0
    for i in range(r, n):
      if lst[i] != c2:
        r = i - 1
        break
    else:
      r = i

    for i in range(l, -1, -1):
      if lst[i] != c1:
        l = i + 1
        break
    else:
      l = i

    if r - l - b < 3:
      return n
    else:
      b = r - l
    while l > 0 and r < n - 1:
      c1 = lst[l - 1]
      c2 = lst[r + 1]
      if c1 != c2:
        break
      else:
        for i in range(r + 1,n):
          if lst[i] != c2:
            r = i - 1
            break
        else:
          r = i
           
        for i in range(l - 1, -1, -1):
          if lst[i] != c1:
            l = i + 1
            break
        else:
          l = i

        if r - l - b < 3:
          break
        else:
          b = r - l
    return n - (r - l + 1)

  ans = INF
  for i in range(n):
    lst[i] = (lst[i] + 1) % 3
    ans = min(ans, check(i))
    lst[i] = (lst[i] + 1) % 3
    ans = min(ans, check(i))
    lst[i] = (lst[i] + 1) % 3
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def product4(a):
    return a[0]*a[1]*a[2]*a[3]

def puyo(a):
    ans = len(a)
    while True:
        ans = len(a)
        for i in range(len(a)-3):
            if a[i] == a[i+1] == a[i+2] == a[i+3]:
                hit = a[i]
                ren = 3
                while i+ren+1 < len(a):
                    if a[i+ren+1] != hit: break
                    ren += 1
                del a[i:i+ren+1]
                break
        else:
            break
    return ans

while True:
    n = int(input())
    if n==0: break

    cha = []
    for i in range(n):
        cha.append(int(input()))

    ans = n
    for i in range(len(cha)-3):
        chain = cha.copy()
        if product4(chain[i:i+4]) in [2,3,8,24,27,54]:
            hit = chain[i]
            if hit == chain[i+1]:
                chain[i+2] = chain[i+3] = hit
            elif hit == chain[i+2]:
                chain[i+1] = hit
            else:
                chain[i] = chain[i+1]
            ans = min(ans,puyo(chain))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
for e in iter(input,'0'):
 n=m=int(e);a=[input()for _ in[0]*n]
 for i in range(n):
  for j in {*'123'}-{a[i]}:
   b=a[:i]+[j]+a[i+1:]
   f=1
   while f:
    s=t=f=0;c=b[0]
    for k in range(1,len(b)):
     if b[k]==c:t=k
     elif t-s>2:f=1;break
     else:s=t=k;c=b[k]
    if f:b=b[:s]+b[t+1:]
   m=min(m,len(b))
 print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
r=sys.stdin.readline
for e in iter(r,'0\n'):
 n=m=int(e);a=[r()for _ in[0]*n]
 for i in range(n):
  for j in {*'123'}-{a[i]}:
   b=a[:i]+[j]+a[i+1:]
   f=1
   while f:
    s=t=f=0;c=b[0]
    for k in range(1,len(b)):
     if b[k]==c:t=k
     elif t-s>2:f=1;break
     else:s=t=k;c=b[k]
    if f:b=b[:s]+b[t+1:]
   m=min(m,len(b))
 print(m)

Submission status: Time Limit Exceeded

Solution code:
def g():
 import sys
 r=sys.stdin.readline
 for e in iter(r,'0\n'):
  n=m=int(e);a=[r()for _ in[0]*n]
  for i in range(n):
   for j in {*'123'}-{a[i]}:
    b=a[:i]+[j]+a[i+1:]
    f=1
    while f:
     s=t=f=0;c=b[0]
     for k in range(1,len(b)):
      if b[k]==c:t=k
      elif t-s>2:f=1;break
      else:s=t=k;c=b[k]
     if f:b=b[:s]+b[t+1:]
    m=min(m,len(b))
  print(m)
if'__main__'==__name__:g()

Submission status: Time Limit Exceeded

Solution code:
def g():
 import sys
 r=sys.stdin.readline
 for e in iter(r,'0\n'):
  n,m=int(e),[];a=[r()for _ in[0]*n]
  for i in range(n):
   for j in {*'123'}-{a[i]}:
    b=a[:i]+[j]+a[i+1:]
    f=1
    while f:
     s=t=f=0;c=b[0]
     for k in range(1,len(b)):
      if b[k]==c:t=k
      elif t-s>2:f=1;break
      else:s=t=k;c=b[k]
     if f:b=b[:s]+b[t+1:]
    m+=[len(b)]
  print(min(m))
if'__main__'==__name__:g()

Submission status: Time Limit Exceeded

Solution code:
for e in iter(input,'0'):
 n=m=int(e);a=[input()for _ in[0]*n]
 for i in range(n):
  for j in{*'123'}-{a[i]}:
   b=a[:i]+[j]+a[i+1:]
   f=1
   while f:
    s=t=f=0;c=b[0]
    while t<len(b):
     t=len(b)
     for x in{*'123'}-{c}:
      if x in b[s+1:]:t=min(t,b.index(x,s+1))
     if t-s>3:t-=1;f=1;b=b[:s]+b[t+1:];break
     elif t==len(b):break
     else:s,c=t,b[t]
   m=min(m,len(b))
 print(m)

Submission status: Time Limit Exceeded

Solution code:
w={*'123'}
for e in iter(input,'0'):
 n=m=int(e);a=[input()for _ in[0]*n]
 for i in range(n):
  for j in w-{a[i]}:
   b=a[:i]+[j]+a[i+1:]
   f=1
   while f:
    s=t=f=0;c=b[0]
    while t<len(b):
     t=len(b)
     for x in w-{c}:
      if x in b[s+1:]:t=min(t,b.index(x,s+1))
     if t-s>3:t-=1;f=1;b=b[:s]+b[t+1:];break
     elif t==len(b):break
     else:s,c=t,b[t]
   m=min(m,len(b))
 print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
r=sys.stdin.readline
w={*'123'}
for e in iter(r,'0\n'):
 n=m=int(e);a=[r()[:-1]for _ in[0]*n]
 for i in range(n):
  for j in w-{a[i]}:
   b=a[:i]+[j]+a[i+1:]
   f=1
   while f:
    s=t=f=0;c=b[0]
    while t<len(b):
     t=len(b)
     for x in w-{c}:
      if x in b[s+1:]:t=min(t,b.index(x,s+1))
     if t-s>3:t-=1;f=1;b=b[:s]+b[t+1:];break
     elif t==len(b):break
     else:s,c=t,b[t]
   m=min(m,len(b))
 print(m)

Submission status: Time Limit Exceeded

Solution code:
def g():
 import sys
 r=sys.stdin.readline
 w={*'123'}
 for e in iter(r,'0\n'):
  n=m=int(e);a=[r()[:-1]for _ in[0]*n]
  for i in range(n):
   for j in w-{a[i]}:
    b=a[:i]+[j]+a[i+1:]
    f=1
    while f:
     s=t=f=0;c=b[0]
     while t<len(b):
      t=len(b)
      for x in w-{c}:
       if x in b[s+1:]:t=min(t,b.index(x,s+1))
      if t-s>3:t-=1;f=1;b=b[:s]+b[t+1:];break
      elif t==len(b):break
      else:s,c=t,b[t]
    m=min(m,len(b))
  print(m)
if __name__ == '__main__':
    g()

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if not n:
        break

    puyos = []
    pre = int(input())
    cnt = 1
    for _ in range(n - 1):
        p = int(input())
        if pre != p:
            puyos.append((pre, cnt))
            pre = p
            cnt = 0
        cnt += 1
    puyos.append((pre, cnt))
    lp = len(puyos)

    min_puyo = n
    for i, puyo in enumerate(puyos):
        color, num = puyo
        if num == 2:
            continue
        tn, j = n, 1
        while True:
            if i - j < 0 or i + j >= lp:
                break

            tp_c, tp_n = puyos[i - j]
            up_c, up_n = puyos[i + j]
            if tp_c != up_c:
                break

            first_adjust = 0
            if j == 1:
                if num == 1:
                    first_adjust = 1
                else:
                    first_adjust = -1
                    tn -= 4

            dp = tp_n + up_n + first_adjust
            if dp < 4:
                break
            tn -= dp
            j += 1
        if min_puyo > tn:
            min_puyo = tn
    print(min_puyo)

Submission status: Accepted

Solution code:
INF = 100000
while True:
  n = int(input())
  if not n: break
  lst = [int(input()) for _ in range(n)]

  def check(x):
    c1 = c2 = lst[x]
    l = r = x
    b = 0
    for i in range(r, n):
      if lst[i] != c2:
        r = i - 1
        break
    else:
      r = n - 1

    for i in range(l, -1, -1):
      if lst[i] != c1:
        l = i + 1
        break
    else:
      l = 0

    if r - l - b < 3:
      return n
    else:
      b = r - l

    while l > 0 and r < n - 1:
      c1 = lst[l - 1]
      c2 = lst[r + 1]
      if c1 != c2:
        break
      else:
        for i in range(r + 1,n):
          if lst[i] != c2:
            r = i - 1
            break
        else:
          r = n - 1
           
        for i in range(l - 1, -1, -1):
          if lst[i] != c1:
            l = i + 1
            break
        else:
          l = 0

        if r - l - b < 4:
          break
        else:
          b = r - l
    return n - (b + 1)

  ans = INF
  for i in range(n):
    lst[i] = (lst[i] + 1) % 3 + 1
    ans = min(ans, check(i))
    lst[i] = (lst[i] + 1) % 3 + 1
    ans = min(ans, check(i))
    lst[i] = (lst[i] + 1) % 3 + 1
  print(ans)

Submission status: Accepted

Solution code:
def solve():
  INF = 100000
  while True:
    n = int(input())
    if not n: break
    lst = [int(input()) for _ in range(n)]
  
    def check(x):
      c1 = c2 = lst[x]
      l = r = x
      b = 0
      for i in range(r, n):
        if lst[i] != c2:
          r = i - 1
          break
      else:
        r = n - 1
  
      for i in range(l, -1, -1):
        if lst[i] != c1:
          l = i + 1
          break
      else:
        l = 0
  
      if r - l - b < 3:
        return n
      else:
        b = r - l
  
      while l > 0 and r < n - 1:
        c1 = lst[l - 1]
        c2 = lst[r + 1]
        if c1 != c2:
          break
        else:
          for i in range(r + 1,n):
            if lst[i] != c2:
              r = i - 1
              break
          else:
            r = n - 1
             
          for i in range(l - 1, -1, -1):
            if lst[i] != c1:
              l = i + 1
              break
          else:
            l = 0
  
          if r - l - b < 4:
            break
          else:
            b = r - l
      return n - (b + 1)
  
    ans = INF
    for i in range(n):
      lst[i] = (lst[i] + 1) % 3 + 1
      ans = min(ans, check(i))
      lst[i] = (lst[i] + 1) % 3 + 1
      ans = min(ans, check(i))
      lst[i] = (lst[i] + 1) % 3 + 1
    print(ans)
solve()

Submission status: Accepted

Solution code:
def solve():
  INF = 100000
  while True:
    n = int(input())
    if not n: break
    lst = [int(input()) for _ in range(n)]
  
    def check(x):
      c = lst[x]
      l = r = x
      b = 0
      for i in range(r, n):
        if lst[i] != c:
          r = i - 1
          break
      else:
        r = n - 1
  
      for i in range(l, -1, -1):
        if lst[i] != c:
          l = i + 1
          break
      else:
        l = 0
  
      if r - l - b < 3:
        return n
      else:
        b = r - l
  
      while l > 0 and r < n - 1:
        c = lst[l - 1]
        if c != lst[r + 1]:
          break
        else:
          for i in range(r + 1,n):
            if lst[i] != c:
              r = i - 1
              break
          else:
            r = n - 1
             
          for i in range(l - 1, -1, -1):
            if lst[i] != c:
              l = i + 1
              break
          else:
            l = 0
  
          if r - l - b < 4:
            break
          else:
            b = r - l
      return n - (b + 1)
  
    ans = INF
    for i in range(n):
      lst[i] = (lst[i]) % 3 + 1
      ans = min(ans, check(i))
      lst[i] = (lst[i]) % 3 + 1
      ans = min(ans, check(i))
      lst[i] = (lst[i]) % 3 + 1
    print(ans)
solve()

Submission status: Accepted

Solution code:
def doChain(ar, si, ei):
	p, c = 0, []  #p:ar[i]のcolor, c:4連続以上のarのindex
	for i in range(si, ei):
		if ar[i]==p:
			c.append(i)
			if i==len(ar)-1 and len(c)>=4:
				del ar[min(c):max(c)+1]
				return True, max(0, si-3),min(ei+5, len(ar))
		else:
			if len(c)>=4:
				del ar[min(c):max(c)+1]
				return True, max(0, si-3),min(ei+5, len(ar))
			p = ar[i]
			c = [i]
	return False, 0, len(ar)


while True:
	N = int(input())
	if N==0: break
	A = [int(input()) for _ in range(N)]
	minvalue = N
	for j in range(len(A)-1):
		B = A[:]
		if B[j+1]!=B[j]:
			B[j+1] = B[j]
			result = True
			si, ei = max(0, j-3), min(j+5, len(A))
			while result==True:
				result, si, ei = doChain(B, si, ei)
				if len(B)<minvalue:
					minvalue = len(B)

	print(minvalue)

Submission status: Accepted

Solution code:
def cara(n):
	kazu=[]
	ilo=[]
	a=int(input())
	una=a
	kazu.append(1)
	ilo.append(a)
	for n in range(n-1):
		a=int(input())
		if una==a:
			kazu[-1]+=1
		else:
			kazu.append(1)
			ilo.append(a)
			una=a
	return ilo,kazu
def kes(ilo,kazu):
	k=10000
	unanseer=sum(kazu)
	anseer=sum(kazu)
	for p in range(len(ilo)):
		n=0
		if kazu[p]>=3 :
			anseer=kurabe(ilo,kazu,p)
		n=0
		if p+2 < len(ilo) and ilo[p]==ilo[p+2] and kazu[p]+kazu[p+2]>=3 and kazu[p+1]==1:
			while p+2+n<len(ilo) and p-n>=0 and ilo[p-n]==ilo[p+2+n] and kazu[p-n]+kazu[p+2+n]>=4:
				n+=1
			if n>2500:
				print(n)
			unanseer=kensa(ilo,kazu,n,p)
		if unanseer<anseer:
			anseer=unanseer
		if anseer<k: 
			k=anseer
	return k
def kensa(ilo,kazu,n,p):
	k=0
	if n==0:
		for w in range(len(kazu)):
			k+=kazu[w]
	else:
		for q in range(0,p-n+1):
			k+=kazu[q]
		for i in range(p+2+n,len(kazu)):
			k+=kazu[i]
	return k
def kurabe(ilo,kazu,p):
	n=0
	a=0
	b=0
	k=0
	
	#上からもらう
	if p+1 < len(ilo):
		kazu[p+1]-=1
		kazu[p]+=1
		while 0<p-a and len(kazu)>p+1+a and ilo[p+1+a]==ilo[p-1-a] and kazu[p+1+a]+kazu[p-1-a]>=4:
			a+=1
		kazu[p+1]+=1
		kazu[p]-=1

	#下からもらう
	if p-1 >= 0:
		kazu[p-1]-=1
		kazu[p]+=1
		while len(kazu)>p+1+b and 0<p-b and ilo[p+b+1]==ilo[p-1-b] and kazu[p+b+1]+kazu[p-1-b]>=4:
			b+=1
		kazu[p-1]+=1
		kazu[p]-=1
	if a<b:
		n=b
	else:
		n=a
	for q in range(0,p-n):
			k+=kazu[q]
	for i in range(p+n,len(kazu)):
			k+=kazu[i]
	k-=3
	return k

while True:
	n=int(input())
	if n==0:
		break
	ilo,kazu=cara(n)
	print(kes(ilo,kazu))

Submission status: Accepted

Solution code:
# p周辺の4つは消えることが前提
def erase(array, i, N):
    if array[i - 1] == array[i]:
        up = i - 1
        down = i
    elif array[i] == array[i + 1]:
        up = i
        down = i + 1
    else:
        return N - 2

    while True:
        if array[up] == -1 or array[down] == -1 or not array[up] == array[down]:
            return up + N - down - 1
        save_up = up
        save_down = down
        c = array[up]
        while array[up] == c:
            up -= 1
        while array[down] == c:
            down += 1

        if save_up - up + down - save_down < 4:
            return save_up + N - save_down - 1



def main():
    while True:
        N = int(input())
        if N == 0:
            return
        a = [-1]
        for i in range(N):
            a.append(int(input()))
        a.append(-1)

        min_erased = N
        for i in range(1, N + 1):
            save = a[i]
            a[i] = save % 3 + 1
            min_erased = min(min_erased, erase(a, i, N + 2))
            a[i] = (save + 1) % 3 + 1
            min_erased = min(min_erased, erase(a, i, N + 2))
            a[i] = save

        print(min_erased)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def myinput(n):
	C=[int(input())]
	L=[1]
	for i in range(1,n):
		c = int(input())
		if C[-1] == c:
			L[-1]+=1
		else:
			C.append(c)
			L.append(1)
	return [C,L]

def check(C,L,low, hih):
	m = len(C)
	ret = 0
	if 0<=low and L[low]>=4 and (hih>=m or C[low] != C[hih]):
		ret += L[low]
		low -= 1
	if hih<m and L[hih]>=4 and (low<0 or C[low] != C[hih]):
		ret += L[hih]
		hih += 1
	while 0 <= low and hih < m and C[low] == C[hih] and L[low] + L[hih] >= 4:
		ret += L[low] + L[hih]
		low -= 1
		hih += 1
	return ret

def solve(C,L):
	m = len(C)
	ret = 0
	for i in range(m):
		L[i]-=1
		if i+1 < m:
			L[i+1]+=1
			if L[i]>0:
				ret = max(ret, check(C, L, i  , i+1))
			else:
				ret = max(ret, check(C, L, i-1, i+1))
			L[i+1]-=1
		if i-1 >= 0:
			L[i-1]+=1
			if L[i]>0:
				ret = max(ret, check(C, L, i-1, i))
			else:
				ret = max(ret, check(C, L, i-1, i+1))
			L[i-1]-=1
		L[i]+=1
	return ret

while True:
	n = int(input())
	if n == 0:
		break
	C,L = myinput(n)
	print(n - solve(C,L))

Submission status: Runtime Error

Solution code:
def product4(a):
    return a[0]*a[1]*a[2]*a[3]

def puyo(a):
    ans = len(a)
    for i in range(len(a)-3):
        if a[i] == a[i+1] == a[i+2] == a[i+3]:
            hit = a[i]
            ren = 3
            while i+ren+1 < len(a):
                if a[i+ren+1] != hit: break
                ren += 1
            ans = min(ans, puyo(a[:i]+a[i+ren+1:]))
    return ans

while True:
    n = int(input())
    if n==0: break

    cha = []
    for i in range(n):
        cha.append(int(input()))

    ans = n
    for i in range(len(cha)-3):
        chain = cha.copy()
        if product4(chain[i:i+4]) in [2,3,8,24,27,54]:
            hit = chain[i]
            if hit == chain[i+1]:
                chain[i+2] = chain[i+3] = hit
            elif hit == chain[i+2]:
                chain[i+1] = hit
            else:
                chain[i] = chain[i+1]
        ans = min(ans,puyo(chain))
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
r=sys.stdin.readline
w={*'123'}
for e in iter(r,'0'):
 n=m=int(e);a=[r()for _ in[0]*n]
 for i in range(n):
  for j in w-{a[i]}:
   b=a[:i]+[j]+a[i+1:]
   f=1
   while f:
    s=t=f=0;c=b[0]
    while t<len(b):
     t=len(b)
     for x in w-{c}:
      if x in b[s+1:]:t=min(t,b.index(x,s+1))
     if t-s>3:t-=1;f=1;b=b[:s]+b[t+1:];break
     elif t==len(b):break
     else:s,c=t,b[t]
   m=min(m,len(b))
 print(m)