CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)


image.png

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

600점 겟

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

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

A. New Scheme (-881)Permalink

A. New Scheme

그냥 해주면 된다.

B. Default Price (-417)Permalink

B. Default Price

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

C. Standings (605)Permalink

C. Standings

그냥 정렬해주는 문제

D. Snuke Maze (619)Permalink

D. Snuke Maze

BFS 기본 문제

E. MEX (1042)Permalink

E. MEX

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

F. Vouchers (1284)Permalink

F. Vouchers

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

G. Minimum Xor Pair Query (2008)Permalink

G. Minimum Xor Pair Query

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

x,zx,z의 이진수 표현에서 큰 비트부터 같다가 처음으로 달라지는 비트를 kk 라고할 때, xx는 거기가 00이고 zz11이다.

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

yyk+1k+1 이상의 비트는 x,zx,z와 같을 것이고 거기가 00이라면 xy<2kx \oplus y < 2^k 이다. 거기가 11이라면 yz<2ky \oplus z < 2^k 이다.

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

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

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)Permalink

Ex. Make Q

Tags:

Categories:

Updated:

Comments