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:
n = int(input())
ss = list(input())
num_white = [0]
num_black = [0]

for s in ss:
  if s == '#':
    num_black.append(num_black[-1] + 1)
    num_white.append(num_white[-1])
  else:
    num_black.append(num_black[-1])
    num_white.append(num_white[-1] + 1)

ar_moves = [ ]
for i in range(n+1):
  moves = 0
  # numbers of blacks before i
  moves += num_black[i] - num_black[0]
  # numbers of whites after i
  moves += num_white[-1] - num_white[i]
  ar_moves.append(moves)
print(min(ar_moves))

#  .##..#.
# 00122233
# 01112334

Submission status: Accepted

Solution code:
input()
S = input()
length = len(S)

dp = {}

for i in range(length):
  for ch in ['#', '.']:
    base = 1 if S[i] != ch else 0

    if i == 0:
      dp[(i, ch)] = base
      continue
    if ch == '#':
      dp[(i, ch)] = min(base + dp[(i-1,'#')], base + dp[(i-1,'.')])
    else:
      dp[(i, ch)] = base + dp[(i - 1, '.')]


# print('dp', dp)
print(min(dp[(length - 1, '#')], dp[(length - 1, '.')]))

Submission status: Accepted

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


ans = N+1

# ...
wnum = S.count('.')
# ###
bnum = S.count('#')

# ...###
wcnt = 0
bcnt = 0
for i, s in enumerate(S):
    l_wnum = wcnt
    l_bnum = bcnt
    r_wnum = wnum - l_wnum
    step = l_bnum + r_wnum
    if step < ans:
        ans = step

    #print('i: ', i)
    if s == '.':
        wcnt += 1
    else:
        bcnt += 1

# ...
if bnum < ans:
    ans = bnum

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = str(input())
num_list=[]
white=0
black=0
#一番左が境界の場合
num_list.append([0,0])
for i in range(0,N):
    if(S[i]=="."):
        white+=1
    elif(S[i]=="#"):
        black+=1
    num_list.append([white,black])

#左から0,1,.....Nのところに境界を持ってきたときのしろと黒の個数がnum_listに入っている
ans=N
tmp=0
for i in range(0,N+1):
    tmp=num_list[i][1]+white-num_list[i][0]
    if(ans>tmp):
        ans=tmp
print(ans)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

N = int(input())
S = "0" + input()

flag = False
cnt = 0
for i in range(1, N+1):
    c = S[i]
    if not flag and c == "#":
        flag = True
    elif c == "." and flag:
        cnt += 1

ans = cnt

# white
flag = False
cnt2 = 0
for i in range(1, N+1):
    c = S[i]
    if not flag and c == "#":
        flag = True
        
    if c == "#":
        cnt2 += 1
    elif c == "." and flag:
        cnt -= 1
        cnt += cnt2
        cnt2 = 0
        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

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

l_black = 0
r_white = S.count('.')
ans = r_white

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

print(ans)

Submission status: Accepted

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

ans = [3*10**5]
white = [0]
black = [0]
for i in range(n):
    if s[i] == ".":
        white.append(white[i] + 1)
        black.append(black[i])
    else:
        white.append(white[i])
        black.append(black[i] + 1)
#print(white)
#print(black)
for i in range(n+1):
    ans.append(black[i] + white[n]-white[i])

print(min(ans))

Submission status: Accepted

Solution code:
# encoding: utf-8
import sys
# input = sys.stdin.readline

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

w = [0] * (N + 1)
b = [0] * (N + 1)
wi = bi = 0
for i, Si in enumerate(S):
    if Si == '.': wi += 1
    else: bi += 1
    # print("#", i, wi, bi)
    w[i + 1] = wi
    b[i + 1] = bi

ans = N
for i in range(N + 1):
    ans_tmp = b[i] + (w[-1] - w[i])
    if ans > ans_tmp: ans = ans_tmp

