問題文
都市についての数列が与えられ、これらは都市の0時との時差である。
都市との時刻の差の最小値をとするとき、の最大値を求めよ。
※日本語が崩壊してる気がするので問題文を読むことをおすすめします。
解く前に考えていたこと
・読解に少し手間取った。要するに時差が3というのは、0時から考えると3時と21の二つがあるので、どちらを取るべきですか、みたいな問題。
・なので、すべての配置を試すことはできない。であることに着目する。
・の全探索を考えたけど間に合わない。(各時差に該当する都市があるかどうか)
・の中に同じ数がいくつ有るか(0か1か2)のみが重要であることがわかる。
(なぜなら、同一の時差を持つ都市が3つ以上ある場合、同じ時間に属する都市が少なくとも1つ存在する。これらの時差は常に0である。)
・配置の状態を12bitの3進数で表すような方針を立てた。要するにbit目が0,1,2ならの時差を持つ都市が0,1,2個ある。
2個の場合は時と時とすれば良い。1つのときは...…結局わかりません?
解説
・↑の方針でも十分に解けた。まず3進数である必要はない。なぜなら、同じ数が2つ以上ある場合、と時に一つずつ配置するのが必ず最適になる。
・つまり、一つの時間帯の状態は0または1である。さらに、時差の数字は決まっているので、も状態は必要なく個で十分。
・bit目が1ならに配置し、bit目が0なら番目に配置すれば良い。
・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; }