[IOI 2017] The Big Prize

https://www.acmicpc.net/problem/20079

 

ioi임 + 인터랙티브임 요소 때문에 올려치기가 좀 있는 것 같다.

 

• 단순히 계산해보면 $v\leq 5$이다.
• 가장 별로인 종류가 거의 대부분을 차지한다.
• 가장 별로인 종류만 무시하면서 분할정복 느낌으로 탐색을 진행한다.
• (가장 별로인 종류가 아닌 다른 종류들) × (log n)에 해결된다.

 

뭔가 잘못짠 부분이라던가.. 좀 있어야 할 것 같은데 데이터가 약한건가 뭔가.. 대충 짰는데 그냥 잘 돌더니 100점을 받았다.

뭔가 철학도 재미도 없는 문제인 것 같다.

 

• 내가 구현을 잘 해서 쉬웠던 걸 수도 있을 것 같다.
• 탐색 구간이 들어오면, $m$을 잡고서, $m$이 가장 별로인 애가 아니면, 전부 답의 후보로 하나하나 확인해도 되므로 $m_1$ ~ $m_2$로 나이브하게 넓힌다.
• 그 뒤 $[a, m_1-1]$과 $[m_2+1, b]$로 탐색을 날려주는데, 항상 탐색 구간을 감싸는 바깥 인덱스들은 접근해도 된다. (나이브하게 넓혀버리면서, 구간을 가장 별로인 애들이 끊기는 지점으로 쪼갰기 때문에)

 

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(random_device{}());
map<int, vector<int>> C;
map<int, set<int>> S;
int n, mx;

vector<int> ASK(int x) {
	if(x==-1) return {0, n};
	if(x==n) return {n, 0};
	if(!C.contains(x)) C[x]=ask(x), S[C[x][0]+C[x][1]].insert(x);
	return C[x];
}

void search(int a, int b) {
	if(a>b) return;
	
	int m1=(a+b)>>1, m2=m1;
	auto v=ASK(m1);
	
	while(a<=m1 && ASK(m1)[0]+ASK(m1)[1] < mx) m1--;
	while(m2<=b && ASK(m2)[0]+ASK(m2)[1] < mx) m2++;
	
	if(a<m1 && ASK(a-1)[0]<ASK(m1)[0]) search(a, m1-1);
	if(m2<b && ASK(m2)[1]>ASK(b+1)[1]) search(m2+1, b);
}

int find_best(int _n) {
	n = _n;
	for(int i=0; i<50; ++i) {
		auto v=ASK(uniform_int_distribution<int>(0,n-1)(rng));
		mx = max(mx, v[0]+v[1]);
	}
	search(0, n-1);
	return *(S.begin()->second.begin());
}