先週の予選ラウンドに引き続き第1回戦。
通過条件は24時間以内に35点取ること（所要時間不問）。
全4問で配点はそれぞれ10,25,25,40なので、Dを1問通すか、それ以外で2問。
今回はC++で参戦。
４問提出したうちの２問が通っていたのでRound 2進出。
10: Pie Progress (AC)
Pie Progress | Facebook Hacker Cup 2017 Round 1
結果
AC (10点)
方針
ある１日に売られているパイが 2 3 4 5 1 の場合
- 1枚調達：(1) + 1^2 = 2
- 2枚調達：(1+2) + 2^2 = 7
- 3枚調達：(1+2+3) + 3^2 = 15
- 4枚調達：(1+2+3+4) + 4^2 = 26
- 5枚調達：(1+2+3+4+5) + 5^2 = 40
沢山買うと第2項の累進的課税が辛い…
１枚毎の調達単価（差分）は
- 1枚目：(1) + 1^2 = 1+1 = 2
- 2枚目：(1+2)-(1) + 2^2-1^2 = 2+3 = 5
- 3枚目：(1+2+3)-(1+2) + 3^2-(2^2+1^2) = 3+5 = 7
- 4枚目：(1+2+3+4)-(1+2+3) + 4^2-(3^2+2^2+1^2) = 4+7 = 11
- 5枚目：(1+2+3+4+5)-(1+2+3+4) + 5^2-(4^2+3^2+2^2+1^2) = 5+9 = 14
パイの売価を安い順に{c0, c1, ...}とすると、それぞれの調達コストは c_i + (2*i - 1) になる。
あとは、N日食いつなげるようにパイを調達する（手持ちのパイを毎日１枚消費しつつ、調達コスト最安になるようにパイを買っていく）だけ。
priority queueを使った実装がさっと思いついたのでそのままC++で書いて提出。
実装
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(e,s) ((s).find(e)!=(s).end())
int main() {
int T; cin >> T;
for (int t=1; t<=T; ++t) {
priority_queue<int, vector<int>, greater<int> > pq;
int cost = 0;
int N, M; cin >> N >> M;
for (int i=0; i<N; ++i) {
vector<int> Ci(M);
for (int j=0; j<M; ++j) {
cin >> Ci[j];
}
sort(Ci.begin(), Ci.end());
for (int j=0,p=1; j<M; ++j,p+=2) {
int c = Ci[j] + p;
pq.push(c);
}
int cheapest = pq.top(); pq.pop();
cost += cheapest;
}
printf("Case #%d: %d\n", t, cost);
}
return 0;
}
25: Fighting the Zombies (WA)
Fighting the Zombies | Facebook Hacker Cup 2017 Round 1
結果
WA (0点)
方針（※WA）
無限平面の任意の場所を任意の半径の円で囲んで切り取って移動させて、その後にRxRの正方形で囲んだエリアのゾンビが倒せる…最大何匹倒せるか？
ゾンビは全部で50匹。
平面は無限だが、ゾンビが左辺と底辺（同一でも可）に来るようなRxRの正方形に限定してよいかなと。円で囲んで移動させる方も、結局はRxRの正方形の枠内に来るやつだけが倒せるので、RxRの正方形を2つ使って、最大限にゾンビを捕獲するゲーム？
（そこまでの実装でサンプルケースは通る）
いや、2つの正方形が重なった場合、円で切り取られて（折角正方形に入っていたのに）外に追いやられてしまうケースがあるだろ…移動させる側の正方形（を囲む円）をどう配置すればいいのか。それが分からなくて中断。
いや、２つの正方形が重なってた場合に、移動しない側の正方形にしか含まれないゾンビにはなるべく手を付けずに、移動側の正方形の中のゾンビだけをできるだけ多く移動させるような円が描けるかって話。
２つの正方形の辺の交わる２点間に直線が引ければ。
移動側の正方形を円が囲む必要も、円がその正方形に含まれる必要もない、ってことは、その直線に限りなく近い弧を描く円を使えば良いのか。
あ、それで円の中心も半径も任意なのか…
実装（※WA）
#include <iostream>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(e,s) ((s).find(e)!=(s).end())
typedef long long ll;
typedef pair<int, int> ii;
#ifdef DEBUG
#undef NDEBUG
#endif
#include <cassert>
int N, R;
vector<int> X, Y;
vector<ii> ps;
int P;
inline bool inside(int left, int bottom, int x, int y) {
return (left <= x && x <= left + R) && (bottom <= y && y <= bottom + R);
}
int sub(int i0, int i1) {
assert(0 <= i0 && i0 < P);
assert(0 <= i1 && i1 < P);
int left0 = ps[i0].first, bottom0 = ps[i0].second;
int left1 = ps[i1].first, bottom1 = ps[i1].second;
int cnt = 0;
rep(i, N) {
int x = X[i], y = Y[i];
if (inside(left0, bottom0, x, y) || inside(left1, bottom1, x, y)) {
++cnt;
}
}
return cnt;
}
int main() {
int T; cin >> T;
assert(1 <= T && T <= 50);
for (int t=1; t<=T; ++t) {
cin >> N >> R;
assert(1 <= N && N <= 50);
assert(1 <= R && R <= 1000000000);
X.resize(N);
Y.resize(N);
set<int> _xs, _ys;
rep(i, N) {
int x, y; cin >> x >> y;
assert(0 <= x && x <= 1000000000);
assert(0 <= y && y <= 1000000000);
X[i] = x;
Y[i] = y;
_xs.insert(x);
_ys.insert(y);
}
ps.clear();
tr(xt, _xs) {
int x = *xt;
tr(yt, _ys) {
int y = *yt;
ps.push_back(ii(x, y));
}
}
P = ps.size();
assert(1 <= P && P <= 10000);
int ans = 0;
for (int i=0; i<P-1; ++i) { // OOPS
for (int j=i+1; j<P; ++j) {
int c = sub(i, j);
ans = max(ans, c);
}
}
printf("Case #%d: %d\n", t, ans);
}
return 0;
}
反省点
計算時間を短縮しようと思って、最後の二重ループを書き直したのが敗因。
これだとP=1の時に死ぬ。
--- b1.cc 2017-01-16 00:03:12.000000000 +0900
+++ b2.cc 2017-01-16 03:58:24.000000000 +0900
@@ -78,8 +78,8 @@
assert(1 <= P && P <= 10000);
int ans = 0;
- for (int i=0; i<P-1; ++i) {
- for (int j=i+1; j<P; ++j) {
+ for (int i=0; i<P; ++i) {
+ for (int j=0; j<P; ++j) {
int c = sub(i, j);
ans = max(ans, c);
}
25: Manic Moving (WA)
Manic Moving | Facebook Hacker Cup 2017 Round 1
結果
WA (0点)
方針（※WA）
・トラックには２ファミリー分の家財しか積めない
・載せる順序も降ろす順序もリストの順番を厳守
トラックが取りうる状態とその遷移が限定されている。
「空(未着手)」「#1だけ運搬中」「#1と#2を運搬中」
「空(#1まで完了)」「#2だけ運搬中」「#2と#3を運搬中」
…
「空(#nまで完了)」
「#2だけ運搬中」には、「#1と#2を運搬中」から#1を下ろしてきた場合と、「空(#1まで完了)」に#2を積んだ場合がある。
「空(#2まで完了)」には、その２つの「#2だけ運搬中」からの遷移がある。
「空(未着手)」「#1を積んだところ」-「#1と#2を運搬中」
「空(#1まで完了)」「#2を積んだところ」「#1を下ろして#2を運搬中」「#2と#3を運搬中」
...
とすると、それぞれの状態が都市番号に１対１で対応する。
ワーシャルフロイドで求めた最短経路（ガソリン最小経路）を用いて、各状態の最小コストをDPで計算していく。
実装（※WA）
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <utility>
using namespace std;
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(e,s) ((s).find(e)!=(s).end())
// #undef NDEBUG
#include <cassert>
#define INFTY 10000000
int main(int argc, char **argv) {
ifstream fin(argv[1]);
int T; fin >> T;
assert(1 <= T && T <= 100);
for (int t=1; t<=T; ++t) {
int N, M, K; fin >> N >> M >> K;
assert(2 <= N && N <= 100);
assert(1 <= M && M <= 5000);
assert(1 <= K && K <= 5000);
vector<vector<int> > dist(N, vector<int>(N, INFTY));
rep(i, N) dist[i][i] = 0;
rep(i, M) {
int Ai, Bi, Gi; fin >> Ai >> Bi >> Gi;
--Ai; --Bi;
assert(0 <= Ai && Ai < N);
assert(0 <= Bi && Bi < N);
assert(1 <= Gi && Gi <= 1000);
dist[Ai][Bi] = dist[Bi][Ai] = Gi;
}
vector<pair<int, int> > family;
rep(i, K) {
int Si, Di; fin >> Si >> Di;
--Si; --Di;
assert(0 <= Si && Si < N);
assert(0 <= Di && Di < N);
family.push_back(make_pair(Si, Di));
}
// warshall_floyd
rep(i, N) rep(j, N) rep(k, N) {
dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
}
vector<vector<int> > dp(2, vector<int>(4, INFTY));
vector<vector<int> > at(2, vector<int>(4, -1));
rep(i, K) {
int Si = family[i].first, Di = family[i].second;
if (dist[0][Si] == INFTY || dist[0][Di] == INFTY) {
goto impossible;
}
}
for (int i=0; i<=K; ++i) {
int i0 = i % 2, i1 = (i+1) % 2;
// 0: 0 s0 - s1
// 1: e- s0 e- s1
dp[i0].assign(4, INFTY);
if (i == 0) {
at[i0][0] = at[i0][2] = 0;
} else {
at[i0][0] = at[i0][2] = family[i-1].second;
}
if (i < K) {
at[i0][1] = family[i].first;
if (i < K-1) {
at[i0][3] = family[i+1].first;
}
}
// rep(n, 4) assert(0 <= at[i0][n] && at[i0][n] < N);
if (i == 0) {
dp[i0][0] = 0; // 0
} else {
dp[i0][0] = dp[i1][1] + dist[ at[i1][1] ][ at[i0][0] ];
if (i >= 2) {
dp[i0][0] = min(dp[i0][0],
dp[i1][2] + dist[ at[i1][2] ][ at[i0][0] ]);
}
if (i == K) break;
}
dp[i0][1] = dp[i0][0] + dist[ at[i0][0] ][ at[i0][1] ];
if (i > 0) {
dp[i0][2] = dp[i1][3] + dist[ at[i1][3] ][ at[i0][2] ];
}
if (i < K-1) {
dp[i0][3] = dp[i0][1] + dist[ at[i0][1] ][ at[i0][3] ];
if (i > 0) {
dp[i0][3] = min(dp[i0][3],
dp[i0][2] + dist[ at[i0][2] ][ at[i0][3] ]);
}
}
}
printf("Case #%d: %d\n", t, dp[K%2][0]);
continue;
impossible:
printf("Case #%d: -1\n", t);
}
return 0;
}
反省点
あとで。
40: Beach Umbrellas (AC)
Beach Umbrellas | Facebook Hacker Cup 2017 Round 1
結果
AC (40点)
方針
何通りの組み合わせがあるか数え上げて1000000007での剰余を答えるやつ。
配点の割に難しくないのでは？
両端に来る２本の傘を選ぶ（2 x nC2通り）と、片方の傘の軸からもう片方の傘の軸までの最短距離が決まる →Σ(傘の半径x2) - Σ(端にある２本の傘の半径)
そうすると全体の自由度が決まるので、あとはどの傘立てを使う／使わないか（n+rCn通り）、傘をどの順番で並べるか（(n-2)!通り）が求められればその合計。
modでの加減乗除はフェルマーの小定理を使うやつ。
実装
#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
using namespace std;
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
#define tr(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(e, s) ((s).find(e)!=(s).end())
typedef long long ll;
typedef pair<ll,ll> ll2;
const ll MOD = 1000000007LL;
map<ll2, ll> cmm;
ll add(ll x, ll y) { return (x + y) % MOD; }
ll sub(ll x, ll y) { return (x - y) % MOD; }
ll mul(ll x, ll y) { return (x * y) % MOD; }
ll pow(ll x, ll y) {
ll v = 1;
for (; y; x=mul(x,x),y>>=1)
if (y&1) v = mul(v, x);
return v;
}
ll divi(ll x, ll y) { return mul(x, pow(y, MOD-2)); }
ll C(ll n, ll k) { // nCk
ll2 p(n, k);
if (found(p, cmm)) return cmm[p];
ll v = 1;
for (ll i=1; i<=k; ++i)
v = divi(mul(v, n-i+1), i);
return cmm[p] = v;
}
ll solve(int N, ll M, vector<ll>& R) {
if (N == 1) return M;
ll w_all = 0LL;
rep(i, N) w_all += R[i]*2;
ll ans = 0LL;
ll fac = 1LL;
for (ll i=1LL; i<=N-2; ++i) fac = mul(fac, i);
for (int i=0; i<N-1; ++i) {
for (int j=i+1; j<N; ++j) {
ll w = w_all - R[i] - R[j];
ll red = (M-1) - w;
if (red < 0) continue;
ans = add(ans, C(N+red, N));
}
}
return mul(ans, fac*2);
}
int main() {
int T; cin >> T;
for (int t=1; t<=T; ++t) {
int N;
ll M;
cin >> N >> M;
vector<ll> R(N);
rep(i, N) cin >> R[i];
printf("Case #%d: %lld\n", t, solve(N, M, R));
}
return 0;
}