Codeforces Round #539 (Div. 2) A ~ C

codeforces.com/contest/1113

Dashboard - Codeforces Round #539 (Div. 2) - Codeforces

 

풀은 문제: A, B, C

못 풀은 문제: D, E, F

풀이만 보고 풀은 문제:

코드와 풀이를 보고 풀은 문제:

 

 

난이도

A - 900

B - 1300

C - 1600

D - 1800

E - 2800

F - 2400

 

 

 

C번은 prefix로 하는 것까지는 바로 생각했는데, 같은 xor 값이 나올 때의 처리를 거의 1시간 30분만에 생각해냈다.

 

 

 

 

A. Sasha and His Trip

 

1번 도시부터 n번 도시가 있고, 각각 도시의 거리는 1L의 기름이 소모된다고 한다.

차에는 vL까지 기름을 채울 수 있고, i번째 도시에서는 1L당 i달러에 기름을 살 수 있다고 한다.

1번 도시에서 출발하여 n번 도시까지 가는데 필요한 최소의 달러를 구하시오

 

도시를 한 칸씩 이동할때마다 기름이 1달러씩 비싸지니까 1번 도시에서 기름을 꽉채우고, 두번째 도시부터 n-v번째 도시까지 계속 정차하여 1리터씩 기름을 사야 최소가 나올 것이다.

 

그래서 for문으로 구현하면 된다.

 

def main():
    n, v = map(int,input().split())
    if v >= n-1:print(n-1)
    else:
        ans = v #달러
        z = v #총 기름의 양
        for i in range(2,n):
            z += 1
            ans += i
            if z == n-1:
                print(ans)
                exit()

 

 

 

 

B. Sasha and Magnetic Machines

 

a[i]/x의 값은 정수여야하니 1과 a[i]를 제외한 a[i]의 약수로 나눌 수 있다고 볼 수 있다.

n은 50000이고, a는 100이므로 브루트포스로 하나하나 확인해도 상관이 없다.

정렬을 해서 가장 작은 값을 찾고, for문으로 하나하나 x의 값을 넣어보면 된다.

 

def main():
    n = int(input())
    a = [*map(int,input().split())]
    a.sort()
    ans = sum(a)
    val = sum(a)
    for i in range(n):
        k = a[i]
        z = []
        for j in range(2,k):
            if k%j == 0:z.append(j)
        for x in z:
            ans = min(ans, val - (k-k//x) + (a[0]*x - a[0]))
    print(ans)

 

(k - k//x) 와 (a[0]*x - a[0])는 뭐냐면 만약 [1, 9]이고 k = 9일 때 1과 9를 제외한 9의 약수는 3이므로 [3, 3]으로 바꿀 수 있을 것이다.

val = sum(a) = 1 + 9 = 10인데 이것을 3+3 = 6으로 바꿔야 하므로 1 + 9 - ( 9 - 3 ) + ( 3 - 1 ) = 3 + 3 이 된다.

 

 

 

 

 

C. Sasha and a Bit of Relax

 

먼저 xor 연산의 특징을 알아보면  x = y일 때 x ^ y = 0이라는 것이다.

 

문제에서 a[l] ^ ... ^ a[mid] = a[mid+1] ^ ... ^ a[r]인 개수를 구하라고 했는데 이건 a[l] ^ ... ^ a[r] = 0인 개수를 구하라는 것과 똑같은 말이라고 생각할 수 있다.

 

이것을 이용하여 prefix array를 만들어서 0을 제외한 값이 prefix array의 값에 있다면 (그 값이 나온 개수) - 1을 해주면 된다.

 

다음 예시를 보자

[ 1, 4, 2, 1, 3, 1, 2, 0, 3, 0 ]

위와 같은 prefix array가 있으면

 

a[0] = 1이고, a[3] = 1이다.

그래서 a[3] ^ a[0] = 0 임을 알 수 있다.

a[0] ^ .... ^ a[5] = 1인데 이것은 a[5] ^ a[0] = a[5] ^ a[3] = 0 임을 알 수 있다.

그래서 a[l] ^ ... ^ a[r] = 0임을 확인하려면 a[r] ^ a[l-1]로 확인하면 되는 것을 확인할 수 있다

 

그리고 a[7] = 0, a[9] = 0 이고 a[9] ^ a[7] = 0인 것을 알 수 있다.

이것을 통해 0은 (그 값이 나온 개수)를 더해야하는 것을 알 수 있다.

 

여기까지 왔으면 이제 위치에 대해서 따져봐야한다.

선택하는 배열의 길이가 짝수여야하므로 r이 짝수면 l-1도 짝수가 될 수 밖에 없다. 반대도 마찬가지이다.

그래서 답을 구할 때는 같은 xor값이 나와도 현재까지 prefix array의 길이가 짝수인지 홀수인지 구별해서 답을 구해야한다.

 

def main():
    n = int(input())
    a = [*map(int,input().split())]
    ans = 0
    x = 0
    D = [[0]*2 for _ in range(2**20)]
    D[0][1] = 1
    for i in range(n):
        x ^= a[i]
        ans += D[x][i % 2]
        D[x][i%2] += 1
    print(ans)