print(ans)

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N=ri()
S=input()
white = [0] * (N+1)
black = [0] * (N+1)
for i in range(N):
    if S[N-1-i] == '.':
        white[i] = white[i-1] + 1
    else:
        white[i] = white[i-1]
    if S[i] == '#':
        black[i] = black[i-1] + 1
    else:
        black[i] = black[i-1]
ans = black[-1] + white[N-1]
for i in range(N):
    ans = min(ans, black[i] + white[N-2-i])
print(ans)

Submission status: Accepted

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

cum_b = [0]
for c in S:
    cum_b.append(cum_b[-1] + int(c=='#'))

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

Submission status: Accepted

Solution code:
n = int(input())
s = input()
n = len(s)
white = [0]
for i, si in enumerate(s, 1):
    white.append(white[-1] + (1 if si == '.' else 0))

ans = n
for i in range(n + 1):
    # print(i, (i - white[i]) + (white[n] - white[i]))
    ans = min((i - white[i]) + (white[n] - white[i]), ans)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

black = [0 for _ in range(len(s) + 1)]
white = [0 for _ in range(len(s) + 1)]
for i in range(len(s)):
    if s[i] == ".":
        white[i] = 1
    else:
        black[i] = 1
for i in reversed(range(len(black)-1)):
    black[i] += black[i + 1]
    white[i] += white[i + 1]
# print(black)
# print(white)
cost = 0
_min = 10**10
for i in range(len(black)-1):
    if s[i] == "#":
        _min = min(_min, cost + white[i])
        cost += 1
    # print("i:{} cost:{} _min:{}".format(i, cost, _min))
print(min(cost, _min))

Submission status: Accepted

Solution code:
from collections import defaultdict as ddic, deque
from itertools import combinations, permutations, product
import sys
sys.setrecursionlimit(10**6)
stdout = sys.stdout
rr = lambda: raw_input().strip()
rri = lambda: int(raw_input())
rrm = lambda: list(map(int, raw_input().strip().split()))


def solve(N, A):
    dp0 = [0] * (N+1)
    dp1 = [0] * (N+1)
    for i in xrange(N-1, -1, -1):
        for color in (0, 1):
            if color == 1:
                ans = dp1[i+1] + (A[i] != color)
            else:
                ans = min(dp0[i+1], dp1[i+1]) + (A[i] != color)

            if color == 0:
                dp0[i] = ans
            else:
                dp1[i] = ans

    return min(dp0[0], dp1[0])

###
N = rri()
S = rr()
A = [1 if c == '#' else 0 for c in S]
print solve(N, A)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
answers = []

from itertools import accumulate

white_cumsum = list(accumulate([1 if s=='.' else 0 for s in S]))
black_cumsum = list(accumulate([1 if s=='#' else 0 for s in S]))

answers.append(white_cumsum[-1])
answers.append(black_cumsum[-1])

for i in range(N):
  answers.append(black_cumsum[i] + white_cumsum[-1] - white_cumsum[i])
    
answer = min(answers)
print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N = d_in()
S = s_in()

np_s = np.zeros(N+1, dtype=int)
for i in range(N):
    if S[i] == '#':
        np_s[i+1] = 1

cum_s = np.cumsum(np_s)

tot = cum_s[-1]
ans = N
for i in range(N+1):
    r_white = (N-i) - (tot - cum_s[i])
    l_black = cum_s[i]
    ans = min(ans, r_white + l_black)

print(ans)

Submission status: Accepted

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

n = int(input())
s = list(input())
res = 10**9

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

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = S()
    a = []
    t = 0
    for c in s:
        if c == '#':
            t += 1
        a.append(t)
    b = []
    t = 0
    for c in s[::-1]:
        if c == '.':
            t += 1
        b.append(t)
    b = b[::-1]
    r = inf
    for i in range(n):
        t = a[i] + b[i]
        if r > t:
            r = t

    return r - 1


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def solve(n, s):
    ans = float('inf')
    black = 0
    white = s.count('.')
    for m in range(n + 1):
        ans = min(ans, black + white)
        if m < n and s[m] == '#':
            black += 1
        if m < n and s[m] == '.':
            white -= 1
    return ans

