Time Gap [CODE FESTIVAL 2017 Final C]

https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_c

解法

https://cf17-final-open.contest.atcoder.jp/submissions/1812785

公式解説の図が最強すぎる
円の構造のやつは今後これで考えることにする。
例外的に時差が0と12の場合は1つに確定するが、他はどの人も時間の候補は2つとなる。
全ての候補者について、どちらになるかを全探索するとO(2^50)となってダメ。
全探索はするが、もう少し効率良くやることにする。
　
「cnt[i] := 時間iの人の人数」とする。
　
まず、例外から考えよう。

• 1 ≦ cnt[0]
  • 高橋君とかぶるので、答えは0
• cnt[12] == 1
  • その時間に人がいるのは間違いない。
• 1 < cnt[12]
  • その中の二人がかぶるので、答えは0

　
他のある時間t([1,11])を考える。
cnt[t] == 0ならば人はいない。
cnt[t] == 1ならば時間tか時間(24-t)のどちらかに人がいる。これは分からないので全探索で考える。
cnt[t] == 2ならば時間tか時間(24-t)のどちらにも人がいる。ここは確定。
2 ≦ cnt[t]ならば、どうやっても2人以上いる時間が出来てしまうので、答えは0
　
あとは、cnt[t]==1である部分だけを全探索して、距離の最小をチェックする。
全探索する可能性があるtは[1,11]の11通りで全部でO(2^11)、最小のチェックを愚直にやってO(N^2)。
全部でO(2^11*50^2)なので間に合う。

int N, D[50];
//---------------------------------------------------------------------------------------------------
int cnt[13], vis[24];
int count() {
    int mi = 101010;
    rep(i, 0, 24) rep(j, 0, 24) if (vis[i] and vis[j] and i != j) {
        int d1 = abs(i - j);
        int d2 = 24 - d1;
        int d = min(d1, d2);
        mi = min(mi, d);
    }
    return mi;
}
//---------------------------------------------------------------------------------------------------
int solve() {
    rep(i, 0, N) cnt[D[i]]++;
 
    if (cnt[0]) return 0;
    vis[0] = 1;
 
    vector<int> v;
    rep(i, 1, 12) {
        if (cnt[i] == 1) v.push_back(i);
        else if (cnt[i] == 2) vis[i] = vis[24 - i] = 1;
        else if(2 < cnt[i]) return 0;
    }
    if (cnt[12] == 1) vis[12] = 1;
    else if (2 <= cnt[12]) return 0;
 
    int M = v.size();
    if (M == 0) {
        return count();
    }
 
    int ans = 0;
    rep(msk, 0, 1<<M) {
        rep(i, 0, M) {
            if (msk & (1 << i)) vis[v[i]] = 1, vis[24 - v[i]] = 0;
            else vis[v[i]] = 0, vis[24 - v[i]] = 1;
        }
        ans = max(ans, count());
        
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> D[i];
    cout << solve() << endl;
}