edu 130, 804, 803 virtual

edu 130

https://codeforces.com/contest/1697

Dashboard - Educational Codeforces Round 130 (Rated for Div. 2) - Codeforces

A

쉬면 에너지 회복 아니면 에너지 소비해서 이동,

현재 에너지 m 

 

따라서 1에서 n으로 이동할 때 필요 에너지 m이하면 0만큼 휴식

아니라면 모든 필요 에너지-m 만큼 휴식 필요 

 

B

x 개 산다면 y개가 공짜 

공짜 금액 최대로 

 

가장 비싼 것들로만 산다.

 

C

주어진 string s1에서 

ab 는 ba로 바꿀 수 있고,

bc 는 cb로 바꿀 수 있다. 

 

s1을 s2로 바꿀 수 있는지에 대한 문제

 

a,b,c의 관계에 대한 operation이 주어져 있는데 

두 개의 operation 모두 b와 연관되어 있다. 

 

따라서 b를 중심으로 생각

 

b는 a의 앞으로 이동 가능

b는 c의 뒤로 이동 가능 

 

근데 a,c는 서로 앞뒤가 바뀔 수 없다. 

따라서 s1에서 가능한 모든 string을 만들어 보고, b를 제거한다면 

모든 string의 모양이 같다는 걸 생각할 수 있다. 

 

마찬가지로 s2도 s1에서 만들었다면 b를 제거한 모양이 같아야하는데 

 

단순하게 b를 제거한 모양만 같다면 s2로 변환이 가능한 것일까

 

그러려면 b는 모든 곳으로 마음대로 이동이 가능해야 하는데 

bbba

에서 

abbb는 불가능하다. 

 

따라서 뭔가 추가로 확인해야 한다. 

 

b를 뺀 모습이 같아야 하고, 

a는 원래 자리보다 더 뒤로밖에 이동이 안되고, 

c는 더 앞으로 밖에 이동이 안되는데 

 

이 점을 확인하면 된다.

 

세 개처럼 보이는 변수에서 하나 고정해놓고 생각하는게 핵심인듯

 

804

https://codeforces.com/contest/1699

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

A

(a ^ b) + (b ^ c) + (c ^ a) = x 

x가 주어지고 a,b,c를 아무거나 출력

 

홀수가 불가능한것 같아서 

x를 홀수일때 생각해보자 

 

x 홀수라는 의미는 x의 마지막 비트 = 1

 

위 식의 연산을 거꾸로 하면 

 

(무언가) + (c ^ a)

 

마지막 비트 생략

 

case 1 : 무언가 1 , (c^a) = 0

 

c, a 1 and 무언가 1

 

(a ^ b) + (b ^ c) = 1

b가 1이든 0이든 불가능

 

위와 같이 모든 케이스에 대해서 생각해보면 불가능 

 

따라서 홀수라면 불가능 

짝수라면? 

 

c를 0으로 두면 식이 

(a^b) + a+b로 바뀜

따라서 그냥 a와 b를 n의 절반으로 하면 됨

 

B

인접한 두개만 현재 위치의 색과 달라야 한다.

 

뭔가 간단한 모습이 있을 것 같아서 몇개 그려봄

 

1 0 

0 1 

 

이 모습과 인접한 곳은 

 

0 1

1 0 

 

과 인접한 곳은 

 

1 0

0 1

 

반복되면 가능 

 

가능한지 판단은 

하나일때 한줄일때 

두줄일때 이정도만 확인해보면 계속 반복되는 모양이기에 증명된다고 생각

 

구현은 1 0 1 0 이런꼴로 미리 matrix를 작성을 해두고

1이면 

1 0

0 1

 

0이면

0 1

1 0 을 출력하면 된다. 

 

C 

 

a 순열이 주어지고 a순열과 모든 substring l,r 범위에서 MEX의 값이 같게 나오는 순열의 가짓수를 반환하는 문제 

 

MEX함수는 0부터 세었을 때 안나온 첫번째 수를 반환하는 함수

 

