予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

C - Time Gap

問題文

 N都市についての数列 Dが与えられ、これらは都市T_{0}の0時との時差である。
都市T_iT_{j}の時刻の差の最小値をsとするとき、sの最大値を求めよ。
※日本語が崩壊してる気がするので問題文を読むことをおすすめします。

atcoder.jp

解く前に考えていたこと

・読解に少し手間取った。要するに時差が3というのは、0時から考えると3時と21の二つがあるので、どちらを取るべきですか、みたいな問題。

 N\leq 50なので、すべての配置を試すことはできない。D_{i} \leq 12であることに着目する。
2^{23}の全探索を考えたけど間に合わない。(各時差に該当する都市があるかどうか)
Dの中に同じ数がいくつ有るか(0か1か2)のみが重要であることがわかる。
(なぜなら、同一の時差を持つ都市が3つ以上ある場合、同じ時間に属する都市が少なくとも1つ存在する。これらの時差は常に0である。)

・配置の状態を12bitの3進数で表すような方針を立てた。要するにibit目が0,1,2ならiの時差を持つ都市が0,1,2個ある。
2個の場合は i時と i+12時とすれば良い。1つのときは...…結局わかりません?

解説

・↑の方針でも十分に解けた。まず3進数である必要はない。なぜなら、同じ数が2つ以上ある場合、i時i+12時に一つずつ配置するのが必ず最適になる。
・つまり、一つの時間帯の状態は0または1である。さらに、時差 jの数字は決まっているので、2^{23}も状態は必要なく2^{12}個で十分。
ibit目が1ならiに配置し、ibit目が0なら i + 12番目に配置すれば良い。
・0時は高橋くんが使うらしいので初期値1。また,時差12の場合の配置は一通りに決まる。

#include<bits/stdc++.h>
using namespace std;
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
signed main(){
    int N; cin >> N;
    vector<int>v(N);
    for(auto & e : v) cin >> e;
    array<short,13> cnt = {0};
    cnt[0]++;
    for(auto  e : v)cnt[e]++;
    for(auto  e : cnt) if(e >= 3) return puts("0") * 0;
    if(cnt[0] >= 2 or cnt[12] >= 2) return puts("0")* 0;
    int ans = -INF;
    
    for(int bit = 0; bit < (1LL << 12); ++bit){
        vector<int>pos(25,0LL);
        pos[0] = cnt[0];
        pos[12] = cnt[12];
        int tans = INF;
        for(int i = 1; i <= 12; ++i){
            if(cnt[i] == 0) continue;
            if(cnt[i] == 2) pos[i] = pos[24 - i] = 1;
            if(cnt[i] == 1){
                ((bit & (1LL << (i - 1))) >= 1 ? pos[i] : pos[24 - i]) = 1;
            }
        }
        for(int i = 0; i < pos.size(); ++i){
            for(int j = 0; j < pos.size(); ++j){
                if(i != j and pos[i] == 1 and pos[j] == 1)
                    cmin(tans, min(abs(i-j),24 - abs(i-j)));
            }
        }
        if(tans == INF)continue;
        cmax(ans, tans);
    }
    cout << ans << endl;
}