Problem:


Score : 300 points

Problem Statement

There are N stones arranged in a row. Every stone is painted white or black.
A string S represents the color of the stones. The i-th stone from the left is white if the i-th character of S is ., and the stone is black if the character is #.

Takahashi wants to change the colors of some stones to black or white so that there will be no white stone immediately to the right of a black stone.
Find the minimum number of stones that needs to be recolored.

Constraints

1 \leq N \leq 2\times 10^5

S is a string of length N consisting of . and #.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the minimum number of stones that needs to be recolored.

Sample Input 1

3
#.#

Sample Output 1

1

It is enough to change the color of the first stone to white.

Sample Input 2

5
#.##.

Sample Output 2

2

Sample Input 3

9
.........

Sample Output 3

0



Sample input:
3
#.#


Sample output:
1

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = list(input())[: -1]
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + (s[i] == "#")
res = float("inf")
for i in range(N + 1):
  r = cs[-1] - cs[i]
  l = i - cs[i]
  res = min(res, N - i - r + i - l)
print(res)

Submission status: Accepted

Solution code:
from copy import copy
class imos1d:
  def __init__(self, src):
    self.d = [0]
    self.d += copy(src)
    for i in range(len(src)):
      self.d[i+1] += self.d[i]
  
  def query(self, l, r):
    return self.d[r] - self.d[l]
  
N = int(input())
S = input()
B = [ 1 if s == '#' else 0 for s in S ]
W = [ 0 if B[i] else 1 for i in range(len(B)) ]
Bi = imos1d(B)
Wi = imos1d(W)
# print(Bi.d)
# print(Wi.d)
ans = N
for i in range(0, N+1):
  ans = min(ans,
            N - Wi.query(0, i)- Bi.query(i, N))
  # print(N - Wi.query(0, i)- Bi.query(i, N))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s=input()
if ('.' not in s) or ('#' not in s):
    print(0)
    exit()
bc = [0 for i in range(n)]
wc = [0 for i in range(n)]
for i in range(n):
  if s[i] == '#':
    bc[i] = 1
  else:
    wc[i] = 1
for i in range(n-1):
  bc[i+1] += bc[i]
for i in range(n-1,0,-1):
  wc[i-1] += wc[i]
ans = min(wc[0],bc[-1])
for i in range(n-1):
  ans = min(ans,bc[i]+wc[i+1])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s=input()
if ('.' not in s) or ('#' not in s):
    print(0)
else:
    bc = [0 for i in range(n)]
    wc = [0 for i in range(n)]
    for i in range(n):
        if s[i] == '#':
            bc[i] =1
        else:
            wc[i] = 1
    for i in range(n-1):
        bc[i+1] += bc[i]
    for i in range(n-1,0,-1):
        wc[i-1] += wc[i]
    ans = min(wc[0],bc[-1])
    for i in range(n-1):
        ans = min(ans,bc[i]+wc[i+1])
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
use=[0 if S[i]=="." else 1 for i in range(N)]
now=[0 for i in range(N)]
count=sum(use)
lst=set()
lst.add(count)


for i in range(N-1,-1,-1):
    now[i]=1
    if use[i]:
        use[i]=0
        count-=1
    else:
        use[i]=1
        count+=1
    lst.add(count)
print(min(lst))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
c = s.count(".")
ans = c
for i in range(n):
    if s[i] =="#":
        c +=1
    else:
        c -=1
    ans = min(ans,c)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
cnt=0
black=[0]*N
white=[0]*N
for i in range(N):
    if S[i]==".":
        white[i]=1
    else:
        black[i]=1
    if i>=1:
        white[i]+=white[i-1]
        black[i]+=black[i-1]
        
B=black[-1]
W=white[-1]

ans=min(B,W)
for i in range(1,N):
    num=black[i-1]+W-white[i-1]
    ans=min(ans,num)
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
sl = list(input())

