log 2021-07-08
sport
cf 730 div 2 review
해설: https://codeforces.com/blog/entry/92582
- A
- 유클리드 호제법에서도 나온 최대공약수의 성질로 풀이. GCD(a,b)=GCD(a-b,b) (if a>b)
- B
- 모든 쌍의 차이 합이, 균등 분배할 때 가장 적어진다는 것을 직관적으로 생각했는데, 증명이 적혀 있다. 복잡해서 잘 모르겠지만, 차이가 2 이상인 원소가 하나라도 있다면, 그 둘을 분배해서 같게 만드는 것이 항상 답을 더 작게 할 수 있다는 것이 핵심인 듯하다.
p,p+2,기타 원소들 s가 있다고 치면, f(a,b)=a와 b들의 차이합 이라고 정의할 때, 다음과 같이 계산된다: f(p,p+2)+f(p,s)+f(p+2,s)=2+f(p,s)+f(p+2,s) =2+sum(|p-s1|+|p-s2|+…+|p-sn|)+sum(|p+2-s1|+|p+2-s2|+…+|p+2-sn|) 그런데, p,p+2를 p+1,p+1로 분배하면 다음과 같다: f(p+1,p+1)+f(p+1,s)+f(p+1,s)=2f(p+1,s) =2sum(|p+1-s1|+|p+1-s2|+…+|p+1-sn|) 이 때 아래가 항상 더 작음을 증명해야 하는데.. 어떻게?
어떤 원소 sk와, p,p+1,p+2의 관계에 대해 생각해보자. p,p+2가 모두 sk보다 작다면, |p-sk|+|p+2-sk| = 2sk - p - (p+2) 이다. p+1과는 2 * (sk - (p+1))이 되므로, 1번 - 2번 = 2sk - 2p-2 - (2sk - 2p -2) = 0이다. sk가 p,p+2 사이에 있다면, f(p,sk)+f(p+2,sk) = p+2 - p = 2이다. 2f(p+1,sk) = 2|p+1-sk| < 2 ($\because$ |p+1-sk| < 1) p,p+2가 모두 sk보다 크다면, 마찬가지로 차이가 0일 것이다.
모든 경우에 f(p,s)+f(p+2,s) >= 2*f(p+1,s) 이므로, 아래가 더 작다.
- C
감쇠율 v가 0.1이상이므로, 생각보다 시행 횟수가 적기 때문에, 완전탐색으로 구현하면 된다고 한다. 나도 dfs로 다 찾게 했는데, 소수 약등호 함수 구현을 못하겠어서 그부분은 긁어왔다.
- D
대화형 문제. 패스워드를 물어볼 때마다 비밀번호가 바뀌는데, k 베이스 XOR로 변한다. 기존 x에서, y인지 물어보면 x XOR_k z = y 인 z로 비밀번호가 변한다.
5 xor 7 = 101 111 212 mod 2 =010
x y z 101 010 -> 111
처음 비밀번호는 모르고, 이후로도 계속 모른다. 아마도, 어떤 시작 비밀번호든 맞추도록 하는 절차가 있는 모양이다. 어떻게?
a xor b = c
a b c
0
111 111 000
111 110 001
101 121 222
어떤 한 비트를 찍는 횟수는 최대 k, 비트마다 찍으면 k^20만 으로 무조건 시간초과다.
101 010 222
012 201
k=3
x z y 0 x 0 = 0 1 x 2 = 0 2 x 1 = 0
0 x 1 = 1 1 x 0 = 1 2 x 2 = 1
0 x 2 = 2 1 x 1 = 2 2 x 0 = 2
a x (p - a) = p a x (p - a) % k = p a x (k - a) = 0
a -> (p-a)%k -> k-(p-a)%k
도저히 모르겠어서 힌트 봄. 힌트 본 결과, 이전 쿼리의 효과를 제거하면서 다음 질문을 하는 방식으로 풀 수 있다고 한다. 또한, 다음 k비트 z = y - x mod k이다. 즉, 어떤 쿼리i에서 a를 물어보면, z = (a - x) mod k 이므로, 다음 쿼리에서 b를 묻고 싶다면, (a+b)mod k를 하면 되나? z2 = ((a+b)mod k - z) mod k = ((a+b)mod k - (a-x) mod k) mod k = (b + x)mod k
내일 다시 정리 예정
Comments