n = int(input())
s = input()
print(solve(n, s))

Submission status: Accepted

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

count_white = [0] * (N + 1)
count_black = [0] * (N + 1)

for i in range(N - 1, -1, -1):
    if S[i] == ".":
        count_white[i] = count_white[i + 1] + 1
    else:
        count_white[i] = count_white[i + 1]

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

ans = float("inf")

for i in range(N + 1):
    temp = count_white[i] + count_black[i]
    if temp < ans:
        ans = temp

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = ns()

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

ans = float('inf')

for i, si in enumerate(s):
    if si == '#':
        rb -= 1
    else:
        rw -= 1
        
    ans = min(ans, rw + lb)
    
    if si == '#':
        lb += 1
    else:
        lw += 1
        
print(ans)

Submission status: Accepted

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

ans = 0
for si in s:
    if si == '#':
        ans += 1

white = [0] * (n+1)
black = [0] * (n+1)

for i in range(n):
    if s[i] == "#":
        white[i+1] = white[i]
        black[i+1] = black[i] + 1
    else:
        white[i+1] = white[i] + 1
        black[i+1] = black[i]



for i in range(n):
    if s[i] == ".":
        continue
    ans = min(ans, black[i] + white[n] - white[i + 1])

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

# #. というパターンをなくしたい

from collections import Counter
cntr = Counter(S)
kuro = cntr["#"]
siro = cntr["."]

ans = min(kuro, siro)
if kuro >= 1 and siro >= 1:
    tmp = N - siro # 全部白にする
    for i in range(N-1, -1, -1):
        if S[i] == ".":
            tmp += 1
            # ans = min(ans, tmp)
        else:
            tmp -= 1
            ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys, collections, bisect, math, itertools
from fractions import gcd 
#input = sys.stdin.readline #文字列入力のときは注意

n = int(input())
s = input()
#a = [int(i) for i in input().split()]
#m = [[int(i) for i in input().split()] for j in range(n)] # 縦「n」行

b = [0]*(n+1)
for i in range(n):
    b[i+1] += b[i] + (1 if s[i]=="#" else 0)

w = [0]*(n+1)
for i in range(n):
    w[i+1] += w[i] + (1 if s[i]=="." else 0)
#print(b,w)
ans = n
for i in range(n):
    if i != 0:
        p = b[i-1]
    else: p=0
    q = w[n]-w[i]
#    print(p,q)
    ans = min(ans,p+q)

print(min(ans,b[n]))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
whitecount = [0 for i in range(N+1)]
for i in range(N):
    if S[i] == ".":
        whitecount[i+1] = whitecount[i] + 1
    else:
        whitecount[i+1] = whitecount[i]
ans = 1000000
for i in range(N+1):
    anstemp = i - whitecount[i] + (whitecount[-1] - whitecount[i])
    ans = min(anstemp, ans)
print(ans)

Submission status: Accepted

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

wh = [0] * (N+1)
bl = [0] * (N+1)

for i in range(N):
    if S[i] == "#":
        bl[i+1] = bl[i] + 1
    else:
        bl[i+1] = bl[i]
        
    if S[N-1-i] == ".":
        wh[N-1-i] = wh[N-i] + 1
    else:
        wh[N-1-i] = wh[N-i]
        


ans = 1145141919810

for i in range(N+1):
    if bl[i] + wh[i] < ans:
        ans = bl[i] + wh[i]
        
print(ans)

Submission status: Accepted

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

ans = N
numB = 0
numW = Ss.count('.')
for S in Ss+'_':
    ans = min(ans, numB+numW)
    if S == '#':
        numB += 1
    else:
        numW -= 1

print(ans)

Submission status: Accepted

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

B=[0]
for i in range(N):
    if S[i]=="#":
        B.append(B[-1]+1)
    else:
        B.append(B[-1])