bl = [0]
wl = [0]
a = 0
b = 0
for s in sl:
   if s == "#":
      b += 1
   if s == ".":
      a += 1
   bl.append(a)
   wl.append(b)

ans = float("inf")
for i in range(n):
   tmp = wl[i+1] + bl[-1] - bl[i+1]
   ans = min(ans, tmp)

ans = min(wl[-1],ans)
ans = min(bl[-1],ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
sum_b = [0]
sum_w = [0]
b = 0
w = 0

for s in S:
    if s == "#":
        b += 1
    else:
        w += 1
    # 白黒の累積和作る
    sum_b.append(b)
    sum_w.append(w)

ans = float("inf")
for i in range(N + 1):
    # i番目までにある黒をすべて白にし、それ以降の白をすべて黒にするのに必要な手数
    buf = sum_b[i] + (sum_w[-1] - sum_w[i])
    # 更新するか否か
    ans = min(ans, buf)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
tmp=0
for i in range(n):
  if s[i]==".":
    tmp+=1
ans=tmp
for i in range(n):
  if s[i]==".":
    tmp-=1
  else:
    tmp+=1
  ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()

I=[0]*N
I[0]=1 if S[0]=='#' else 0
for i in range(1,N):
    I[i]=I[i-1]+(1 if S[i]=='#' else 0)

ans=N
for i in range(N+1):
    LB = 0 if i==0 else I[i-1]
    RW = 0 if i==N else N-i - (I[N-1]-(0 if i==0 else I[i-1]))
    ans=min(ans,LB+RW)

print(ans)

Submission status: Accepted

Solution code:

N = int(input())

S = input()

ans = float("inf")

lb = 0
rw = 0

for i in range(N):
    if S[i] == ".":
        rw += 1

for i in range(N+1):

    ans = min(ans , lb + rw)

    if i == N:
        break

    if S[i] == "#":
        lb += 1
    else:
        rw -= 1

print (ans)

Submission status: Accepted

Solution code:
import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)

n = int(input())
l = input()

#print(l)
lsh = []*(n+1)
lsh.append(0)
sharp = 0
comma = 0

for i in range(n):
	if l[i]=="#":
		sharp = sharp + 1
	lsh.append(sharp)
#print(lsh)

for i in range(n-1,-1,-1):
	#print(i)
	if l[i]==".":
		comma = comma + 1
	lsh[i] = lsh[i] + comma

print(min(lsh))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

bl, wl = 0, 0
br, wr = S.count('#'), S.count('.')
ret = min(br, wr)
for s in S :
  ret = min(ret, bl + wr)
  if s == '#' :
    bl += 1
    br -= 1
  else :
    wl += 1
    wr -= 1
    
print(ret)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
w = S.count('.')
b, i = 0, 0
ans = w
for s in S:
    if s == '.':
        w -= 1
    else:
        b += 1
    ans = min(ans, w+b)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
b=0
h=S.count(".")
m=h
for i in range (len(S)):
    if(S[i]=="#"):
        b+=1
    else:
        h-=1
    if(m>(b+h)):
        m=(b+h)
print(m)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

cnt = 10 ** 9
W = s.count(".")
w = 0
b = 0
for i, j in enumerate(s):
    cnt = min(cnt, b + W - w)
    if j == "#":
        b += 1
    else:
        w += 1
print(min(cnt, b + W - w))

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
S = input()

if N == 2:
    if S == '#.':
        print(1)
    else:
        print(0)
    exit()

s = [1 if i == '#' else 0 for i in S]
a = list(accumulate(s))
b = list(reversed(list(accumulate(reversed(s)))))
answer = N
for i in range(1, N - 1):
    tmp = a[i] + N - i - 1 - b[i]
    if tmp < answer:
        answer = tmp

