CODE FESTIVAL 2017 Final C - Time Gap (500)

C - Time Gap

概要

0からNまでの番号が付けられたN+1人について、番号1～Nまでの人の住む都市の時刻は、番号0の人（高橋君）の時刻と比べて差がDiある。
このとき、N+1人の時刻の差の最小値のうち、ありうる最大値を答えよ。

制約

1 ≦ N ≦ 50
0 ≦ Di ≦ 12

方針

番号iの人は高橋君の時刻よりDi時間前かDi時間後かのどちらかであり、各iに対して前か後ろかを全通り試すと答えが出る、がN≦50のときは2^50は10^15くらいなので間に合わない。

効率化を考える。まずは特殊ケース。
高橋君との時刻の差がDiの人が3人いると、必ず2人は同じ時刻になるため答えは0になる。
時刻0の人が高橋君の他にもう1人いる、またはDi = 12の人が2人いても答えは0になる（ちょうど1日違っても、時刻は同じ）。
また、N=1の時はD1自体が答えになる。

これ以外の場合は、Di = jなる人が1人もしくは2人の場合である。
2人の場合は高橋君の時刻を12とするとそれぞれの時刻が12-Di, 12+Diで確定する。
1人の場合は高橋君の前か後ろかをそれぞれ試す。ここまでくると、前か後ろかを試す候補は時刻の12個に収まるので間に合う。

解答

Submission #7053052 - CODE FESTIVAL 2017 Final (Parallel)

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<int> D(N);
	rep(i, N) cin >> D[i];
 
	if(N == 1){
		cout << D[0] << endl;
		return 0;
	}
 
	vector<int> c(13, 0);
	c[0]++;
	rep(i, N) c[D[i]]++;
 
	for(int i = 1; i < 12; i++){
		if(c[i] >= 3){
			cout << 0 << endl;
			return 0;
		}
	}
 
	if(c[12] >= 2 || c[0] >= 2){
		cout << 0 << endl;
		return 0;
	}
 
	vector<int> t;
	vector<int> d;
 
	if(c[0] == 1) t.push_back(12);
 
	for(int i = 1; i < 12; i++){
		if(c[i] == 2){
			t.push_back(12+i);
			t.push_back(12-i);
		}else if(c[i] == 1){
			d.push_back(i);
		}
	}
 
	if(c[12] == 1) t.push_back(24);
 
	int k = (int) d.size();
	int ans = 0;
 
	// cout << k << endl;
 
	for(int i = 0; i < (1 << k); i++){
		for(int j = 0; j < k; j++){
			if((i >> j) & 1){
				t.push_back(12-d[j]);
			}else{
				t.push_back(12+d[j]);
			}
		}
 
		sort(t.begin(), t.end());
		int s = t[1] - t[0];
		int l = (int) t.size();
		for(int j = 1; j < l; j++){
			s = min(s, t[j] - t[j-1]);
		}
 
		s = min(s, 24 - t[l-1] + t[0]);
		// cout << i << "," << s << endl;
		ans = max(ans, s);
 
		for(int j = 0; j < k; j++){
			if((i >> j) & 1){
				t.erase(lower_bound(t.begin(), t.end(), 12-d[j]));
			}else{
				t.erase(lower_bound(t.begin(), t.end(), 12+d[j]));
			}
		}
 
	}
 
	cout << ans << endl;
 
 
}