MAXB=B[-1]
ANS=10**10

for i in range(N+1):
    l=B[i]
    r=(N-i)-(MAXB-B[i])
    #print(i,l,r)
    

    ANS=min(ANS,l+r)

print(ANS)

Submission status: Accepted

Solution code:
n = int(input())
s = str(input())
w = 0
for i in range(n):
  if s[i] == ".":
    w += 1
mi = w
c = w
for i in range(n):
  if s[i] == "#":
    c += 1
  else:
    c -= 1
  if c < mi:
    mi = c
print(mi)

Submission status: Accepted

Solution code:
n = input()
s = list(raw_input().strip())

blacks = s.count('#')
whites = n - blacks

ans = min(blacks, whites)

b, w = 0, 0
for i in xrange(n):
    if s[i] == '#': b += 1
    else: w += 1

    v = (i + 1) - w + n - i - 1 - (blacks - b)
    ans = min(ans, v)

print ans

Submission status: Accepted

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
import heapq
import math
import bisect


def main():
    N = int(input())
    S = input()
    W = [0] * (N+1)
    B = [0] * (N+1)
    for i in range(N):
        W[i+1] = W[i]
        B[i+1] = B[i]
        if S[i]=='.':
            W[i+1] += 1
        else:
            B[i+1] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
s = input()

left = 0
right = 0

black = [0] * n
white = [0] * n
for i in range(n):
    if s[i] == ".":
        black[i] += 1
    else:
        white[i] += 1

black.insert(0, 0)
white.insert(0, 0)
black = np.cumsum(black)
white = np.cumsum(white)

results = [black[n]]
for i in range(n):
    results.append(white[i + 1] + black[n] - black[i + 1])
print(min(results))

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())
S = input()
accNumBlack = [0] + list(accumulate([int(c == '#') for c in S]))

ans = float('inf')
for i in range(N+1):
  tmp = 0
  # i - 1 個目までを白にする
  tmp += accNumBlack[i] - accNumBlack[0]
  # i 個目からを黒にする
  tmp += (N - i) - (accNumBlack[N] - accNumBlack[i])
  ans = ans if ans < tmp else tmp
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N = int(input())
S = input()

B, H = [0], [0]
for i, s in enumerate(S):
    if s == '.':
        H.append(1)
        B.append(0)
    else:
        H.append(0)
        B.append(1)

B, H = list(accumulate(B)), list(accumulate(H))
ans = float('inf')
for i in range(N + 1):
    ans = min(ans, B[i] + H[-1] - H[i])
print(ans)

Submission status: Accepted

Solution code:
def stones(N: int, S: str)->int:
    # 左から見た黒石の個数の累積和と
    # 右から見た白石の個数の累積和を保持し
    # その和が最小となる位置を探す。
    black, white = [0] * (N+1), [0] * (N+1)

    for i, c in enumerate(S):
        black[i+1] = black[i]
        if c == '#':
            black[i+1] += 1

    for i, c in enumerate(S[::-1]):
        white[N-i-1] = white[N-i]
        if c == '.':
            white[N-i-1] += 1

    # print(black)
    # print(white)

    return min(black[i] + white[i+1] for i in range(N))


if __name__ == "__main__":
    N = int(input())
    S = input()
    ans = stones(N, S)
    print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

N = int(input())
S = input()
value = 0
for c in S:
    if c == ".":
        value += 1
ans = value
for i in range(N):
    if S[i] == ".":
        value -= 1
    else:
        value += 1
    ans = min(ans,value)
print(ans)

Submission status: Accepted

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

dp = [0 for i in range(N + 1)]
for i in range(N):
    dp[i + 1] = dp[i] + (S[i] == '#')
ans = min(dp[i] + (N - i - (dp[N] - dp[i])) for i in range(N + 1))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=[0 if i=="." else 1 for i in input()]
X=[0 for i in range(N+1)]
Y=[0 for i in range(N+1)]
for i in range(N):
    X[i+1]=S[i]+X[i]
    Y[-2-i]=Y[-1-i]+(1-S[-1-i])
