Codeforces Round 885 (Div. 2) - C. Vika and Price Tags

C. Vika and Price Tags

대회때 풀었던 문젠데 에디토리얼을 살펴보려한다.

---

$a_i=b_i$ 를 그냥 $a,b$ 라고 하자.

$a=b=0$ 이라면 모두 $0$이여서 신경쓸 필요 없다.

$a=b$ 라면 $a,b,0,b,b,0,\cdots$ 처럼 $0$이 나온다.

$a \ge b$ 라면 한 번의 연산 이후에는 $b, a-b$ 가 되고 이것의 합이 $a$ 라서 $a'+b'$ 의 합이 줄어든다.

$a < b$ 라면 두 번의 연산 이후에는 $b-a, a$ 가 되고 이것의 합이 $b$ 라서 $a'+b'$ 의 합이 줄어든다.

수가 유한히 감소할 수 있으므로 언젠가 $0$이 됨을 알 수 있다.

처음 $0$이 되는 순간까지 필요한 연산의 횟수를 $c$라 하자.

결국 $0,x,x,0,x,x,0,x,x,0,\cdots$ 처럼 되기때문에 주기 $3$이 중요하다.

따라서 $a=b=0$ 인 케이스를 제외한 모든 $c$가 $3$에 대한 동일한 나머지를 가져야 가능하다.

Solution 1

$wlog. a \ge b$ 라 하고 그렇지 않다면 연산 한 번을 진행해서 $b, b-a$ 를 만들어 $a \ge b$ 라고 하자.

연산의 진행을 본다.

$a,~b,~a-b,~a-2b,~b,~ a-3b,~ a - 4b,~ \cdots ,$ 처럼 진행된다.

이러한 규칙을 통해 $a=kb+r \quad (k \ge 0, 0 \le r < k)$ 이라 하면 일반화된 유클리드 알고리즘으로 해결가능하다.

$a,~b,~a-b,~a-2b,~b,~ a-3b,~ a - 4b,~ \cdots , a-kb, r$ 이 되는 시점을 본다.

$k$ 에 따라 $a-kb$ 가 언제 나오는지 보자(0-index).

k	처음 나오는 곳
1	2
2	3
3	5
4	6
5	8
6	9
…

$k$가 홀수라면 그 다음수가 $a-(k+1)b$ 인데 이는 $0$ 이하이므로 처음 나오는곳 바로 이전이 $b$ 임을 이용해

$f(b, a ~ \% ~ b)$ 를 호출한다.

$k$가 짝수라면 그 다음수가 $b$ 라 $f(a ~ \% ~ b, b)$ 를 호출한다.

두 경우 모두 진행된 횟수는 $k+\left\lfloor \dfrac{k}{2} \right\rfloor$ 만큼 진행된다.

예를 들어, $k=3$ 이라면 $4$ 만큼 진행되었고 현재 $b, a ~ \% ~ b$ 가 나오는게 맞기 때문이다.

int gcd(int a, int b) {  
   if (a == 0) return 0;  
   if (b == 0) return 1;  
   if (a == b) return 2;  
   if (a > b) {  
      int q = a / b;  
      int r = a % b;  
  
      if (q % 2 == 1) {  
         return gcd(b, r) + q + q / 2;  
      } else {  
         return gcd(r, b) + q + q / 2;  
      }  
  
   } else {  
      return gcd(b, abs(b - a)) + 1;  
   }  
}  
  
void solve() {  
   int n;  
   cin >> n;  
   vi a(n), b(n);  
   fv(a);  
   fv(b);  
   vi g(3);  
   debug(1);  
   for (int i = 0; i < n; i++) {  
      if (a[i] == 0 && b[i] == 0) continue;  
      g[gcd(a[i], b[i]) % 3]++;  
   }  
   for (int i = 0; i < 3; i++)  
      if (g[i] == acc(g)) {  
         cout << "YES\n";  
         return;  
      }  
   cout << "NO\n";  
}

Solution 2

아마 대회중에 내가 풀었던 방법이 이거인것같다.