answer = min(answer, a[-1], N - a[-1])
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()
    ans = 0
    x = 0
    for c in S:
        if c == "#":
            x += 1
        else:
            if x > 0:
                ans += 1
                x = max(x-1, 0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
b,w,ans=0,0,0
w=S.count('.')
ans=w
for i in S:
	if i=='#':b+=1
	else:w-=1
	ans=min(b+w,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
s = input()

btow = [0 for _ in range(N+1)]
wtob = [0 for _ in range(N+1)]

for i in range(N):
    if s[i]=='#':
        btow[i+1]=btow[i]+1
    else:
        btow[i+1]=btow[i]
    if s[-1-i]=='.':
        wtob[i+1]=wtob[i]+1
    else:
        wtob[i+1]=wtob[i]

ans = float('inf')

for i in range(N+1):
    ans = min(ans,btow[i]+wtob[-1-i])

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
w = [0 for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
  b[i] = (0 if i==0 else b[i-1]) + (s[i]=='#')
  w[n-1-i] = (0 if i==0 else w[n-i]) + (s[n-1-i]=='.')
ans = 10000000000
for i in range(n+1):
  ans = min(ans, (0 if i==0 else b[i-1]) + (0 if i==n else w[i]))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
dp = [ [0]*n for _ in range(2) ]
if s[0] == ".":
  dp[1][0] = 1
else:
  dp[0][0] = 1
for i in range(n-1):
  if s[i+1] == ".":
    dp[0][i+1] = dp[0][i]
    dp[1][i+1] = min(dp[0][i], dp[1][i]) + 1
  else:
    dp[0][i+1] = dp[0][i] + 1
    dp[1][i+1] = min(dp[0][i], dp[1][i])
print(min(dp[0][n-1], dp[1][n-1]))

Submission status: Accepted

Solution code:
N = int(input())
S = input().strip()
dmin = 0
for i in range(N):
    if S[i]=="#":
        dmin += 1
d = dmin
for i in range(N-1,-1,-1):
    if S[i]=="#":
        d = d-1
    else:
        d = d+1
    dmin = min(dmin,d)
print(dmin)

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    w = s.count(".")
    b = 0
    mc = w + b
    for i in range(n):
        if s[i] == "#":
            b += 1
        else:
            w -= 1
        mc = min(mc, b + w)
    print(mc)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
S = input()

right_black = S.count('#')
right_white = S.count('.')
left_black, left_white = 0, 0

ans = left_black + right_white
for s in S:
    if s == '#':
        right_black -= 1
        left_black += 1
    else:
        right_white -= 1
        left_white += 1

    ans = min(ans, left_black + right_white)

print(ans)

Submission status: Accepted

Solution code:
# 石の番号は0-initial
N=int(input())
S=input()
# 0~iまでの石を白'.'，i+1~N-1までの石を黒'#'にする必要がある
L=[0] # iより左の黒石の個数
for i in range(N):
    L.append(L[-1]+int(S[i]=='#'))
R=[0] # i-1より右（i以右）の白石の個数（右から数えて後で反転させる）
for i in range(N-1,-1,-1):
    R.append(R[-1]+int(S[i]=='.'))
R=R[::-1]

ans=min([L[i]+R[i] for i in range(N+1)])

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]

def main():
    n=inp()
    s=input()
    w=0
    for i in range(n):
        if s[i]=='.':
            w+=1
    b=n-w
    ans=n
    x=0
    y=w
    for i in range(n):
        ans=min(ans,x+y)
        if s[i]=='.':
            y-=1
        else:
            x+=1
        ans=min(ans,x+y)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
k = 0
si = s.count('.')
m = si
for i in s:
  if i == '#':
    k += 1
  else:
    si -= 1
  m = min(m,k+si)
print(m)

Submission status: Accepted

Solution code:
# 2019-11-23 01:28:44(JST)
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    # 各indexを基点として、右側の白の数と左側の黒の数の和の最小値を求めればいい
    black_count = s.count('#')
    
    left_black = 0
    right_white = n - black_count
    minimum = left_black + right_white
    for i in range(0, n):
        if s[i] == '#':
            left_black += 1
        elif s[i] == '.':
            right_white -= 1
        minimum = min(minimum, left_black + right_white)
    
    print(minimum)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
w = b = 0
mn = 0
# 境界線(ex: "..#.....(ココ)###..####")より(左にある黒の数)+(右にある白の数)が求めるべき値
# これが最小になるように前から確認してmnを更新していく
for i in range(n):
    if s[i]=="#":
        b+=1
    else:
        w+=1
    if mn>b-w:
      mn = b-w
      #print(i,mn,b,w)
      
#　最後に全体の白の数を足すことで、
# 境界線より (左の黒の数-白の数)+(全体の白の数) = (左にある黒の数)+(右にある白の数)
print(mn+w)

Submission status: Accepted

Solution code:
from itertools import groupby
import numpy as np
N = int(input())
s = groupby(list(input()))
table = []
for key,group in s:
  cnt = 0
  for id,_ in enumerate(group,1):
    cnt = id
  table.append([key,cnt])
#print(table)
if len(table) == 1:
  print(0)
  exit()
B = [0] * (len(table) + 1)
W = [0] * (len(table) + 1)
for i in range(len(table)):
  if table[i][0] == "#":
    B[i+1] += table[i][1]
  else:
    W[i+1] += table[i][1]
B = np.cumsum(np.array(B))
W = np.cumsum(np.array(W)) 
ans = float("inf")
for i in range(len(table)+1):
  ans = min(ans,B[i] + W[-1] - W[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
cnt_b = [0] * (N+1)
cnt_w = [0] *(N+1)
for i in range(len(S)):
   cnt_b[i+1] = cnt_b[i]
   cnt_w[i+1] = cnt_w[i]
   if S[i] == '.':
      cnt_w[i+1] +=1
   else:
      cnt_b[i+1] +=1

ans = 1000000
for i in range(N+1):
   cost = cnt_b[i] + cnt_w[N] - cnt_w[i]
   ans = min(cost, ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=0
r=s.count('.')
m=r
for i in range(n):
  if s[i]=='.':
    r-=1
  else:
    l+=1
  m=min(m,r+l)
print(m)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
white = black = 0
W = S.count('.')
B = N - W #黒石の数
answer = W
for i in range(N):
    if S[i] == '.':
        white += 1
    else:
        black += 1
    change = black + W - white
    if change < answer:
        answer = change
    
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[] for _ in range(N)]
white = black = 0
for i in range(N):
    if S[i] == '.':
        white += 1
    else:
        black += 1
    dp[i] = [white, black]
W = S.count('.')
B = N - W #黒石の数
answer = W
for i in range(N):
    # iの場所より左側を全て白、右側を黒にする
    change = dp[i][1] + (W - dp[i][0])
    if change < answer:
        answer = change
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
S=list(input())

b = 0
w = 0
for i in range(len(S)):
    if(S[i]=="#"):
        b += 1
    else:
        w += 1
        
b_ = 0
min_ = min([w,b])
w_ = 0
for i in range(len(S)):
    if(S[i]=="#"):
        b_ += 1
    else:
        w_ += 1
    min_ = min([w-w_+b_,min_])
        

print(min_)

Submission status: Accepted

Solution code:
#白だけ返す、黒だけ返すとは限らない
#左は白、右は黒、にすることもある
n = int(input())
s = input()
b = 0
w = 0
bl = []
wl = []
for i in range(n):
    if s[i]==".":
        w += 1
        if b:
            bl.append(b)
            b = 0
    else:
        b += 1
        if w:
            wl.append(w)
            w = 0
if b:
    bl.append(b)
if w:
    wl.append(w)

if s[-1] == "#":
    bl.pop()


if s[0] == ".":
    wl.pop(0)
ans_b = 0
ans_w = sum(wl)
ans = ans_w + ans_b

for i in range(len(bl)):
    ans_b += bl[i]
    ans_w -= wl[i]
    ans = min(ans,ans_b +ans_w )

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
s=input()
B=[0]*N
W=[0]*N

if s[0]=="#": W[0]=1
else: B[0]=1

for i in range(1,N):
    if s[i]=="#":
        B[i]=min(B[i-1],W[i-1])
        W[i]=W[i-1]+1
    else:
        B[i]=min(B[i-1],W[i-1])+1
        W[i]=W[i-1]
        
print(min(B[N-1],W[N-1]))

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
rw=[0]*(n+1)
lb=[0]*(n+1)
for i in range(n):
    if s[i]=='#':
        lb[i+1]=lb[i]+1
    else:
        lb[i+1]=lb[i]
for i in range(n):
    if s[n-i-1]=='.':
        rw[n-i-1]=rw[n-i]+1
    else:
        rw[n-i-1]=rw[n-i]
ans=100000000000
for i in range(n+1):
    ans=min(ans,lb[i]+rw[i])
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input() #all# or all. or あるところから#
m=S.count('.')
b=[0]*(N+1)
a=[0]*(N+1)
m=N
for i in range(N):
  if S[i]=='#':
    b[i+1]=b[i]+1
    a[i+1]=a[i]
  else:
    b[i+1]=b[i]
    a[i+1]=a[i]+1
for j in range(N+1):
  m=min(m,b[j]+(a[N]-a[j]))
print(m)

Submission status: Accepted

Solution code:
n = int(input())
s = list(str(input()))
white_all = s.count(".")
black_all = s.count("#")
white = 0
black = 0
num = []

for i in range(n):
    if s[i] == ".":
        white += 1       
    else:
        black += 1
    num.append(black + (white_all - white))


print(min(min(num), white, black))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

b = [0] * N
w = [0] * N

for i, s in enumerate(S):
    if s == "#":
        b[i] += 1
    elif s == ".":
        w[i] += 1

def accmulate(arr):
    N = len(arr)
    cs = [0]*(N+1)
    for i in range(N):
        cs[i+1] = cs[i] + arr[i]
    return cs

# [l,r)
def query(cs, l, r):
    return cs[r] - cs[l]

b = accmulate(b)
w = accmulate(w)
ans = N

for k in range(N+1):
    res = b[k] + (w[N] - w[k])
    ans = min(ans, res)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools

n=int(input())
s=list(input())
a=s.count('#')
b=0
ans=a

for i in range(1,n+1):
    if s[-i]=='.':
        b+=1
    else:
        a-=1
        
    ans=min(a+b,ans)
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    s = input()
    black = s.count("#")
    white = len(s) - black
    ans = min(black, white)
    
    b,w = 0,0
    for i in range(len(s)):
        if s[i] == "#":
            b += 1
        else:
            w += 1
        
        ans = min(ans, b + (white - w))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
kuro=0
siro=s.count(".")
ans=siro
for i in range(n):
    if s[i]=="#":
        kuro+=1
    else:
        siro-=1
    ans=min(ans,kuro+siro)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
S=list(input())
N=len(S)

turn=0
kuro=0
shiro=0
last=0

ma=0
ans=0
for index,item in enumerate(S):
    if item==".":
        kuro+=1
        last=0
    else:
        shiro+=1
        last+=1
    ma=max((kuro-shiro),ma)
    if ma==(kuro-shiro):
        turn=index
        ans=shiro-kuro

print(min(ans+kuro,shiro-last))#混迷極まる

Submission status: Accepted

Solution code:
def cumsum(inlist,r = 0):
    s = 0
    outlist = []
    if r == 1:
        inlist.reverse()
    for i in inlist:
        s += i
        outlist.append(s)
    if r == 1:
        outlist.reverse()
    return outlist

n = int(input())
s = input()

w_list = [ 1 if i == "." else 0 for i in s ]
b_list = [ 1 if i == "#" else 0 for i in s ]

cum_w_list = cumsum(w_list,1)
cum_b_list = cumsum(b_list)

ans_list = [ s.count(".") ] + [ cum_b_list[i] + cum_w_list[i+1] for i in range(n-1) ] + [ s.count("#") ]

print( min(ans_list) )

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

def main():
    n = int(input().strip())
    S = input().strip()
    stack = []
    ans = 0
    for c in S:
        if c == '#':
            stack.append('#')
        else:
            if len(stack) != 0:
                stack.pop()
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
S=list(input())

lb=0
rw=S.count(".")

li=[rw]
for i in range(N):
  if S[i]=="#":
    lb+=1
  else:
    rw-=1
  li.append(lb+rw)
  
print(min(li))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    s = [1 if c == "#" else 0 for c in input().strip()] + [1]
    sum_ = sum(s)

    ans = N + 1 - sum_ # 全て黒にするのに必要な数
    for i in range(1, N+1):
        s[i] += s[i-1]
        ans = min(ans, s[i-1]+N+1-i-sum_+s[i-1])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  ans=inf

  s=S()

  ans=min(ans,len(s)-s.count('.'))
  ans=min(ans,len(s)-s.count('#'))

  a=s.count('.')
  b=s.count('#')

  _a=0
  for i in range(n):
    if s[i]=='.':
      a-=1
    else:
      _a+=1
    ans=min(ans,_a+a)
    # print(ans)
  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n=int(input())
s=input()
# どこを境目として撮るかということを尺取法で考えてみる！
lists=[0]*(n+1)
count=0
for  _ in range(n):
    if s[_]==".":
        count+=1
lists[0]=count
for i in range(1,n+1):
    #それぞれのインデックスについてそこが#か.に等しいのかをチェックする
    if s[i-1]!=".":
        count+=1
        lists[i]=count
    else:
        count-=1
        lists[i]=count
print(min(lists))

Submission status: Accepted

Solution code:
"""
N = 12
S = "..#..##.##.."
# expected => 4
"""
N = int(input())
S = input()
###


# black from left
vB = []
cntB = 0
vB.append(cntB)
for s in S:
    if s == "#":
        cntB += 1
    vB.append(cntB)

# white from right
vW = []
cntW = 0
for s in S[::-1]:
    vW.append(cntW)
    if s == ".":
        cntW += 1
vW.append(cntW)


#print(cntB, cntW)
#print(vB)
#print(vW[::-1])

print(min(b+w for b,w in zip(vB, vW[::-1])))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
cnt=s.count(".")
ans=cnt
for i in s:
  if i==".":cnt -=1
  else:cnt +=1
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()

cnt=0
for s in S:
  if s!="#":
    cnt+=1
ans=cnt

for s in S:
  if s==".":
    cnt-=1
  else:
    cnt+=1
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()


black = [0]*(N+1)
for i in range(N):
    if S[i] == "#":
        black[i+1] = black[i]+1
    else:
        black[i+1] = black[i]

ans = N
for i in range(N+1):
    tmp = (black[N-i]-black[0])+(i-(black[N]-black[N-i]))
    ans = min(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(input().strip())

lb, lw, rb, rw = 0, 0, l.count("#"), l.count(".")


ans = lb+rw
for i in range(len(l)):
    if l[i] == "#":
        lb += 1
        rb -= 1
    else:
        lw += 1
        rw -= 1

    ans = min(ans, lb+rw)
print(ans)

Submission status: Accepted

Solution code:
#%%
n = int(input())
s = list(input())

lb, lw, rb, rw = 0, 0, s.count('#'), s.count('.')

ans = lb+rw
for i in range(n):
    if s[i] == '#':
        lb += 1
        rb -= 1
    else:
        lw += 1
        rw -= 1
    ans = min(ans, lb+rw)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
to_white = [0] * n
to_black = [0] * n
for i in range(n):
    if s[i] == '#':
        if i == 0:
            to_white[i] = 1
        else:
            to_white[i] = to_white[i-1] + 1
    else:
        if i == 0:
            to_white[i] = 0
        else:
            to_white[i] = to_white[i-1]
for i in reversed(range(n)):
    if s[i] == '.':
        if i == n-1:
            to_black[i] = 1
        else:
            to_black[i] = to_black[i+1] + 1
    else:
        if i == n-1:
            to_black[i] = 0
        else:
            to_black[i] = to_black[i+1]
ans = 10**100
for i in range(n):
    ans = min(ans, to_white[i] + to_black[i] - 1)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

w_cnt = [0]
w = 0
for s in S:
    if s == '.':
        w += 1
    w_cnt.append(w)

b_cnt = [0]
b = 0
for s in S[::-1]:
    if s == '#':
        b += 1
    b_cnt.append(b)


ans = float('inf')
i = 0
for b, w in zip(b_cnt[::-1], w_cnt):
    ww, bb = i, N - i
    ans = min(ans, abs(b - bb) + abs(w - ww))
    i += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

w_cnt = [0]
w = 0
for s in S:
    if s == '.':
        w += 1
    w_cnt.append(w)

b_cnt = [0]
b = 0
for s in S[::-1]:
    if s == '#':
        b += 1
    b_cnt.append(b)
b_cnt.reverse()


ans = float('inf')
i = 0
for b, w in zip(b_cnt, w_cnt):
    ww, bb = i, N - i
    ans = min(ans, abs(b - bb) + abs(w - ww))
    i += 1
print(ans)

Submission status: Accepted

Solution code:
n =int(input())
s = input()
tres = s.count(".")
res = tres
for c in s:
    if c == ".":
        tres -= 1
    else:
        tres += 1
    res = min(res,tres)        

print(res)

Submission status: Accepted

Solution code:
n=int(input())
s=str(input())
a=0
b=s.count('.')
l=[b]
for i in range(n):
    if s[i]=='#':
        a+=1
    if s[i]=='.':
        b-=1
    l.append(a+b)
print(min(l))

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    s = input()
    if len(set(s)) == 1:
        print(0)
    else:
        acc_w, acc_b = [], []
        w, b = 0, 0
        for i in range(n):
            if s[i] == ".":
                w += 1
            else:
                b += 1
            acc_w.append(w)
            acc_b.append(b)
        w = s.count(".")
        b = s.count("#")
        ans = min(w, b)
        for i in range(n - 1):
            if s[i] == "." and s[i + 1] == "#":
                t = acc_b[i] + w - acc_w[i]
                if t < ans:
                    ans = t
        print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def C(N, S):
    n_diff_chars = S.count(".")
    cand_list = [n_diff_chars]
    for c in S:
        if c == ".":
            n_diff_chars -= 1
        else:
            n_diff_chars += 1
        cand_list.append(n_diff_chars)
    print(min(cand_list))


if __name__ == "__main__":
    N = int(input())
    S = input()
    C(N, S)

Submission status: Accepted

Solution code:
# tenka1-2019-beginnerC - Stones
def main():
    N, S = open(0).read().split()
    ans, blk = 0, 0
    for i in S:
        if i == "#":
            blk += 1
        else:
            if blk:
                ans += 1
                blk -= 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(lambda x: 1 if x == "#" else 0, input()))

cs = [0] * (n+1)
for i in range(n):
    cs[i+1] = cs[i] + s[i]

ans = 10**6
for i in range(n+1):
    ans = min(ans, cs[i] + n - i - (cs[n] - cs[i]))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

n = int(input())
s = input()

S =[]
for i in s:
    S.append(i)

w = 0
b = 0

for i in range(n):
    if S[i] == "#":
        b += 1
    elif S[i] == ".":
        w += 1

ans = [0 for i in range(n+1)]

ans[0] = w
for i in range(n):
    if S[i] == "#":
        ans[i+1] = ans[i]+1
    elif S[i] == ".":
        ans[i+1] = ans[i]-1
        
print(min(ans))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

ans = S.count('.')
c = S.count('.')

for i in range(N):
    if S[i] == '.':
        c -= 1
    else:
        c += 1
    ans = min(ans, c)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

LeftBlack  = [0]*N
RightWhite = [0]*N

LeftBlack[0]=0
for i in range(1,N):
    if S[i-1] == '#':
        LeftBlack[i]=LeftBlack[i-1]+1
    else:
        LeftBlack[i]=LeftBlack[i-1]

RightWhite[N-1]=0
for i in range(N-2,-1,-1):
    if S[i+1] == '.':
        RightWhite[i] = RightWhite[i+1]+1
    else:
        RightWhite[i] = RightWhite[i+1]

ans = N
for i in range(N):
    if S[i] == '.':
        n = LeftBlack[i]+RightWhite[i]
    else:
        n = LeftBlack[i]+RightWhite[i]+1
    ans = min(ans,n)

b = 0
w = 0
for i in range(N):
    if S[i]=='.':
        b +=1
    else:
        w +=1
ans = min(ans,b)
ans = min(ans,w)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
s=input()
s_int=[0 if x=="." else 1 for x in s]
ruiseki=np.cumsum([0,]+s_int)
 
#print(s_int,ruiseki)
res=float("inf")
for i in range(n+1):
  #print("左黒",ruiseki[i],"右白",(n-i-(ruiseki[-1]-ruiseki[i])),"計",n-i-ruiseki[-1]+2*ruiseki[i])
  res=min(n-i-ruiseki[-1]+2*ruiseki[i],res)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ns = []
i = 0
while i < N:
  j = S.find(".", i)
  if j < 0: j = N
  k = S.find("#", j)
  if k < 0: k = N
  ns.append((j-i, k-j))
  i = k
#print(ns)
rs = []
r = sum([w for b, w in ns])
rs.append(r)
for b, w in ns:
  r += b-w
  rs.append(r)
#print(rs)
r = min(rs)
print(r)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

# 変更後は (0個以上の.)+(0個以上の#) という形になっていればよい。
# ###～###から始めて、.##～###、..#～###、、、...～...までのすべてのパターンについて
# そうなるために変更する必要のある石の個数をカウントし、その最小値を求める。
ans = S.count('.')
tmp = ans
for i in range(N):
  if S[i] == '.':
    tmp -= 1
  else:
    tmp += 1
  ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

w = [0]
cnt = 0
for i in range(n):
  if s[i] == '#':
    cnt += 1
  w.append(cnt)

ans = len(s)
for i in range(n+1):
  ans = min(ans, w[i]+(n-i-(w[-1]-w[i])))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()

white=s.count(".")
black=0
ans=white

for s_i in s:
    if s_i == "#":
        black+=1
    else:
        white-=1
    ans = min(ans, white+black)
print(ans)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    S = input()
    suffix_w = [0]
    for i in range(N-1, -1, -1):
        if S[i] == ".":
            suffix_w.append(suffix_w[-1] + 1)
        else:
            suffix_w.append(suffix_w[-1])
        # print(suffix_w, S[i])
    suffix_w = suffix_w[::-1]
    # print(suffix_w)


    min_c = float('inf')
    countb = 0
    countw = 0
    for i in range(N):
        if S[i] == "#":
            c = suffix_w[i+1] + countb
            min_c = min(min_c, c)
            countb += 1
        else:
            countw += 1
    min_c = min(min_c, countb, countw)
    return min_c

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
S = input()

black = S.count('#')
white = S.count('.')

ans = white
prev_black = 0
for i in range(N):
    if(S[i] == '.'):
        white -= 1
    else:
        prev_black += 1
    ans = min(white + prev_black, ans)

print(ans)