solved.ac 2022 난이도 산정

solved.ac는 프로그래밍 문제 해결 사이트의 문제들에 난이도를 붙이는 커뮤니티 프로젝트다. 기존에는 이 사이트의 문제들에 난이도 표기가 없어서, 다양한 문제를 풀어 보고 싶어도 난이도를 가늠하기 어려웠다. 그래서 solved.ac가 만들어졌다. solved.ac가 생긴 이후 $1\,900$명 이상의 기여자가 난이도 의견을 공유해 주었고, 지금은 약 $16\,000$문제에 난이도가 붙었다.

어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 정한다. 기존에는 의견이 제출된 시점과 상관없이 단순 절사평균으로 난이도를 정했다. 그러나 프로그래밍 문제 해결은 빠르게 변하는 분야이므로, solved.ac는 새로운 의견에 더 큰 무게를 두도록 난이도 산정 공식을 바꾸기로 했다. 어떤 문제에 $N$개의 난이도 의견이 제출되었을 때 문제의 난이도는 다음 방법으로 정한다.

• 난이도 의견이 하나도 없으면 문제의 난이도는 $0$이다.
• 난이도 의견이 하나 이상 있으면, 의견을 제출한 시각 순으로 정렬한 뒤 각 의견의 가중치 $p_i$를 다음 수식으로 정한다. $p_i=\max\left(0.5^{(t_N-t_i)/365\text{일}},0.9^{N-i}\right)$
  • $t_i$는 $i$번째 난이도 의견이 제출된 시각이다. 시간 순으로 정렬했으므로 $t_1\le t_2\le\cdots\le t_N$이며, $t_N$은 가장 최근에 제출된 의견의 시각이다.
• 문제의 난이도 $X$는 $p_i$를 가중치로 하는 가중평균을 소수점 아래 첫째 자리에서 반올림한 정수다. $X=\frac{p_1l_1+p_2l_2+\cdots+p_Nl_N}{p_1+p_2+\cdots+p_N}=\frac{\sum_{i=1}^{N}p_il_i}{\sum_{i=1}^{N}p_i}$
  • $l_i$는 $i$번째 의견에 담긴 난이도를 $1$ 이상 $30$ 이하의 정수로 바꾼 값이다. $1$은 가장 낮은 난이도인 브론즈 $5$를, $30$은 가장 높은 난이도인 루비 $1$을 가리킨다.

첫 번째 줄에 난이도 의견의 개수 $N$이 주어진다. $(0\le N\le 1\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄마다 난이도 의견이 하나씩 주어진다. $i$번째 줄에는 $t_i$와 $l_i$가 공백으로 구분되어 주어진다.

• $t_i$는 난이도 의견이 남겨진 시각으로, 연도/월/일 시:분:초 형식이다.

  • 연도는 4자리이고, 월/일/시/분/초는 각각 2자리의 문자열이다. 필요한 경우 자릿수를 맞추기 위해 숫자 $0$이 앞에 붙을 수 있다. 특히 $2020$년은 윤년이므로, $2020$년의 $2$월 마지막 날은 $29$일이다.
  • 시간은 24시간 형식이다.
  • 주어지는 시각은 2019년 6월 6일 00:00:00부터 2022년 7월 1일 23:59:59까지이며, $t_1\le t_2\le\cdots\le t_N$이 되도록 정렬되어 있다.

• $l_i$는 난이도 의견의 값을 의미하는 정수이다. $(1\le l_i\le 30)$

주어진 난이도 의견들을 바탕으로 계산한 문제의 난이도를 출력한다. 출력한 정수가 채점 프로그램이 계산한 반올림하기 전의 가중평균과 $0.5+10^{-5}=0.50001$ 이하의 차이를 보이면 정답으로 인정한다.

첫 번째 경우에서 첫 번째 의견은 마지막 의견보다 약 834일 6시간, 즉 약 $2.286$년 전의 의견이다. 따라서 가중평균은 다음과 같다. $X\approx\frac{\max\left(0.5^{2.286},0.9^1\right)\times 24+\max\left(0.5^0,0.9^0\right)\times 18}{\max\left(0.5^{2.286},0.9^1\right)+\max\left(0.5^0,0.9^0\right)}=\frac{0.9\times 24+1\times 18}{0.9+1}\approx 20.842$ 이를 반올림한 $21$이 난이도로 결정된다.