Codeforces Round 871 (Div. 4) F,H 풀이

코드포스를 시작했고 제 알고리즘 실력은 쓰레기란걸 알며 겸손해졌습니다.

버츄얼을 돌렸는데 재밌는 문제를 봐서 풀이를 작성합니다.

 

H. Don't Blame Me

https://codeforces.com/contest/1829/problem/H

Problem - H - Codeforces

 

문제

array의 subsequence를 뽑아내고, subsequence의 원소를 모두 AND한 결과의 비트수가 k가 되는 

subsequence의 개수

 

아이디어

1. k도 작고 배열에 원소로 들어오는 수는 0~63(6비트)으로 범위가 좁습니다. 그걸 이용해야할 것 같습니다.

2. 따라서 우리는 1이 k개 있는 비트를 다 구할 수 있습니다.

0~63을 보며 비트수를 세고 만족하는걸 미리 구해놓습니다. 어차피 수 범위가 적으니 각자만의 방법으로...

bitcnt = [[False] * 64 for _ in range(7)]  # bitcnt[k][n]: True면 n의 비트수는 k
for num in range(64):
    ref = 1
    tmp = 0
    while ref <= num:
        if ref & num:
            tmp += 1
        ref = ref << 1
    bitcnt[tmp][num] = True
    cntbit[num] = tmp

3. a AND b <= max(a,b)가 보증됩니다. 보통의 경우엔 1을 지워버리니까요 따라서 우리가 필요한 숫자는 0~63입니다.

4. a AND b == b AND a입니다. 순서는 관계 없습니다.

5. 인덱스 i+1인 원소부터 subseqence에 추가하고 싶지 않고 array[i]를 subseqence에 추가할 때 우리가 AND해서 얻을 수 있는 수는

array[:i](i 전까지 슬라이싱한 것)에서 만들 수 있는 모든  subseqence의 원소를 AND한 결과에다가 각각 array[i]를 AND를 해보면 알 수 있습니다.

6. array[i]를 사용하고 싶지 않을 수 있습니다.

이럴 땐 array[:i]에서 만들 수 있는 모든 subseqence의 원소를 AND한 결과를 그대로 쓰면 됩니다.

7. 이 문제는 5~6을 볼때 DP로 푸는 것이 적당해보입니다.

 

유형

DP 

 

풀이

우리들이 필요한건

1. i번째 원소를 사용했나 or 안했나

2. 무슨무슨 결과가 나왔나, 여기서 결과는 경우의수

입니다.

따라서 dp를 다음과 같이 선언합니다.

N, K = map(int, input().split())
A = list(map(int, input().split()))
# A의 원소 x개를 and해서 비트수가 k가 되게 하기
# a의 원소는 2^6 - 1 이하
dp = [[[0] * 64 for _ in range(N)] for _ in range(2)]  # dp[s][n][k]: (s:0사용안함 s:1사용함) 해당 숫자를 만드는 경우의 수

 이제 이 테이블을 채워주면 됩니다.

rest = 10 ** 9 + 7
dp[1][0][A[0]] = 1 # 초기값
for i in range(1, N):
    num = A[i]
    dp[1][i][num] = 1
    for s in range(2):
        for n in range(64):
        	#n = (지금까지 나온 모든 결과) AND num 이라할 때 n이 나오는 경우의 수 
            dp[1][i][n & num] = (dp[s][i - 1][n] + dp[1][i][n & num]) % rest
            # 사용안할거면 이전 결과 그대로
            dp[0][i][n] = (dp[s][i - 1][n] + dp[0][i][n]) % rest

 

dp[s][-1][n]은 상태가 s일때 n을 만드는 모든 subseqence의 개수가 될겁니다.

우리는 비트수가 k가 되는 수들을 구했으므로 n에다가 그 값을 대입하면 됩니다.

 

 

 

 

G. Hits Different

https://codeforces.com/contest/1829/problem/G

Problem - G - Codeforces

문제 

하나의 캔이 무너지면, 그것의 위에 걸쳐있는 1~2개의 캔도 무너집니다.

따라서 연쇄적으로 많은 캔들이 무너질 것입니다.

특정한 캔 하나를 쳐서 무너뜨렸을 때, 그 캔을 포함해 무너지는 모든 캔의 숫자들을 각각 제곱한 합을 구하는 문제입니다.

 

아이디어

1. 우선 캔이 몇층에 있는지 알아야합니다.

맨 윗층을 0층이라 해봅시다.

각 층의 맨 왼쪽은 S[i] = S[i-1] + i,S[0] = 1 꼴이 된다. (한 층이 지나면 추가로 하나의 캔을 더 놓으므로)