Z=[X[i]+Y[i] for i in range(N+1)]
print(min(Z))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    S = input()
    res = S.count('.')
    c = res
    for s in S:
        if s == '.':
            c -= 1
            res = min(res, c)
        else:
            c += 1

    return str(res)

    
        

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

Submission status: Accepted

Solution code:
from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
S = input()[:-1]

white = S.count('.')
L = [0]*N
for i, c in enumerate(S):
    if c == ".":
        L[i] = 1
L = [0]+list(accumulate(L))
# print(white)
# print(L)
if white == N or white == 0:
    ans = 0
else:
    ans = float('inf')
    for i in range(N+1):
        b = i-L[i]
        w = L[-1]-L[i]
        #print("{} times b:{} w:{}".format(i, b, w))
        ans = min(ans, b+w)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    black = [0] * (N+1)
    white = [0] * (N+1)
    for i in range(N):
        black[i+1] = black[i]
        white[N-i-1] = white[N-i]
        if S[i] == "#":
            black[i+1] += 1
        if S[N-i-1] == ".":
            white[N-i-1] += 1
    ans = float("inf")
    for i in range(N+1):
        ans = min(ans, black[i] + white[i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
d = [0] * (N+1)
s = [0] * (N+1)
for i, c in enumerate(S):
    if c=="#":
        s[i + 1] = s[i] + 1
        d[i+1] = d[i]
    else:
        s[i + 1] = s[i]
        d[i + 1] = d[i] + 1
#print(s, d)
ans = float("inf")
ddd = d[-1]
for ss, dd in zip(s[:-1],d[1:]):
    ans = min(ans, ss+(ddd-dd))

print(ans)

Submission status: Accepted

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

cnt = 0
w = [0]
for c in s:
    if c == '.':
        w.append(cnt + 1)
        cnt += 1
    else:
        w.append(cnt)

cnt = 0
b = [0]
for c in s:
    if c == '#':
        b.append(cnt + 1)
        cnt += 1
    else:
        b.append(cnt)

# w_c = [0]
# for i in range(n):
#     w_c.append(w_c[i] + w[i])
# b_c = [0]
# for i in range(n):
#     b_c.append(b_c[i] + b[i])

# ...###
res = 10**10
for i in range(n + 1):
    tmp = 0
    tmp += b[i]
    tmp += w[-1] - w[i]
    res = min(tmp,res)
print(res)

Submission status: Accepted

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

# 白→黒　が許容される状態

ans = N + 1

# 所与→全黒
ans = S.count(".")
prev = ans

for i in range(N):
	if S[i] == "#":
		now = prev + 1
	else:
		now = prev - 1


	if now < ans:
		ans = now
	prev = now

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
w = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(n):
    if s[i] == '.':
        w[i + 1] += 1
    else:
        b[i + 1] += 1

for i in range(1, n + 1):
    w[i] += w[i - 1]
    b[i] += b[i - 1]

num = float('inf')
for i in range(n + 1):
    num = min(num, b[i] + w[n] - w[i])

print(num)

Submission status: Accepted

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

white_cum = [0]*(N+1)
black_cum = [0]*(N+1)

cum = 0
for i in range(N):
    if S[i] == "#":
        cum += 1
    white_cum[i+1] = cum

cum = 0    
for i in range(N):
    if S[N-1-i] == ".":
        cum += 1
    black_cum[N-1-i] = cum
    
res = min([white_cum[i] + black_cum[i] for i in range(N+1)])
print(res)

Submission status: Accepted

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

whites = [0]
blacks = [0]

for i in range(N):
	whites.append(whites[-1] + ('.' == S[i]))
	blacks.append(blacks[-1] + ('#' == S[i]))

min_count = blacks[0] + (whites[N] - whites[0])

for i in range(1, N+1):
	min_count = min(min_count, blacks[i] + (whites[N] - whites[i]))

print(min_count)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
ans=1000000000
w=[0]*(N+1)
for i in range(N):
  if S[i]==".":
    w[i+1]=w[i]+1
  else:
    w[i+1]=w[i]
    
for i in range(N+1):
  ans=min(ans,i-2*w[i]+w[N])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = cum[i] + int(s[i] == '#')
mincost = n
for i in range(n+1):
    mincost = min(mincost, 2 * cum[i] - cum[n] + (n - i))
print(mincost)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
ans=[S.count('.')]

for i in range(N):
	temp=ans[-1]
	if S[i]=='#':
		temp+=1
	else:
		temp-=1
	ans.append(temp)

print(min(ans))

Submission status: Accepted

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

T = [[N,N] for _ in range(N)]
if S[0]==".":
  T[0][0] = 0
  T[0][1] = 1
else:
  T[0][0] = 1
  T[0][1] = 0

for i in range(1,N):
  for p in range(2):
    for c in range(2):
      if not (p==1 and c==0):
        if S[i]==".":
          t = c
        else:
          t = 1-c
        T[i][c] = min(T[i][c], T[i-1][p]+t)
print min(T[N-1])

Submission status: Accepted

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

left = [0]
right = [0]

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

for s in S[::-1]:
    right.append(right[-1] + (1 if s == '.' else 0))

ans = n

for i in range(0, n + 1):
    ans = min(ans, left[i] + right[n - i])

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache

# input = sys.stdin.readline

# N個整数
#n= list(map(int, input().split()))

# 1整数
n = int(input())

# 空白区切りリスト整数
# b = list(map(int, input().split()))

# 空白区切り文字列
# t, d = input().split()
s = input()

ret = 9999999
count = 0

##全黒から
for i in range(n):
    ##白なら変更
    if s[i] == '.':
        count += 1
ret = min(ret,count)

#i個目を白にしたとしての距離
for i in range(n):
    if s[i] =='.':
        count -= 1
    else:
        count += 1
    ret = min(ret,count)

print(ret)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from bisect import bisect, bisect_left
from itertools import product, permutations, combinations
from fractions import gcd
import sys
sys.setrecursionlimit(int(1e7))

def inpl(): return list(map(int, input().split()))

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

ans = 1e10
changes = S.count("#")
ans = min(changes, ans)
for i in range(N-1, -1,-1):
    if S[i] == ".":
        changes += 1
    else:
        changes -= 1
    ans = min(ans, changes)
print(ans)

Submission status: Accepted

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

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

minChange = 100000
for i in range(N+1):
    minChange = min(black[i] - black[0] + white[N] - white[i], minChange)
print(minChange)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
X = [0] * (N+1)
Y = [0] * (N+1)
for i in range(N):
    X[i+1] = X[i] + (1 if S[i]=="#" else 0)
for i in range(N+1):
    Y[i] = X[i] + (N-i-X[N]+X[i])
print(min(Y))

Submission status: Accepted

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

f = [0]
tmp = 0
for c in s:
    if c == '#':
        tmp += 1
    f.append(tmp)

b = [0]
tmp = 0
for c in s[::-1]:
    if c == '.':
        tmp += 1
    b.append(tmp)
b.reverse()

# print(f)
# print(b)
print(min(map(sum, zip(f, b))))

Submission status: Accepted

Solution code:
INF = 999999999999999999L
EPS = 1e-12

def read():
    return raw_input().strip()

def read_ints():
    return map(int,read().split())

n = int(read())
s = read()
A = s.count("#")
B = s.count(".")
a = 0
b = 0
best = INF 

for i in range(len(s)):
    best = min(best, a+(B-b))
    if s[i] == ".":
        b += 1
    else:
        a += 1
best = min(best, a+(B-b))

print best

Submission status: Accepted

Solution code:
N = int(input())
S = input()
D = [0]*(N+1)
for i in range(N):
    D[i+1] = D[i] + (S[i] == '#')
ans = 10**18
for i in range(N+1):
    ans = min(ans, D[i] + (N-i - (D[N] - D[i])))
print(ans)

Submission status: Runtime Error

Solution code:
from random import randint
import math
#from math import gcd
from fractions import gcd
def is_prime(x):#https://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

n = int(input())
a=[]
for _ in range(n+1):
    a.append(int(input()))
a.reverse()

prm0 = []
prm02 = []
a0 = a[0]

sq = int(a0**(1/2))+3

for i in range(2,sq):
    if a0%i==0:
        prm0.append(i)
        prm02.append(a0//i)
pr_ = prm0+prm02
if a0:
    pr_.append(a0)
pr = []
for p in pr_:
    if is_prime(p):
        pr.append(p)
#print("test",pr)
def f(x,p):
    res = 0
    for i in range(n+1):
        res += pow(x,i,p)*a[i]
    return res
ans_l = []
pr2 = {p for p in pr}
for _ in range(50):
    ans = a0
    rn = randint(1,a0)
    ans = gcd(ans,f(rn,a0))
    for p in pr:
        if ans%p and p in pr2:
            pr2.remove(p)
    #print(ans)

#ans_l = list(set(ans_l))
#print(ans_l)

for p in pr2:
    print(p)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = list(b)
e = []
for i in range(len(c)+1):  #左からi個を白にする
    if i == 0: #全て黒に変える場合
        e.append(c.count("."))
        ans = e[0]
    else:
        if c[i-1] == ".":
            d = d + 1
        e.append(((i - d) + (c.count(".") - d)))
        if ans >= e[i]:
            ans = e[i]
print(ans)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = list(b)
e = []
for i in range(len(c)+1):  #左からi個を白にする
    if i == 0: #全て黒に変える場合
        e.append(c.count("."))
        ans = e[0]
        print(e)
    else:
        if c[i-1] == ".":
            d = d + 1
        e.append(((i - d) + (c.count(".") - d)))
        print(e)
        if ans >= e[i]:
            ans = e[i]
print(ans)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = list(b)
if len(c) >= 2:
    while c[0] == "." :
        del c[0]
        if (c[0] == ".") & len(c) == 1:
            break
    while c[len(c)-1] == "#":
        del c[len(c)-1]
        if (c[len(c)-1] == "#") & len(c) == 1:
            break    
    if c.count(".") <= c.count("#"): #白が黒より少ない場合
       d = c.count(".")
    elif c.count(".") > c.count("#"): #白が黒より多い場合
       d = c.count("#")
else: 
    d = 0
print(d)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = list(b)
while c[0] == "." :
    del c[0]
    if (c[0] == ".") & len(c) == 1:
        break
while c[len(c)-1] == "#":
    del c[len(c)-1]
    if (c[len(c)-1] == "#") & len(c) == 1:
        break    
if c.count(".") <= c.count("#"): #白が黒より少ない場合
   d = c.count(".")
elif c.count(".") > c.count("#"): #白が黒より多い場合
   d = c.count("#")
print(d)

Submission status: Runtime Error

Solution code:
H = int(input().strip())
S = input().strip()
#print(H)
#print(S)
counter = 0
white = ''
step = 0
while S[step] != '#':
    white = white + '.'
    step += 1
remainder = S[len(white):]
#print(white)
#print(remainder)
for i in remainder:
    if i == '#':
        counter += 1
paintWhite = 0
paintBlack = 0
if counter > len(remainder) / 2:
    print(len(remainder) - counter)
else:
    print(counter)

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
L=list(S)
c=0
for i in L:
  if(i=='#'):
    a=L.index(i)
    if L[a+1]=='.':
      L[a+1]=='#'
      c=c+1
print(c)

Submission status: Runtime Error

Solution code:
=int(input())
s=input()
bl=s.count('#')
wh=s.count('.')
if bl>wh:
    print(wh)
elif wh>bl:
    print(bl)