Qiitaにはいくつか記事を書いていますが、はてなでは1年以上ぶりです。
普段はPythonばかり書いています。最近はtheanoが気に入っています。あとclickと。
かよちん生誕祭に開催されたFacebook Hacker CupのR1でなぜか全完できたので、たまには記事を書こうという気になりました。
Round 1 : 1/17 3am JST〜1/18 3am JST（24時間）
Facebook Hacker Cup 2016 Round 1
全部で4問 (15,20,25,40)。30点以上獲得すれば通過。
D以外だと2問取らないと30点にならないように出来てる。これはハードかも。
D. Boomerang Tournament (40 points)
夜中に起きたら始まってたので、とりあえず問題を4つとも読んでからお風呂でリラックス。
最後に読んだDを考え始めてて、途中まで実装して、あとはビットマスクでごにょごにょすれば行ける！とか思いながら寝落ち。
２人ずつ (nC2)、４人ずつ (nC4)、のグループで、（その中で組まれた任意のトーナメント対戦で）勝つ可能性が１つでもある者・負ける可能性が１つもない者をそれぞれ決勝まで（メモ化なりDPなりで）bitで持ち上がれば計算量は減らせそう。（bitDPか）
起き上がって実装を仕上げて、大きなテストケースでも時間に余裕があるのを確認して、brute forceな（N=8までしか行けない）コードの解と照合して、提出。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define tr(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
int N, K, P;
vector<vector<int> > W;
vector<int> top, bottom;
vector<int> mm_top, mm_bottom;
vector<vector<set<int> > > pset;
vector<int> winnable, losable;
void sub(int k) {
tr(it, pset[K][1<<k]) {
int pat = *it;
mm_top[pat] = 0;
mm_bottom[pat] = pat;
if (k == 0) {
mm_top[pat] = mm_bottom[pat] = pat;
continue;
}
tr(it2, pset[K][1<<(k-1)]) {
int mask0 = *it2;
if ((pat & mask0) != mask0) continue;
int mask1 = pat - mask0;
if (mask0 > mask1) continue;
int t0 = mm_top[mask0], t1 = mm_top[mask1];
int t0_ = 0, t1_ = 0;
int b0 = mm_bottom[mask0], b1 = mm_bottom[mask1]; // ここまで負けられない
int b0_ = b0, b1_ = b1;
for (int i=0,m=1; i<N; ++i, m<<=1) {
if (m & t0) {
if (winnable[i] & t1) {
t0_ |= m;
top[i] = k;
}
} else if (m & t1) {
if (winnable[i] & t0) {
t1_ |= m;
top[i] = k;
}
}
if (m & b0) {
if (losable[i] & b1) {
b0_ &= ~m;
bottom[i] = min(bottom[i], k);
}
} else if (m & b1) {
if (losable[i] & b0) {
b1_ &= ~m;
bottom[i] = min(bottom[i], k);
}
}
}
int t = t0_ | t1_;
int b = b0_ | b1_;
mm_top[pat] |= t;
mm_bottom[pat] &= b;
}
}
}
int main() {
map<int,int> _log2;
_log2[1] = 0;
_log2[2] = 1;
_log2[4] = 2;
_log2[8] = 3;
_log2[16] = 4;
int _rank[] = { 1, 2, 3, 5, 9 };
int _2k[] = { 1, 2, 4, 8, 16 }; // 2^k
int _22k[] = { 1, 4, 16, 256, 65536 }; // 2^(2^k)
pset.resize(5);
for (int k=0; k<=4; ++k) {
pset[k].resize(1+_2k[k]);
}
for (int p=1; p<65536; ++p) {
int pc = __builtin_popcount(p);
if (__builtin_popcount(pc) != 1) continue;
switch (pc) {
case 1:
if (p < _22k[0])
pset[0][pc].insert(p);
// fall thru
case 2:
if (p < _22k[1])
pset[1][pc].insert(p);
// fall thru
case 4:
if (p < _22k[2])
pset[2][pc].insert(p);
// fall thru
case 8:
if (p < _22k[3])
pset[3][pc].insert(p);
// fall thru
case 16:
if (p < _22k[4])
pset[4][pc].insert(p);
break;
}
}
int _T; cin >> _T;
rep(_t,_T){
cin >> N;
K = _log2[N];
W.assign(N, vector<int>(N));
rep(i,N) rep(j,N) cin >> W[i][j];
P = 1 << N;
mm_top.assign(P, -1);
mm_bottom.assign(P, -1);
top.assign(N, 0);
bottom.assign(N, K+1);
winnable.resize(N);
losable.resize(N);
rep(i,N) {
int x = 0;
for (int j=0,m=1; j<N; ++j,m<<=1) {
if (W[i][j]) x |= m;
}
int y = (1 << N) - 1 - x;
winnable[i] = x;
losable[i] = y;
}
for (int k=0; k<=K; ++k) sub(k);
printf("Case #%d: \n", 1+_t);
rep(i, N) {
int t = _rank[K - top[i]];
int b = _rank[K - (bottom[i] - 1)];
printf("%d %d\n", t, b);
}
}
}（おまけ）検算に使った乱暴なシミュレーション。next_permutation() で回してるのでN=8が限界。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define found(s,e) ((s).find(e)!=(s).end())
int main(){
map<int,int> _log2;
_log2[1] = 0;
_log2[2] = 1;
_log2[4] = 2;
_log2[8] = 3;
_log2[16] = 4;
int _rank[] = { 1, 2, 3, 5, 9 };
int N, K;
vector<vector<int> > W;
int _T; cin>>_T;
rep(_t,_T){
cin >> N;
K = _log2[N];
W.assign(N, vector<int>(N));
rep(i,N) rep(j,N) cin >> W[i][j];
vector<int> iota(N);
rep(i,N) iota[i] = i;
vector<int> lo(N, K+1), hi(N, -1);
do {
int skip = N/2;
vector<int> z(all(iota)), r(N, 0);
for (int l=0,skip=1; skip<N; ++l,skip*=2) {
for (int i=0; i<N; i+=skip*2) {
int a = z[i], b = z[i+skip];
if (!W[a][b]) z[i] = b;
++r[ z[i] ];
}
}
rep(i,N) {
lo[i] = min(lo[i], r[i]);
hi[i] = max(hi[i], r[i]);
}
} while (next_permutation(all(iota)));
printf("Case #%d: \n", 1+_t);
rep(i,N) {
printf("%d %d\n", _rank[K - hi[i]], _rank[K - lo[i]]);
}
}
}
C. Yachtzee (25 points)
続いてC。
積分（というか三角形の面積を足しあわせていったもの）して底辺で割ればいいだけだよね。
これは一番簡単な気がする。
a〜bの積分は、(0〜b) - (0〜a) にした方が分かりやすい。
あとは精度と、時間が間に合うかというところだけ。
面積計算は、2倍にして整数 (long long) で計算すればいいかなと。最後の割り算だけdoubleで。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define rep(var,n) for(int var=0;var<(n);var++)
int N;
vector<ll> C, Cacc;
vector<ll> S2; // S*2
ll W;
ll f(ll x) {
ll q = x / W, r = x % W;
vector<ll>::iterator it = upper_bound(all(Cacc), r);
int ix = (it - Cacc.begin()) - 1;
ll d = r - Cacc[ix];
ll s = S2[ix] + d*d;
return S2[N] * q + s;
}
int main(){
int _T; cin>>_T;
rep(_t,_T){
cin >> N;
ll a, b; cin >> a >> b;
C.resize(N); Cacc.resize(N+1); S2.resize(N+1);
Cacc[0] = S2[0] = 0LL;
rep(i,N) {
ll c; cin >> c;
C[i] = c;
Cacc[i+1] = Cacc[i] + c;
S2[i+1] = S2[i] + c*c;
}
W = Cacc[N];
ll aq = a / W, ar = a % W;
ll bq = b / W, br = b % W;
ll ofs = W * aq;
ll s2 = f(b-ofs) - f(a-ofs); // f(b) - f(a)
double ans = 0.5*s2 / (b-a);
printf("Case #%d: %.9f\n", 1+_t, ans);
}
}
B. Laundro, Matt (20 points)
Bを考えてて、洗濯フェーズの所要時間の最小化は二分探索でできるなあと思ったんだけど
その後の乾燥フェーズに投げるにあたって、洗濯フェーズだけで所要時間最小化したパターンが
乾燥も含めて最短になるのか自信がなくて、後回し（というか寝落ち）。
最小所要時間から、個々の洗濯機の最大稼働回数を求めて、priority queueに次に洗濯機が空く時刻を投入して行って、L個の洗濯物の１つ１つができるだけ早いタイミングで終わるパターンを得て*1キューに入れ、
乾燥フェーズのシミュレーション。こちらもpriority queueにM台*2の乾燥機の空くタイミングを投入。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define all(c) (c).begin(),(c).end()
#define rep(var,n) for(int var=0;var<(n);var++)
ll L, N, M, D;
vector<ll> W;
bool p(ll a) {
ll qs = 0;
rep(i, N) qs += a / W[i];
return qs >= L;
}
int main(){
int _T; cin>>_T;
rep(_t,_T){
cin >> L >> N >> M >> D;
M = min(M, L); // 乾燥機は1e9個も要らんだろ
W.resize(N); rep(i,N) cin >> W[i];
sort(all(W));
// 洗濯側の最短所要時間 a を binary search で
ll lo = 0, hi = W[N-1]*L, a = hi;
// assert p(lo) == false
// assert p(hi) == true
do {
ll mi = (lo + hi) / 2; // 1e15 < 2^50 < LONG_LONG_MAX
if (p(mi)) {
a = hi = mi;
} else {
lo = mi;
}
} while (hi > lo+1);
// 所要時間を a として、なるはやで仕上がる順に洗濯機に投入したい
// q は洗濯仕上がり時刻のリスト
priority_queue<ll, vector<ll>, greater<ll> > pq;
rep(i,N) {
ll wi = W[i];
for (ll w=wi; w<=a; w+=wi) {
pq.push(w);
}
}
vector<ll> q;
rep(i, L) {
q.push_back( pq.top() ); pq.pop();
}
while (!pq.empty()) pq.pop();
// 乾燥機が使える時刻。普通のqueueでいいのかも
priority_queue<ll, vector<ll>, greater<ll> > pq2;
rep(i, M) pq2.push(0);
ll ans;
rep(i, L) {
ll t = q[i];
ll d = pq2.top(); pq2.pop(); // first available dryer
ll next = max(d, t);
pq2.push(next + D);
if (i == L-1) ans = next + D;
}
while (!pq2.empty()) pq2.pop();
printf("Case #%d: %lld\n", 1+_t, ans);
}
}
A. Coding Contest Creation (15 points)
（寝落ち後に）Bを後回しにしてAから。
greedyに取っていけば行けるような気もするんだけど、ミスなく書ける気がしないんだよな…
ちょっと出かけようと思って、歩いてたら頭の中でDPの表が書けたので、そのまま実装して提出。
問目が4つ組の何番目かの表を作って編集距離みたいにDP。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rep(var,n) for(int var=0;var<(n);var++)
inline int min4(int a, int b, int c, int d) { return min(min(a,b),min(c,d)); }
int main(){
int _T; cin>>_T;
rep(_t,_T){
int N; cin >> N; // 1-100000
vector<int> D(N); // 1-100
rep(i,N) cin >> D[i];
vector<vector<int> > dp(N, vector<int>(4)); // dp[i][n], n=0,1,2,3は4つ組の何番目か, 値は編集距離
dp[0][0] = 0; dp[0][1] = 1; dp[0][2] = 2; dp[0][3] = 3;
// D[0]=1 だとその前にはおけないんだけど、そのグループの後に置くのと結局同じことなので
for (int i=1; i<N; ++i) {
int last = D[i-1], curr = D[i], diff = curr - last;
if (0 < diff && diff <= 10) {
dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0); // restart
dp[i][1] = min4(dp[i-1][0] , dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
dp[i][2] = min4(dp[i-1][0] +1 , dp[i-1][1] , dp[i-1][2]+1+2, dp[i-1][3]+0+2);
dp[i][3] = min4(dp[i-1][0] +2 , dp[i-1][1] +1 , dp[i-1][2] , dp[i-1][3]+0+3);
}
else if (10 < diff && diff <= 20) {
// 1 gap
dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0); // restart
dp[i][1] = min4(dp[i-1][0]+3+1, dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
dp[i][2] = min4(dp[i-1][0] +1 , dp[i-1][1]+2+2, dp[i-1][2]+1+2, dp[i-1][3]+0+2);
dp[i][3] = min4(dp[i-1][0] +2 , dp[i-1][1] +1 , dp[i-1][2]+1+3, dp[i-1][3]+0+3);
}
else if (20 < diff && diff <= 30) {
// 2 gaps
dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0); // restart
dp[i][1] = min4(dp[i-1][0]+3+1, dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
dp[i][2] = min4(dp[i-1][0]+3+2, dp[i-1][1]+2+2, dp[i-1][2]+1+2, dp[i-1][3]+0+2);
dp[i][3] = min4(dp[i-1][0] +2, dp[i-1][1]+2+3, dp[i-1][2]+1+3, dp[i-1][3]+0+3);
}
else {
// 前と切って（前を終わらせてから）restart
dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0);
dp[i][1] = min4(dp[i-1][0]+3+1, dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
dp[i][2] = min4(dp[i-1][0]+3+2, dp[i-1][1]+2+2, dp[i-1][2]+1+2, dp[i-1][3]+0+2);
dp[i][3] = min4(dp[i-1][0]+3+3, dp[i-1][1]+2+3, dp[i-1][2]+1+3, dp[i-1][3]+0+3);
}
}
int ans = min4(dp[N-1][0]+3, dp[N-1][1]+2, dp[N-1][2]+1, dp[N-1][3]);
printf("Case #%d: %d\n", 1+_t, ans);
}
}
終了
蓋を開けてみれば４問とも通っていて、まさかの全完。
ただ、24時間あったから行けただけで、これが2時間半とか3時間とかだったら、焦って（途中までやっては放棄して次に行くなどして）1つも取れなかったりするんだよね…
それではRound 2でお会いしましょう！
Tシャツ取れるといいなあ（先着500名様）