제한이 백만이므로, 몇층까지 탑이 있고(대충 500층 보다 적다) 각 층마다 제일 왼쪽이 몇인지 구합니다.

캔이 주어졌을때, 이분탐색으로 몇층인지 구할 수 있습니다.

2. 우선 캔이 각 층에서 어디인지 구해야 합니다.

각 층이 담고있는 숫자는 S[i] ~ S[i+1]-1일 것입니다.

역시 이분탐색으로 구할 수 있습니다.

3. 층 R에서 캔이 C번째에 있디할때

R-1에서 C번째캔과 C-1번째캔은 C위에 걸쳐있습니다.

4. 각 층마다 무너지는 범위를 구해야할 것입니다. 범위를 안다면 그 윗층에서 무너지는 범위도 구할 수 있습니다.

무너지는 범위의 제곱의 합을 알아야하므로,

우린 애초에 연결리스트 형식으로 탑을 직접 만들고(2차원 배열로 만들어서 O(N^2)이면 안된다. 연결리스트면 O(N)이면 된다.), 각 층마다 누적합을 구해야합니다.

start = [1]  # 몇번쨰 줄인가
for i in range(1, 1415):
    start.append(start[-1] + i)
imos = [[1]]
real = [[1]]
for r in range(1, 1415):
    imos.append([0] * (r + 1))
    real.append([0] * (r + 1))
    s = start[r]
    imos[-1][0] = s ** 2
    real[-1][0] = s
    for i in range(1, r + 1):
        imos[-1][i] = imos[-1][i - 1] + (s + i) ** 2
        real[-1][i] = s + i

 

유형

누적합, 구현

 

 

풀이

층을 구할때, 우린 (주어진 캔보다 큰 숫자중 그중 최소의 층) - 1을 하면 됩니다.

이분탐색 upperbound에서 리턴한 값에다가 -1을 해주면 됩니다.

lowerbound를 적용하기엔 리턴하는 값이 원래층 + 1 or 원래층일 것이고 이를 나눠야하므로 귀찮아요.

층을 구했으면 일반 binary search를 적용하든, 위의 upperbound - 1을 적용하든 아무거나 써서

결국 캔의 위치를 구할 수 있습니다.

그렇게 캔의 위치를 구했으면

직접 무너뜨리면 됩니다.

특정 층에서 a~b 범위의 캔이 무너졌으면

그 다음은 아이디어 3번에 의해

a-1~b캔이 무너질 것입니다.

물론 탑의 범위를 넘어서서 무너질 순 없을 것이므로 정확히는

max(0,a-1) ~ min(각 층의 컵의 개수 - 1,b) 범위가 무너질 것입니다. 

그렇게해서 시작층에서 하나하나 층을 올라가며 해당 값을 구하면 됩니다.

for _ in range(int(input())):
    N = int(input())
    R = upperbound(start, N, 1415) - 1  # 무슨 줄인지
    C = upperbound(real[R], N, len(real[R])) - 1  # 몇번째 칸인지
    ans = 0
    s, e = C, C
    r = R
    while R >= 0:
        e = min(e, len(real[R]) - 1)
        ans += imos[R][e] - (imos[R][s - 1] if s > 0 else 0)
        R -= 1
        if s > 0:
            s = s - 1
    print(ans)

더 효율적으로

해당문제를 위 방식으로 풀이하면

max(1000000,(testcase 개수) * R) 의 목잡도입니다.

후자를 (testcase 개수) * 1 로 줄일 수 있습니다.

정사각형 격자를 생각해봅시다.

즉 왼쪽 맨 위 꼭지점부터 순서대로 대각선대로 분할하면

1,2,3,4,... 문제에 만족하는 개수만큼 셀들을 분할할 수 있습니다.

즉 캔의 위치는

1. 몇번째 대각선인가

2. 대각선에서 순서가 몇번째인가로 알 수 있습니다.

캔 하나(빨간색)가 무너진다면

그 위 풀이와 동일하게 바로 전의 대각선에서 순서가 동일한것과, 그 순서 -1인것이 무너질 것(노란색)입니다.

즉 자신의 위의 있는셀과, 자신의 왼쪽에 있는셀이 무너집니다.

이것이 연쇄적으로 진행돼서 최종적으로 어떤 것들이 무너지는가를 보면

정답은 0,0과 처음 무너뜨린위치를 꼭지점으로 하는 직사각형 영역이 됩니다.

이는 누적합으로 O(1)로 구할 수 있습니다.