CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)

CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)

---

제대로(?) 처음 참가해본 엣코더

600점 겟

빨리 풀고 $G$는 그냥 던지고 갔지만 1900점대 퍼포가 나왔다. 코포로 치면 오렌지퍼포인것같다.

업솔빙은 $G$만 의미있을것같다.

A. New Scheme (-881)

A. New Scheme

그냥 해주면 된다.

B. Default Price (-417)

B. Default Price

딕셔너리를 이용해서 잘 구현해주면 된다.

C. Standings (605)

C. Standings

그냥 정렬해주는 문제

D. Snuke Maze (619)

D. Snuke Maze

BFS 기본 문제

E. MEX (1042)

E. MEX

DP로 뒤에서부터 X인데 0,1,2 인 것의 개수와 E인데 총 $8$가지 어떤 수들이 나왔었는지 여부를 검사해주면 M이 나왔을 때 E의 개수에 따라 MEX를 구해서 정답에 더해주면 된다.

F. Vouchers (1284)

F. Vouchers

가장 $D_i$가 큰 쿠폰들부터 보면서 현재 아이템들 중 $L_i$ 이상인 가장 작은것부터 사용해주면 된다.

G. Minimum Xor Pair Query (2008)

G. Minimum Xor Pair Query

$x<y<z$ 일 때, $\text{Min}(x \oplus y, y \oplus z) < x \oplus z$ 라고 주장한다.

$x,z$의 이진수 표현에서 큰 비트부터 같다가 처음으로 달라지는 비트를 $k$ 라고할 때, $x$는 거기가 $0$이고 $z$는 $1$이다.

그곳의 비트를 $2^k$ 라고 하자.

$y$도 $k+1$ 이상의 비트는 $x,z$와 같을 것이고 거기가 $0$이라면 $x \oplus y < 2^k$ 이다. 거기가 $1$이라면 $y \oplus z < 2^k$ 이다.

$x \oplus z \ge 2^k$ 이므로 증명된다.

따라서 set 같은것에 오름차순대로 수를 관리하며 인접한 것들의 $xor$ 값만 관리해주면 된다.

void solve() {  
   int q;  
   cin >> q;  
   int mn = INT_MAX;  
   pi mx_pair;  
  
   multiset<int> val, val_xor;  
  
   while (q--) {  
      int cmd, x;  
      cin >> cmd;  
      if (cmd == 1) {  
         cin >> x;  
         auto it = val.insert(x);  
         int prev = -1, nxt = -1;  
         auto it_nxt = it;  
         it_nxt++;  
         if (it_nxt != val.end()) nxt = *it_nxt;  
         if (it != val.begin()) {  
            --it;  
            prev = *it;  
         }  
         if (nxt != -1 && prev != -1) val_xor.erase(val_xor.find(prev ^ nxt));  
         if (nxt != -1) val_xor.insert(x ^ nxt);  
         if (prev != -1) val_xor.insert(x ^ prev);  
      } else if (cmd == 2) {  
         cin >> x;  
         auto it = val.erase(val.find(x));  
         int nxt = -1, prev = -1;  
         if (it != val.end()) nxt = *it;  
         if (it != val.begin()) {  
            --it;  
            prev = *it;  
         }  
         if (nxt != -1) val_xor.erase(val_xor.find(nxt ^ x));  
         if (prev != -1) val_xor.erase(val_xor.find(prev ^ x));  
  
         if (prev != -1 && nxt != -1)  
            val_xor.insert(prev ^ nxt);  
      } else {  
         cout << *val_xor.begin() << endl;  
      }  
   }  
}

Ex. Make Q (2861)

Ex. Make Q