BOJ 34609 Secret Lilies and Roses

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/34609
• 번역

문제

#

$1$번부터 $n$번까지 번호가 매겨진 $n$송이의 꽃이 왼쪽에서 오른쪽으로 일렬로 놓여 있다. 각 꽃은 백합(lily) 또는 장미(rose) 중 하나이다. $0$ 이상 $n$ 이하의 정수 $j$에 대해, $l_j$를 왼쪽 $j$개의 꽃 중 백합의 수, $r_j$를 오른쪽 $n - j$개의 꽃 중 장미의 수라 하자.

처음에는 꽃의 수 $n$만 주어진다. 꽃의 종류는 숨겨져 있다. 쿼리를 통해 꽃에 대한 정보를 얻을 수 있다. 한 번의 쿼리에서 다음 중 하나를 수행할 수 있다.

• 타입 쿼리(Type query): $1$ 이상 $n$ 이하의 정수 $i$를 지정한다. 그러면 꽃 $i$의 종류를 알 수 있다.
• 곱 쿼리(Multiply query): $0$ 이상 $n$ 이하의 정수 $j$를 지정한다. 그러면 $l_j \times r_j$의 값을 알 수 있다.

$l_k = r_k$를 만족하는 $0$ 이상 $n$ 이하의 정수 $k$를 제한된 횟수의 쿼리로 찾는 것이 목표이다. 꽃의 배치에 대해 그러한 정수가 적어도 하나 존재함이 보장된다. 각 꽃의 종류를 모두 알아낼 필요는 없다.

인터랙션

#

입력의 첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 100$)가 주어진다. 이후 $t$개의 테스트 케이스가 다음과 같이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$ ($1 \le n \le 100$)이 주어진다. 이를 읽은 후 쿼리를 시작할 수 있다. 각 쿼리에 대해 다음 중 하나를 출력한다.

• type $i$ : $1 \le i \le n$인 정수 $i$를 지정하는 타입 쿼리를 수행한다. 응답으로 꽃 $i$의 종류를 나타내는 lily 또는 rose 문자열이 입력된다.
• multi $j$ : $0 \le j \le n$인 정수 $j$를 지정하는 곱 쿼리를 수행한다. 응답으로 $l_j \times r_j$의 정수값이 입력된다.

각 테스트 케이스당 최대 10번의 쿼리를 사용할 수 있다. 즉, 타입 쿼리와 곱 쿼리를 합산한 총 횟수가 10을 초과해서는 안 된다. 10번을 초과하면 “오답(Wrong Answer)“으로 처리된다.

$l_k = r_k$를 만족하는 정수 $k$를 찾으면 answer $k$ ($0 \le k \le n$) 형식으로 출력한다. 정답 출력은 쿼리 횟수에 포함되지 않는다.

정답을 출력한 후 다음 테스트 케이스를 처리한다. 모든 테스트 케이스를 처리하면 인터랙션이 종료되며 프로그램을 종료해야 한다.

🧐 관찰 및 접근

#

• 아 인터랙티브..
• 일단 $N$이 $100$이니까, 7번정도의 이분탐색맛 쿼리랑, 2번정도의 근처 계산 쿼리..? 같은 느낌으로 진행될 것 같은데…
• 일단 $l, r$에는 단조성이 있다. 아무래도. $j$가 커짐에 따라 $l$은 단조증가, $j$는 단조감소한다.
• 두 수열 $l, r$에 대해, 둘중에 한개만 바뀐다. 이것도 아무래도.
  • 그렇다면 곱 쿼리 $k, k+1$ 두개를 비교했을때 값이 커졌다면 $l$이 증가한것이고, 작아졌다면 $r$이 감소한 것일 것이다.
  • 그렇다고 그부분이 최대치는 아니네.. 힝스. 근데 이걸 잘 써먹어야할 것 같은게, $l_j = x$라면 $j$까지에 장미는 $j - x$개 있다는거니까, 이런 정보까지도 잘 활용해야 쿼리를 맞출 수 있을 것 같다.
  • $k, k+1$ 두개를 비교했을때 값이 변하는걸로 $l_k, r_k$도 특정 가능한 것 같다. 만약 $x$만큼 증가했다는건 $F_j$ (Flower이라고 치자)가 lily라는거니까 $r_k = r_{k+1} = x$라는 거 같고, 감소했다는건 $l_k = l_{k+1} = x$인 것 같고.
  • 따라서 두번의 쿼리로 $l_k, r_k$를 알 수 있으니 하면.. 이라기엔 쿼리 10번은 좀 부족하다. $2^6 < 100$이므로 14번은 필요할 것 같은데.
  • 이분탐색의 범위를 조금 더 잘 좁힐 수 있나? 예를들어 $N = 100$이고, $50, 51$번째를 검사했는데 $l_{50} = 40, r_{50} = 10$이었다고 하자. 어차피 오른쪽으로 갈 때 $l$도 최대 한개씩 증가하고, $r$도 최대 한개씩 감소하므로 저 오른쪽에서는 답이 있을 수 없다. 왼쪽으로 갈 때도 한개씩 움직이는 특징에 따라 $21$번째 이후에는 답이 있을 수 없다.
    • …그전에 딱 그부분이 답이어야하는거 아닌가? $l, r$ 둘중에 하나는 무조건 움직여야하는데.
