Problem:


ロシアの旗 (Russian Flag)

  問題

K 理事長はロシアで開催される IOI 2016 に合わせて旗を作ることにした．K 理事長はまず倉庫から古い旗を取り出してきた．この旗は N 行 M 列のマス目に分けられていて，それぞれのマスには白・青・赤のいずれかの色が塗られている．

K 理事長はこの旗のいくつかのマスを塗り替えてロシアの旗にしようとしている．ただし，この問題でいうロシアの旗とは以下のようなものである．

上から何行か (1 行以上) のマスが全て白で塗られている．

続く何行か (1 行以上) のマスが全て青で塗られている．

それ以外の行 (1 行以上) のマスが全て赤で塗られている．

K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を求めよ．

 入力

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

1 行目には，2 つの整数 N, M (3 ≦ N ≦ 50, 3 ≦ M ≦ 50) が空白を区切りとして書かれている．これは，旗が N 行 M 列のマス目に区切られていることを表す．

続く N 行にはそれぞれ M 文字からなる文字列が書かれており，古い旗のマス目に塗られている色の情報を表す．N 行のうちの i 行目の j 文字目 (1 ≦ i ≦ N, 1 ≦ j ≦ M) は，古い旗のマス目の i 行目 j 列目のマスの色を表す 'W', 'B', 'R' のいずれかの文字である．
'W' は白，'B' は青，'R' は赤を表す．

  出力

K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を 1 行で出力せよ．

  入出力例

入力例 1

  

4 5
WRWRW
BWRWB
WRWRW
RWBWR

  
出力例 1

   

11

入力例 2

  

6 14
WWWWWWWWWWWWWW
WBBBWWRRWWBBBW
WWBWWRRRRWWBWW
BWBWWRRRRWWBWW
WBBWWWRRWWBBBW
WWWWWWWWWWWWWW

  
出力例 2

  

44

入出力例 1 において，古い旗には下図のように色が塗られている．

下図において，'X' の書かれた 11 個のマスを塗り替える．

 
これにより下図のようなロシアの旗にすることができる．

11 個未満のマスを塗り替えることではロシアの旗にすることはできないため，11 を出力する．

入出力例 2 においては，古い旗には下図のように色が塗られている．

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



Sample input:
4 5
WRWRW
BWRWB
WRWRW
RWBWR


Sample output:
11

Submission status: Wrong Answer

Solution code:
def differ(i,ss):
  tos = ["W","B","R"]
  count = 0
  for j in ss:
    if (j != tos[i]):
      count += 1
  return count
[n,m] = list(map(int,input().split()))
ls = []
for i in range(n):
  ls.append(input())
dp = [[0 for i in range(50)] for i in range(3)]
dp[0][0] = differ(0,ls[0])
for i in range(3):
  for j in range(n):
    if j == 0:
      if i == 0:
        dp[i][j] = differ(0,ls[0])
      else:
        dp[i][j] = 100
    if i == 0:
      dp[i][j] = dp[i][j-1] + differ(i,ls[j])
    else:
      dp[i][j] = min(dp[i-1][j-1] + differ(i,ls[j]),dp[i][j-1] + differ(i,ls[j]))
