846, 842 div2 virtual

https://codeforces.com/contest/1780

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

A.

숫자 배열이 주어지고, 이 중 세 개의 원소를 합쳐서 홀수가 될 수 있는지 묻는 문제

 

홀수 = 홀수가 홀수가 필요하다 

따라서 홀수가 1개도 없으면 불가능 

짝수가 하나만 존재해서 - 홀,홀,짝 불가능

 

이 두가지 경우만 체크하면 된다. 

 

원소까지 출력해야 하므로 홀/짝을 나누어서 받으면 가능하다. 

 

B.

[l1, + ... + r1], [l2 + , .... , + r2], .. 나누는 방법은 2개 이상

대충 이렇게 subsegment들의 gcd를 최대로 만드는 경우

 

gcd(a1, a2, a3, ... ) <= gcd(a1+a2, a3, ... ) 이다. 

 

왜냐하면 gcd(a, b, c) = gcd(gcd(a, b), c) 이므로 위 식은 gcd(a1, a2, ax), gcd(a1+a2, ax)라고 볼 수 있다. 

a1+a2 는 gcd(a1, a2, ax)를 약수로 갖고 그 역은 성립하지 않으므로

 

따라서 max (중간지점 1 < i < N) 에 대해서 출력하면된다.

 

D.

interactive 문제이다. 

 

어떤 한 가지 수를 생각하고 그 수의 이진수에서 1의 갯수를 출력해준다. 

그리고 내가 어떤 수를 말하면 그 어떤 수에서 말한 수의 1 갯수를 출력 

이걸 업데이트하며 반복해서 그 처음 생각한 수가 어떤 수인지 맞추는 문제

 

처음에 조작을 하다보니 가장 오른쪽 비트를 가지고 만지면 가능하다는 것을 알았다

그렇지만 범위 1e^9에서 30번의 횟수만에 맞출 수 있는지는 판단하지 못하고 답으로 알게됨

 

더 최적화된 방법은 k라는 답변이 왔을 때 2^k를 뺀다고 하는 것이다. 

 

만약에 다음 대답이 k-1이라면 2^k의 비트가 1이었다는 소리이고, 

그렇지 않으면 0이었고 왼쪽 어디 비트가 1이었는지 알 수 있다. 

 

예를 들어서 

 

X10011이고 k=3인 상황을 한 번 보자 

3번째 비트를 빼면 X01111이 되고, k=4가 된다.

 

K now - K before + 1 은 이어진 1의 개수가 된다. 

 

이것은 무조건 한 번의 operation에 하나의 bit가 줄어듦이 보장되고 1e^9에서 30번안에 답을 맞출 수 있다.

 

https://codeforces.com/contest/1768

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

A.

 

k가 주어지고 1<= x < k,  x! + (x-1)! 이 k의 배수가 되도록 하는 x를 출력하는 문제

x! + (x-1)! = (x+1)(x-1)!이므로 x가 k-1이라면 (k-1+1)(k-1-1)! k의 배수가 된다.

 

B.

permutation이 주어지고, 이 중 원하는 것을 최대 k개 뺀 뒤 정렬해서 맨 뒤에 집어넣는다. 

정렬이 되기 위한 operation 최소 

 

1 .. 2 ... 3 ... 이런식으로 1부터 순서가 몇 까지 맞는지 센다. 

나머지는 다 빼고 뒤에 집어넣는다. 어차피 앞에꺼부터 정렬이 되어야 되기 때문에 

2345671 이런식으로 숫자가 주어져도 모두 다 뒤로 넣어서 재정렬해야한다. 

 

최대 k니깐 나누어떨어지면 cnt/k 그렇지않으면 cnt/k + 1이된다. 

 

C.

두 개의 permutation a,b가 존재 

ci = max(ai, bi)

수열 c가 주어지고 a, b를 채울 수 있는지 문제

 

c에 하나만 주어진 수는 a, b에 동일하게 채운다.

두개가 주어진 수는 하나씩 넣는다.

먼저 작은 것부터 채운다. -> 작은 것이 더 가치있기 때문에 (활용도가 훨씬 높다.)

 

이미 쓴 것들은 체크하면서 채우면 된다. 

 

채우는 과정에서 정렬되고 삭제를 쉽게하는 어떤 자료구조가 필요한데 set으로 구현하였다.

 

D.

두 원소의 위치를 바꾸어서 정렬을 시키는 문제

 

근데 정렬이 아니라 인접한 두 원소의 위치가 딱 하나 다른 배열의 형태로 정렬을 시켜야 한다. 

 

먼저 그대로 정렬하는 방법을 센다.

 

임의의 두 원소의 위치를 바꾸어서 적절한 위치에 위치시키는 것은 이 배열에서 cycle이 몇 개 존재하는지 세면 된다. 

cycle의 수를 cycles라고 하면 n-cycles가 정렬하기 위해 필요한 operation 수이다. 

 

왜냐하면 하나의 수를 정렬시키기 위해서는 최대 1번이 필요하다. 

하나하나 이동을 해서 모든 원소들이 정렬이 되는 경우이므로 cycle에 있는 모든 원소들이 cycle의 크기 -1 operation을 하였을때 모두 정렬이 된다는 의미이다. 

 

따라서 잘 계산을 하면 n-cycles가 총 operation 수가 된다. 

 

근데 여기서 인접한 두 원소의 위치가 딱 하나 다른 배열로 만드는 방법은 어떻게 할까?

두 개의 원소가 같은 cycle에 있으면 cycles가 하나 늘게된다. 

 

그렇지 않으면 하나 뺀다.

 

설명을 하자면 

원래 x -> k, y -> k+1 을 가르키는 데 x -> k+1, y -> k를 가리키도록 바뀌었다고 해보자

 

 

 

1) x, y가 원래 같은 cycle에 있었다면 

 

x -> k -> component1 -> y -> k+1 -> component2 -> x 꼴이었을 것이고, 

x->k+1, y->k로 바뀌면

x-> k+1 -> component2 -> x, y -> k -> component1 -> y 꼴의 cycle로 나뉘게 된다.

 

2) 다른 cycle이었다면 

 

x -> k -> component1 -> x, y -> k+1 -> component2 -> y 가 

x -> k+1 -> component2 -> y -> k -> component1 -> x으로 서로 다른 두 개의 cycle이 합쳐지게 된다.