• 아, 이슈인 상황이 있다. 다 장미거나 그러면 곱 결과가 둘다 0이 나와서 쬠 곤란하다… 그전에 위에 내가 관찰한대로라면 곱 결과가 0이 아닌곳만 잘 찾아보면 될텐데.
  • $RR...RR$, $LL...LL$, $RR...LL$ 이런 경우들에 무조건 다 0인데? 이걸 어떻게 검사하지?
    • 아, 이해했다. 이거때문에 type 쿼리가 필요한거구나.
    • 맨 왼쪽이 $L$이거나, 맨 오른쪽이 $R$이기만 하면 어떻게든 저 곱쿼리를 이용해서 한방에 계산이 가능한디.
  • $RRRRRLLRRLLLLLL$ 머 이런느낌이면 어카지?
    • $0, 0, ..., 2, 4, 2, 0, ... 0$ 처럼 나오는데… 저 값이 존재하는 부분이 어디있을지 모른다는게 문제란 말이지.
  • 이분탐색으로 어떻게든 $R \rightarrow L$로 바뀌는 타이밍을 찾았다고 하자. 그때의 인덱스를 $j$라고 하자.
  • 그렇다면 $l_j$는 $1$ 이상이고, $r_{j-2}$는 $1$ 이상이다.
    • $M_j = 0$ (곱이니까 대충 $M$이라고 해보자) 이라면, $r_j = 0$인 것이다.
    • $M_{j-2} = 0$이라면, $l_{j-2} = 0$인 것이다.
    • $F_{j-1} = R, F_j = L$이다.
  • 케이스를 네개로 나눠보자. 찾은 $R, L$을 기점으로.
    • $RRR...R(RL)L...LLL$
      • $M_{j-2} = M_j = 0$
      • 그렇다면 $ans = j-1$
    • $RRLRRR...R(RL)L....LLL$
      • $M_{j-2} \neq 0, M_j = 0$
      • $M_{j-2} = l_{j-2}$
      • 그렇다면 $ans = (j-1) - M_{j-2}$
    • $RRRR...R(RL)L....LLRL$
      • $M_{j-2} = 0, M_j \neq 0$
      • $M_j = r_j$
      • 그렇다면 $ans =(j-1) + M_j$
    • $RRLRRR...R(RL)L....LLRL$
      • $M_{j-2} \neq 0, M_j \neq 0$
      • $M_{j-2} = l_{j-2} \times r_{j-2}$
      • $M_j = l_j \times r_j$
      • $l_j = l_{j-2} + 1$
      • $r_j = r_{j-2} - 1$
      • 대입하면 $M_j = M_{j-2} - l_{j-2} + r_{j-2} - 1$
      • 우리가 얻고싶은 답은 $((j-2) - l_{j-2}) + r_{j-2}$ 로 계산할 수 있으니
      • $ans = (j-1) + (M_j - M_{j-2})$ 인거같기도?
    • 엥? 4개가 일반화가 되는 것 같다.
  • 하 이게 앞에 2개 + 이분탐색 7개 + 마지막에 2개 해서 11개 쿼리네.. 한개를 줄일 수 있을까?
  • 앞에 두개를, 이분탐색만 이용하는걸로 생각해서 잡아버려도 된다!! 그렇게하면 9개로 된다

💻 풀이

#

• 코드 (C++):

void solve(){
    int N; cin >> N;

    int ng = 0, ok = N+1; // ng: R, ok: L이라고 믿자
    while(ok - ng > 1){
        int mid = (ok + ng) >> 1;
        cout << "type " << mid << endl;
        string ret; cin >> ret;
        if(ret == "rose") ng = mid;
        else ok = mid;
    }
    if(ok == N+1){ // 마지막이 rose
        cout << "multi " << N-1 << endl;
        int Lily; cin >> Lily;
        cout << "answer " << N-Lily << endl;
        return;
    }
    if(ok == 1){ // 처음이 Lily
        cout << "multi " << 1 << endl;
        int Rose; cin >> Rose;
        cout << "answer " << Rose << endl;
        return;
    }

    int ret1, ret2;
    cout << "multi " << ok << endl;
    cin >> ret1;
    cout << "multi " << ok-2 << endl;
    cin >> ret2;
    cout << "answer " << (ok-1) + ret1 - ret2 << endl;
}