메타인지 #0

Problem Solving을 할 때, 내 자신에 대해 느껴왔던 것 중 하나는
"답지"를 유난히 많이 본다는 것이다.모방은 창조의 어머니라지만, 모방만이 반복되면 결국 표절의 대가가 되어버리고 만다.

현재 나의 solved.ac 티어는 Diamond 2다. 내 실력보다는 훨씬 높은 티어라는 생각이 든다.
나의 본 실력을 파악하기 위해 한 가지 실험을 진행하려고 한다.

가설: 나는 Bronze 5부터 Diamond 2까지 모든 문제들을 풀 수 있는 실력을 가졌으며, 그 이상의 문제는 답지를 참고해야 한다.

실험은 다음과 같다.
기본 컨셉) Bronze5를 1, Ruby1을 30으로 놓고 이분탐색을 진행한다.

L: 내가 풀 수 있는 문제 티어의 최댓값
R: 내가 풀 수 없는 문제 티어의 최솟값
L, R의 초깃값은 각각 1, 31로 두고 $L+1 == R$이 되는 순간 탐색을 종료한다.

int solve(){
  int L=1,R=31;
  while(L+1<R){
      int m = L+(R-L)/2;
      if(chk(m)) L=m;
      else R=m;
  }
  return L;
}

chk 함수는 다음을 수행한다.

int x를 매개 변수로 받아
x 티어의 문제 3개를 결정한다.
문제를 결정하는 방법은 맞은 사람 수가 크면서, 아직 풀지 않은 문제로 한다. 단, 이미 풀이를 알고 있거나 너무 유사한 문제의 경우 다른 문제를 택한다.
3 문제 중 2문제 이상을 혼자의 힘으로 해결한 경우 true를, 그러지 못한다면 false를 return한다
기한은 CP가 아닌 PS인만큼 무제한이다.

첫번째 x는 (1+31)/2 = 16, Platinum 5가 된다.