우선 0이 포함된다면 거기의 MEX값은 무조건 1이상 

0, 1이 포함된다면 2이상 

 

이런식으로 나아가기 때문에 

 

0부터 생각을 해보자 

 

0의 위치가 원래 그 자리가 아니라면 MEX값이 같게 나올 수 없으므로 고정

그러면 1은 1의 위치가 달라지면 값도 달라진다 따라서 고정

 

2의 위치는 ?

 

뭔가 마찬가지로 달라질 것 같기도 하지만 

 

0 ..2 .. 1  이런 꼴이면 바뀌어도 될 것 같다. 

0, 1 사이의 범위에서 바뀌어도 좋다 

 

0... 1...2라면 마찬가지로 고정

 

3의 위치는? 

0 .....2...3.1에서 어디에 있어야 할까 

어차피 0과 1을 고를때 값은 4이상이므로 0,1사이 아무데나 있어도 가능할까?

 

ㅇㅇ 

 

근데 

0....1..3..2 꼴이라면? 

3이 1의 위치로 간다면 불가능 왜냐면 0, 1의 index를 고르게 된다면 2이던 값이 

1이 되므로 불가능

 

이 소리는 x의 위치를 조사할 때 

MEX의 값이 x가되는 최소범위 l,r에 대해서 밖에 있으면 고정, 

안에 있으면 max(l,r) 큰 모든 곳에 대해서 위치 변경 가능 => MEX 값이 x가되는 최소범위가 l,r이므로 

 

803

https://codeforces.com/contest/1698

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

 

A

배열이 주어지고, a^b^c = d인 d를 구하는 문제

a^b^c = d인 것이 존재한다면 

a^b^c^d = 0이고, 

a^b^d = c이다. 

결론은 아무거나 출력하면 된다.

 

B

operation : k+1개를 선택해서 +1 가능

어떤 array가 주어질 때 거기에서 

operation 마음대로 써서 양쪽의 합보다 큰 우뚝 솟은 봉우리의 최대 갯수를 만들어라 

 

k=1이상이므로 하나만 선택이 불가 

 

이 소리는 무엇이냐면 

 

하나만 우뚝 솟게 만드는게 불가능 무조건 인접한 거랑 같이 솟기때문에 더 많은 양을 만드는 게 불가 

처음 갯수 출력하면 됨

 

C

세개의 덧셈에 대해서 닫혀있게 만드는 문제

 

5개 이상이면 무조건 

양 음 000....으로 구성되어있어야함 

 

양수가 많으면 양수끼리 더해서 계속해서 더 큰양수가 있어야함 

음수도 마찬가지 

 

따라서 

양 0 0

양 음 0

음 0 0 

모두 가능하게만 하면 된다. 

 

근데 왜 5개 이상이냐 

 

3개면 양 양 음 도 가능 

 

4개면 양 음 음 양 가능 

 

그러므로 3,4에 대해서는 모든 케이스 가능한지 백트래킹으로 

5개 이상이면 저걸로 가능

 

D

interactive 문제 

 

어떤 범위를 물어보면 그 범위 수들을 정렬해서 출력해주고, 

딱 하나 원래 위치인 것이 존재 

 

예를 들어서 

 

3, 2, 1 이 존재할 때 

1,2,3으로 출력해준다

 

어떤 index범위에 해당하는 수의 개수를 세준다. 

왜냐하면 만약에 그 범위에 있지 않는건 확실하게 교체가 있었다는 것

그리고, 그 개수가 홀수인 경우가 바뀌지 않은 수가 존재하는 곳임

 

이 이유는 전체 길이가 홀수이기 때문인데 

어떤 범위에 해당하는 수가 짝수개이면 자기들끼리 바꾼거 

 

홀수개이면 자기들끼리 바꾸고, 나머지 하나 홀로남음

 

이걸 이분탐색으로 계속 쿼리 날리고 홀수인걸로 범위 좁혀서 날리면 

 

2^15 = 3만정도이므로 1만의 수 범위에서 충분히 가능하다.