Google Code Jam 2018 Round1C : B. Lollipop Shop

あまり考えず通ってしまった。
https://codejam.withgoogle.com/2018/challenges/0000000000007765/dashboard/000000000003e068

問題

0～(N-1)のN通りの飴が１つずつある。
ここにN人の客が来る。
客は好みの飴の番号を列挙するので、売れる飴があればうち１個を売ることにする。
各客がそれぞれの飴を好む確率は明には開示されないが一定である。

最適な売り方の9割を達成する売り方を答えよ。

解法

まだ売ってない飴のうち、これまで客が好みだと言った回数が最小のものを売ればよい。
そのような飴は後の客が再び好みという確率が低いためである。

int num[202];
int did[202];
int pat[202];
int N;

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	ZERO(num);
	ZERO(did);
	cin>>N;
	FOR(i,N) {
		int M;
		cin>>M;
		int id=-1,best=10101;
		FOR(j,M) {
			cin>>pat[j];
			num[pat[j]]++;
			if(did[pat[j]]==0 && num[pat[j]]<best) {
				id=pat[j];
				best=num[pat[j]];
			}
		}
		
		if(id==-1) {
			cout<<-1<<endl;
		}
		else {
			cout<<id<<endl;
			did[id]=1;
		}
	}
	
}

まとめ

解法自体は単純だけど、ポイント高いのはinteractiveだからかな？