CODE FESTIVAL 2017 Final: C - Time Gap
solution
左右への振り分けを全列挙。$D_i$の上限を$L = 12$として$O(N + L2^L)$。
$D_i = 0, 12$のとき$D_i \equiv 24 - D_i$なので元の時刻は一意に定まり、それ以外が問題。 ふたつの都市の標準時が同じ時刻であると$s = 0$となるので、$D_i = k$となる$i$が$2$つ以上なら選択の余地はない。 ひとつのときだけが問題になるが、それぞれ左右のどちらに振るかを$2^{11}$通り全て試して間に合う。
implementation
#include <algorithm>
#include <array>
#include <climits>
#include <cmath>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
int main() {
// input
int n; scanf("%d", &n);
vector<int> d(n); repeat (i, n) scanf("%d", &d[i]);
// solve
array<int, 13> cnt = {};
cnt[0] += 1;
for (int d_i : d) cnt[d_i] += 1;
int max_s = -1;
repeat (pred, (1 << 11)) {
array<bool, 24> used = {};
int s = INT_MAX;
repeat (i, 13) if (cnt[i]) {
if (i == 0 or i == 12) {
used[i] = true;
if (cnt[i] >= 2) {
s = 0;
}
} else {
if (cnt[i] == 1) {
used[pred & (1 << (i - 1)) ? i : 24 - i] = true;
} else if (cnt[i] == 2) {
used[i] = used[24 - i] = true;
} else {
s = 0;
}
}
}
repeat (i, 24) if (used[i]) {
repeat (j, i) if (used[j]) {
setmin(s, min(abs(i - j), 24 - abs(i - j)));
}
}
setmax(max_s, s);
}
// output
printf("%d\n", max_s);
return 0;
}