log 2021-07-03
sport
cf 729 Div2
A. Odd Set
https://codeforces.com/contest/1542/problem/0
n개의 페어를 합이 홀수가 되도록 만들 수 있는지 묻는 문제. 홀짝 성질을 사용하면 풀 수 있다.
홀+홀=짝 짝+짝=짝 홀+짝=홀 즉, 홀수 짝수 개수 비교한 것이(차이가) 2m 차이가 나야 한다. 아 임의 페어로 만드는 것이 아니라, n개의 페어를 다시 홀수 합의 n개의 페어로 만들 수 있냐는 것이다. 따라서 홀~짝 차이가 0이어야 한다.
B. Plus and Multiply
https://codeforces.com/contest/1542/problem/B
주어진 a,b에 대해, x가 집합에 있다면, xa, x+b도 집합에 포함될 때, 특정 원소가 포함되는지 확인하기
x의 시작은 1이다.
자칫 최적화하려다 답을 찾지 못할 수도 있다. dp인가? 아니면 그리디인가??
1, a, 2a, 3a, … 1+b, a(1+b), 2a(1+b), … 1+2b,a(1+2b) | a+2b … a+2ab
음.. 일단 a 가 곱셈으로 들어가므로 a에 대해 줄이는 게 좋아보이는데, 너무 빼다가 틀리게 될 수 있다. n을 분해하다가, 더 이상 a로 나뉘어 지지 않을때, 어떻게 검사를 해야 할까?? 남은 n은 1, 1+b, 1+2b, a+2b,2a+2b
3,5에 대해, 24 = 3*8 -> 8 = 5 +
a(a+b) = 3(3+5) 3(3(3+5)+5) …
한 백만 수준의 크기 제한이 있다면 배열을 써서 마킹할 텐데, n이 최대 10억이므로 이 방법을 사용할 수가 없다.
아니면, a로 나뉘어 지지 않으면 b를 빼는 그리디 방식은 어떨까?? 그러나, b를 뺄 때, 몇 번이나 빼느냐에 따라 해답을 찾지 못할 가능성이 있을 듯하다.
최소공배수 개념을 사용하면 어떨까. kxa와 x+ib가 같아지는 지점을 최소공배수로 두면.. 그러나, 배수에 따라 단순 이걸로 % 계산해버리면 안 될듯한데..
1, a, 1+b, 1+2b, a(1+2b), aa(1+2b), a(aa(1+2b)+3b)
이렇게 이루어져 있다면, 거꾸로 그리디로 a로 나눈 다음, 안나뉘어 지면, 나뉘어 질 때까지 b를 빼는 것을 반복해도 가능은 해 보인다. 그런데, 그렇게 할 경우 시간초과를 방지해야 한다.
aX+kb 꼴에서 가장 작은 k를 구해야 한다. 그러면 가장 가까운 aX꼴까지 내려가는 것이 목적. 이 값을 a로 나눈 나머지는 kb다. curr = (aX+kb), curr%a = kb, k=(curr%a)/b next_curr = aX = curr - kb = curr - (curr%a)
틀렸다. a로 나눈 나머지는 kb%a라서 틀리다.
아니면 curr를 b만큼 뺀 다음, a로 나눠서 소수부를 버리면 가장 덜 뺀 다음 a배수를 구할 수 있지 않나. 그런데, 생각해보니 다음 a의 배수가 동시에 curr에서 b만큼 뺀 수이기도 해야 한다..
curr = aX -> aX-kb = (a-j)X = aY jX = kb k = jX / b = j aX / ab = j * curr / (ab)
모르겠다. 중국인의 나머지 정리도 아닌 듯하고, 간단한 개념같은데 못풀겠다.
pseudo
원격 서버 셋업 완료.
여전히 네트워크 에러가 뜨는데, 로그를 찍어 보니 CERT관련 에러가 난다. 아마 이것을 해결하려면 HTTPS를 적용해야 할 듯하다.
Comments