Codeforces Round 922 (Div.2) E번

• 링크

https://codeforces.com/contest/1918/problem/E

• 푼 방법

Rating 이 2200인 만큼 정말 어려운 문제였고, 결국 답을 봤다.

하지만, 예측한 사항들이 꽤나있다.

증명을 하지 못해서 실제로 진행하지 못했던, divide and conquer 방식도 생각했었다.

그리고 x 값을 계속 유지하는 생각도 했지만, 1 과 n 을 구해서 x 값을 지정해둔 값으로 계속해서 유지하는 것.

이것을 찾아내지 못했다.

그래도 에디토리얼을 보며 풀면서 많은 것을 배울 수 있었다.

문제의 핵심은 이것이다.

middle 값을 정해놓고, 그것보다 큰 값의 포지션, 그것보다 작은 값의 포지션을 저장하고

둘을 분할정복으로 진행해 m을 가지는 아이의 position 을 확정짓는다.

그 이전에 x 값을 원하는대로 자유로이 낮은값,큰값으로 움직일 수 있도록하기 위해 1의 위치, n의 위치를 구해준다.

1의 위치와 n의 위치를 구하는 로직을 먼저 살펴보면

  int pos1 = -1;
  for (int i = 1; i <= n; i++){
    char result = query(i);
    if (result == '>'){
      if (pos1 != -1){
        query(pos1);
      }
    }else if (result == '<'){
      i--;
    }else{
      pos1 = i;
    }
  }
  int posn = -1;
  for (int i = 1; i <= n; i++){
    char result = query(i);
    if (result == '>'){
      i--;
    }else if (result == '<'){
      if (posn != -1){
        query(posn);
      }
    }else{
      posn = i;
    }
  }

다음과 같은데, 굉장히 간단하다.

먼저 pos1을 구하는 것은 result 가 더 크다고 나오는 경우, 다음 element 로 넘어가주면서 이전에 pos1 즉, pos[i] 보다 작은애가 있다면, 그 값으로 query 를 날려 값을 원상복구해준다.

그렇지 않은 경우는 같을 때까지 계속 진행할 수 있도록 i-- 를 해주고, 같아진 경우 pos1에다가 저장해준다.

posn 도 완전히 동일하다.

이제 위에서 설명했던 middle 값을 구한 뒤, 그 값에 맞춰서 위 아래로 나누어주는 분할정복을 진행할 것인데

처음에는 분할하지 않고 dnq 를 호출할 것이다. 주의할 점은 그 전에 x 값을 middle 값으로 맞춰주어야한다.

  int m = (1 + n) / 2;
  for (int i = 0; i < n - m; i++){
    query(pos1);
  }

위 로직이 해당 로직이다.

그리고 이제, 분할 정복 내부에서는 굉장히 간단하다.

middle 값보다 크거나 작은 것들을 새로운 배열에다가 넣어주고 middle 값을 원상복구 시킨다.

이제 이를 다 실행했다면 분할을 진행해줄 것인데 여기가 생각보다 어렵다.

  if (lm.size() != 0){
    int m2 = (l + m - 1) / 2;
    for (int i = 0; i < m - m2; i++){
      query(pos1);
    }
    dnq(l, m - 1, lm, res, pos1, posn);
    query(posn);
  }
  if (rm.size() != 0){
    int m2 = (r + m + 1) / 2;
    for (int i = 0; i < m2 - m; i++){
      query(posn);
    }
    dnq(m + 1, r, rm, res, pos1, posn);
  }

여기 이 부분인데, 서로 존재하는 경우에만 실행을 할 것이다.

또한, 처음에 진행했던 것처럼 각각 x 를 middle 값에 맞춰주고 분할을 진행하고 left 로 분할한 경우에만 x 값을 돌려준다.

근데 어떻게 posn 쿼리 한번으로 복구될까?