print(dp[2][n-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
w = []
b = []
r = []
for i in range(n):
  s = input()
  w.append(m - s.count("W"))
  b.append(m - s.count("B"))
  r.append(m - s.count("R"))
ans = 3000
for i in range(1, n - 1):
  for j in range(i, n - 1):
    ans = min(ans, sum(w[:i]) + sum(b[i:j+1]) + sum(r[j + 1:]))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

N, M = list(map(int, input().split(' ')))
colors = []
for i in range(N):
    row = list(input())
    row_color = [0, 0, 0]
    for c in row:
        if c == 'W': row_color[0] += 1
        elif c == 'B': row_color[1] += 1
        elif c == 'R': row_color[2] += 1
    colors.append(row_color)

min_diff = float('inf')
for blue_top in range(1, N-1):
    for red_top in range(blue_top+1, N):
        diff = 0
        for i in range(N):
            if i < blue_top:
                diff += colors[i][1] + colors[i][2]
            elif i < red_top:
                diff += colors[i][0] + colors[i][2]
            else:
                diff += colors[i][0] + colors[i][1]
        if diff < min_diff:
            min_diff = diff

print(min_diff)

Submission status: Accepted

Solution code:
def differ(i,ss):
  tos = ["W","B","R"]
  count = 0
  for j in ss:
    if (j != tos[i]):
      count += 1
  return count
[n,m] = list(map(int,input().split()))
ls = []
for i in range(n):
  ls.append(input())
dp = [[0 for i in range(50)] for i in range(3)]
dp[0][0] = differ(0,ls[0])
for i in range(3):
  for j in range(n):
    if j == 0:
      if i == 0:
        dp[i][j] = differ(0,ls[0])
      else:
        dp[i][j] = 100000
    elif i == 0:
      dp[i][j] = dp[i][j-1] + differ(i,ls[j])
    else:
      dp[i][j] = min(dp[i-1][j-1] + differ(i,ls[j]),dp[i][j-1] + differ(i,ls[j]))
print(dp[2][n-1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
f_lis = []
for i in range(n):
    f_lis.append(list(str(input())))

ans_lis = []

W_num = []
W_cou = 0
B_num = []
B_cou = 0
R_num = []
R_cou = 0

for k in range(0,n):
    W_cou += f_lis[k].count('B') + f_lis[k].count('R')
    W_num.append(W_cou)
for k in range(0,n):
    B_cou += f_lis[k].count('W') + f_lis[k].count('R')
    B_num.append(B_cou)
for k in range(0,n):
    R_cou += f_lis[k].count('B') + f_lis[k].count('W')
    R_num.append(R_cou)

for i in range(1,n - 1):
    for j in range(i + 1,n):
        ans_lis.append(W_num[i - 1] + B_num[j - 1] - B_num[i - 1] + R_num[n - 1] - R_num[j - 1])
        
            
print(min(ans_lis))

Submission status: Accepted

Solution code:
h,w=[int(s)for s in input().split(" ")]
flag=[input()for i in range(h)]
mincnt=1145141919810
for i in range(1,h-1):
    for j in range(1,h-i):
        cnt=0
        wr=flag[:i]
        br=flag[i:i+j]
        rr=flag[i+j:]
        for l in wr:
            for c in l:
                if c!='W':cnt+=1
        for l in br:
            for c in l:
                if c!='B':cnt+=1
        for l in rr:
            for c in l:
                if c!='R':cnt+=1
        if cnt<mincnt:
            mincnt=cnt
print(mincnt)

Submission status: Accepted

Solution code:
str_N_M = input()
N, M = map(int, str_N_M.split(' '))

old_flag = []
for i in range(1, N + 1):
    old_flag.append(input())

X = 2500
for white_row in range(1, N - 1):
    for blue_row in range(white_row + 1, N):
        paint_square = 0

        for row in old_flag[:white_row]:
            list_row_w = list(row)
            for moji_w in list_row_w:
                if moji_w == 'B' or moji_w == 'R':
                    paint_square += 1

        for row in old_flag[white_row : blue_row]:
            list_row_b = list(row)
            for moji_z in list_row_b:
               if moji_z == 'W' or moji_z == 'R':
                   paint_square += 1

        for row in old_flag[blue_row:]:
            list_row_r = list(row)
            for moji_r in list_row_r:
                if moji_r == 'B' or moji_r == 'W':
                    paint_square += 1

        if paint_square < X:
            X = paint_square

print(X)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
f = [0 for _ in range(h)]
for i in range(h):
    f[i] = input()
cw = [f[i].count("W") for i in range(h)]
cb = [f[i].count("B") for i in range(h)]
cr = [f[i].count("R") for i in range(h)]
count = h * w
for i in range(1, h - 1):
    for j in range(i, h):
        count = min(count,h * w - sum(cw[:i]) - sum(cb[i:j]) - sum(cr[j:]))
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

flag = []
for _ in range(n):
    string = list(input())
    flag.append(string)

ans = 10**9
for white in range(1, n-1):
    for blue in range(1, n-1):
        red = n - white - blue
        if red <= 0:
            continue

        cnt = 0
        for i in range(white):
            for j in range(m):
                if flag[i][j] != "W":
                    cnt += 1

        for i in range(blue):
            for j in range(m):
                if flag[white+i][j] != "B":
                    cnt += 1

        for i in range(red):
            for j in range(m):
                if flag[white+blue+i][j] != "R":
                    cnt += 1

        if ans > cnt:
            ans = cnt

print(ans)

Submission status: Accepted

Solution code:
def getPaintCount(string, color):
	return len(string)-string.count(color)


N, M = map(int, input().split())
A = []
cnt = 0
for i in range(N):
	s = input().strip()
	if i==0:  #1行目は白
		cnt += getPaintCount(s, 'W')
	elif i==N-1:  #最終行は赤
		cnt += getPaintCount(s, 'R')
	else:
		A.append(s)  #N-2行のリスト

B = []  #白、青、赤の行数の組み合わせリスト
for w in range(0, N-1):  #白は0からN-3行の可能性
	for b in range(1, N-w):  #青は1からN-2行の可能性
		r = N-2-w-b
		if r>=0: B.append([w, b, N-2-w-b])
#print(B)
minmin = 2500
cnt2 = 0
for b in B:
	for i in range(len(A)):
		if i<b[0]:
			cnt2 += getPaintCount(A[i], 'W')
		elif b[0]<=i<b[0]+b[1]:
			cnt2 += getPaintCount(A[i], 'B')
		elif b[0]+b[1]<=i<b[0]+b[1]+b[2]:
			cnt2 += getPaintCount(A[i], 'R')
	if cnt2<minmin:
		minmin = cnt2
	cnt2 = 0

print(cnt+minmin)

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split(" ")]

blue=[0]
white=[0]
red=[0]
for i in range(N):
    S=input()
    blue.append(M-S.count("B")+blue[-1])
    white.append(M-S.count("W")+white[-1])
    red.append(M-S.count("R")+red[-1])

def paint(i,j):
    retval=0
    retval+=white[i]-white[0]
    retval+=blue[j]-blue[i]
    retval+=red[N]-red[j]
    return retval

retval=10**10
for i in range(1,N):
    for j in range(i+1,N):
        retval=min(paint(i,j),retval)

print(retval)

Submission status: Accepted

Solution code:
#C
inf = float("inf")
N,M = map(int,input().split())
flag = [list(str(input())) for i in range(N)]
WBR = []

for i in range(N):
    w = flag[i].count("W")
    b = flag[i].count("B")
    r = flag[i].count("R")
    WBR.append([w,b,r])
    
    
ans = inf
for w in range(N-2):
    for b in range(N-1):
        if w >= b:
            pass
        else:
            kari = 0
            for i in range(N):
                if i <= w:
                    kari+=(M-WBR[i][0])
                elif i <= b:
                    kari+=(M-WBR[i][1])
                else:
                    kari+=(M-WBR[i][2])
            ans = min(ans,kari)
                    
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
flag=[list(input()) for _ in range(n)]
w=[]
b=[]
r=[]
for i in flag:
    w.append(i.count('W'))
    b.append(i.count('B'))
    r.append(i.count('R'))
ans=10**18
for x in range(1,n-1):
    for y in range(x+1,n):
        ans=min(ans,sum(b[:x])+sum(r[:x])+sum(w[x:y])+sum(r[x:y])+sum(w[y:])+sum(b[y:]))
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

flag = []
for _ in range(n):
    string = list(input())
    flag.append(string)

ans = 10**9
for white in range(1, n-1):
    for blue in range(1, n-1):
        red = n - white - blue
        if red <= 0:
            continue

        cnt = 0
        for i in range(white):
            for j in range(m):
                if flag[i][j] != "W":
                    cnt += 1

        for i in range(blue):
            for j in range(m):
                if flag[white+i][j] != "B":
                    cnt += 1

        for i in range(red):
            for j in range(m):
                if flag[white+blue+i][j] != "R":
                    cnt += 1

        if ans > cnt:
            ans = cnt

print(ans)

Submission status: Accepted

Solution code:
inf = 10**20
n,m = map(int, input().split())
flist = []
wbrnum = {}
for i in range(n):
    a = list(str(input()))
    flist.append(a)
    b = []
    b.append(a.count('W'))
    b.append(a.count('B'))
    b.append(a.count('R'))
    wbrnum[i] = b
cnt = inf
for i in range(n-2):
    cnti = 0
    for l in range(i+1):
        cnti += (wbrnum[l][1]+wbrnum[l][2])
    for j in range(i+1,n-1):
        cntj = 0
        cnto = 0
        for o in range(i+1,j+1):
            cntj += (wbrnum[o][0]+wbrnum[o][2])
        for o in range(j+1,n):
            cnto += (wbrnum[o][0]+wbrnum[o][1])
        cnt = min(cnt,(cnti+cntj+cnto))
        #print(i,j,cnti,cntj,cnto,cnt)
print(cnt)