Codeforces Round#650 Div.3C.Social Distance의 연속적인 0 및 1 처리

6344 단어 codeforces

개요

  • n열이 있는 의자는 n문자의 좌석 상황 s를 줄 수 있다.예를 들어, 10001.1 은 착석입니다.0은 빈자리입니다.
  • 사교 공간 때문에 k개의 빈자리를 비워야 앉을 수 있다.
  • 현재 사교 공간은 유지되고 있다.그럼 최대 몇 명이 앉을 수 있을까요?
  • 예제

  • k=1100010의 경우
  • 한 사람도 앉을 수 있어요.10101010 만들 수 있어요.
  • k=2가 000000일 경우
  • 두 사람이 더 앉을 수 있어요.100, 100 만들 수 있어요.
  • k=1이 10101인 경우
  • 더 이상 앉을 수 없다(0명).10101 밖에 못해요.
  • 이렇게 생각했어요.



    우선, 이렇게 아무도 없는 좌석이 n=7이라고 가정하면 k=2로 지정된다.이런 상황에서 ceil(n/(k+1))사람이 가장 큰 좌석수인데 그림에서 보듯이 떠오른다.왜냐하면 먼저 왼쪽에 앉고 k가 비면 다시 바꾸는 것이 탐욕에 가장 적합하기 때문이다.
    사람이 탈 수 있고 팔 수 있는 구간은 0연속 구간에 불과해 아무리 앉아도 옆 0연속 구간에 영향을 주지 않는다.즉, 연속된 0개 구간에 대해 상술한 계산을 할 수 있다.
    맞다

    그림에서 보듯이 4개의 빈 좌석이 있는 것을 감안하면 양쪽 끝은 특수 처리를 해야 한다.
  • 중간 상황을 고려한다.물론 비단 연속 0구간은 이 구간에 포함되지 않고 인접한 1구간은 1이다.따라서 양쪽 끝은 반드시 k의 거리를 비워야 한다.
  • 즉, 연속된 0의 수량이 l이면 이 구간은 (l-k-k)의 왼쪽 또는 오른쪽 끝에 1을 놓을 수 있는 구간으로 여겨져 위에서 말한 바와 같이 계산할 수 있다.
  • 예를 들어 왼쪽의 상황을 고려한다.이런 상황에서 오른쪽 옆집은 1이기 때문에 반드시 k의 거리를 비워야 한다.그러나 왼쪽 끝이 끝이기 때문에 가장 왼쪽에 1을 놓을 수 있다.오른쪽도 마찬가지예요.
  • from pprint import pprint
    import sys
    
    import itertools
    def countstrs(s):
        return [(k, len(list(g))) for k, g in itertools.groupby(s)]
    import math
    
    q = int(input())
    for _ in range(q):
        n,k = map(int, input().split())
        s = input()
    
        res = 0
    
        dat = countstrs(s)
        #print(dat)
        l = len(dat)
        for i in range(l):
            ignoreLeft = False
            ignoreRight = False
            if i == 0:
                ignoreLeft = True
            if i == (l-1):
                ignoreRight = True
    
            if dat[i][0] == "1":
                continue
    
            cnt = dat[i][1]
            if ignoreRight is False:
                cnt -= (k)
            if ignoreLeft is False:
                cnt -= (k)
    
            #print("space", cnt)
            if cnt <= 0:
                continue
    
            res += math.ceil(cnt / (k+1))
    
        print(res)
    

    좋은 웹페이지 즐겨찾기