이는 크게 봤을 때 결국 r-l==1 일 때까지 진행이 되고, 그렇게 되면 query(posn) 한번이면 middle 값으로 복구가 되는 것이다.

right 는 이후에 진행되는 것이 없거나, 혹은 left 가 복구를 해주니까 이를 할필요가 없는 것이다.

물론 이게 너무 헷갈린다면

  if(lm.size()!=0){//down
    int m2=(l+m-1)/2;
    for(int i=0;i<m-m2;i++){
      query(pos1);
    }
    dnq(l,m-1,lm,res,pos1,posn);
    for(int i=0;i<m-m2;i++){
      query(posn);
    }
  }
  if(rm.size()!=0){//up
    int m2=(r+m+1)/2;
    for(int i=0;i<m2-m;i++){
      query(posn);
    }
    dnq(m+1,r,rm,res,pos1,posn);
    for(int i=0;i<m2-m;i++){
      query(pos1);
    }
  }

이렇게해도 문제는 없지만, 음.. query 를 더 날리니까 약간 쫄리긴한다.

쨌든 해당 문제는 이렇게 풀어낼 수 있었고, 많이 배운 문제였다.

아 그리고, 이 문제를 푸는데 시간을 너무 많이 쏟아서 약간 비효율적인 부분이 있엇던 것 같다.

진짜 다음부터는 아쉬워도 포기할 줄 알고, 빠르게 에디토리얼을 보고 학습하는 방향으로 진행해야겠다.

• 유의할 사항

endl 을 사용하지 않으면 인터렉션이 잘 동작하지 않는다.

다행인 것은 endl 이 codeforces 에서 크게 느리지 않은 것 같다.

• 시간 복잡도

O(Log N * N)

• 코드

char query(int idx){
  std::cout << "? " << idx << std::endl;
  char result;
  std::cin >> result;
  return result;
}

void dnq(int l, int r, std::vector<int> &pos, std::vector<int> &res, int pos1, int posn){
  int m = (l + r) / 2;
  std::vector<int> lm, rm;
  for (int i = 0; i < pos.size(); i++){
    char result = query(pos[i]);
    if (result == '>'){
      rm.push_back(pos[i]);
      query(pos1);
    }else if (result == '<'){
      lm.push_back(pos[i]);
      query(posn);
    }else{
      res[pos[i]] = m;
    }
  }
  if (lm.size() != 0){
    int m2 = (l + m - 1) / 2;
    for (int i = 0; i < m - m2; i++){
      query(pos1);
    }
    dnq(l, m - 1, lm, res, pos1, posn);
    query(posn);
  }
  if (rm.size() != 0){
    int m2 = (r + m + 1) / 2;
    for (int i = 0; i < m2 - m; i++){
      query(posn);
    }
    dnq(m + 1, r, rm, res, pos1, posn);
  }
}

void solve() {
  int n;
  std::cin >> n;
  int pos1 = -1;
  for (int i = 1; i <= n; i++){
    char result = query(i);
    if (result == '>'){
      if (pos1 != -1){
        query(pos1);
      }
    }else if (result == '<'){
      i--;
    }else{
      pos1 = i;
    }
  }
  int posn = -1;
  for (int i = 1; i <= n; i++){
    char result = query(i);
    if (result == '>'){
      i--;
    }else if (result == '<'){
      if (posn != -1){
        query(posn);
      }
    }else{
      posn = i;
    }
  }
  std::vector<int> res(n + 1);
  std::vector<int> pos(n);
  for (int i = 1; i <= n; i++){
    pos[i - 1] = i;
  }
  int m = (1 + n) / 2;
  for (int i = 0; i < n - m; i++){
    query(pos1);
  }
  dnq(1, n, pos, res, pos1, posn);
  std::cout << "! ";
  for (int i = 1; i <= n; i++){
    std::cout << res[i] << " ";
  }
  std::cout << std::endl;
}

int main(void){
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  std::cin >> T;
  while (T-- > 0) {
    solve();
  }
  return 0;
}