https://code.google.com/codejam/contest/5314486/dashboard#s=p0
A. Fresh Chocolate
Nグループあり、それぞれG[i]人いる。
1パックにP個のチョコが入っている。
あるグループにチョコを上げる時はパックを開けてチョコを1人に1つ渡す。
もし、チョコが余った場合は次のグループに渡すのに使うが、その場合は新鮮でないチョコが次のグループの一部(または全部)にいってしまう。
適切な順でNグループにチョコを渡すことで、最大何グループが全員新鮮なチョコを受け取れるか。
B. Roller Coaster Scheduling
N行1列のコースター、C人の人間、M枚のチケットがある。
i番目のチケットにはB[i]さんが前からP[i]番目の席に座れると書いてある。
コースター運営者は"プロモート"を上手く行い、使うコースターの数を最小化した上で、プロモート回数も最小化したい。
以下のルールが満たされる必要がある。
- 同じコースターに同一人物は複数人乗れない
- 同じコースターの同じ席に複数人乗れない
- プロモートをすると、あるチケットのP[i]をより小さい数に変更できる
C. Beaming With Joy
R行C列の盤面があり、以下の構成要素から成る。
- / : /となってる反射板(ビームを反射する)
- \ : \となってる反射板(ビームを反射する)
- - : 左右にビームを発射する発射機
- | : 上下にビームを発射する発射機
- # : 壁(ビームが止まる)
- . : 何もない
2種類の発射機は回転させることで-を|に、|を-に変えることができる。
発射機を適切に回転させて、以下のルールを全て満たすようにできるか。
できれば、回転後の盤面も答えよ。
- 全ての何もない所にビームが来ている
- 発射機にビームが当たってはいけない
D. Shoot the Turrets
未読
以下、解説
A. Fresh Chocolate
int N, P, G[101]; int cnt[4]; //--------------------------------------------------------------------------------------------------- int dp[201][201][201]; int dodp() { rep(a, 0, cnt[1] + 1) rep(b, 0, cnt[2] + 1) rep(c, 0, cnt[3] + 1) dp[a][b][c] = 0; rep(a, 0, cnt[1] + 1) rep(b, 0, cnt[2] + 1) rep(c, 0, cnt[3] + 1) { int sm = a + b * 2 + c * 3; int d = dp[a][b][c]; if (sm % P == 0) d++; dp[a+1][b][c] = max(dp[a+1][b][c], d); dp[a][b+1][c] = max(dp[a][b+1][c], d); dp[a][b][c+1] = max(dp[a][b][c+1], d); } return dp[cnt[1]][cnt[2]][cnt[3]]; } //--------------------------------------------------------------------------------------------------- void sol() { cin >> N >> P; rep(i, 0, N) cin >> G[i]; rep(i, 0, P) cnt[i] = 0; rep(i, 0, N) cnt[G[i] % P]++; int ans = cnt[0]; if (P == 2) ans += (cnt[1] + 1) / 2; else if (P == 3) { int mi = min(cnt[1], cnt[2]); cnt[1] -= mi; cnt[2] -= mi; ans += mi; ans += (cnt[1] + 2) / 3; ans += (cnt[2] + 2) / 3; } else if (P == 4) { ans += dodp(); } printf("%d\n", ans); }|
まず、「cnt[i] = G[j] % P == iであるjの個数」としてこれを計算しておく。
全ての場合においてcnt[0]では全員とりあえず新鮮なチョコを貰えるので、これを答えに足しておく。
small解法
貪欲解で解ける。
P==2の時は、cnt[1]は奇数で2グループに1つ新鮮なチョコが得られるので、ceil(cnt[1]/2)も足す
P==3の時は、cnt[1]とcnt[2]を丁度1つずつ使うことで丁度Pが作れるので、なるだけこのペアを作る。
作れなくなったら、cnt[1]だけで、cnt[2]だけでPを作るようにして、計算する。
large解法
P == 4の時は、DPで解く(貪欲解で解いて死んだ)。
dp[a][b][c] := cnt[1]をa個、cnt[2]をb個、cnt[3]をc個使うときの新鮮なチョコを食べられるグループの最大
を計算していく。
dp[a][b][c]からdp[a+1][b][c],dp[a][b+1][c],dp[a][b][c+1]への遷移を考えていくのだが、食べる前の状況を考えてみると、(a+2b+3c) % P == 0であれば、次食べるグループは新鮮なチョコが食べられるのでインクリメントする。
これで更新してcnt[0]と合わせると答え。
B. Roller Coaster Scheduling
small解法
フローで解けるみたいです
large解法
貪欲法で解ける。JAPLJさんの解法を解読した。
int N, C, M, P[1010], B[1010]; int S[1010], K[1010]; //--------------------------------------------------------------------------------------------------- int ceil(int a, int b) { return (a + b - 1) / b; } void solve() { cin >> N >> C >> M; rep(i, 0, M) cin >> P[i] >> B[i]; rep(i, 0, 1010) S[i] = K[i] = 0; rep(i, 0, M) { S[P[i]]++; K[B[i]]++; } // 1 int ans1 = *max_element(K, K + C + 1); // 2 int sm = 0; rep(i, 1, N + 1) { sm += S[i]; ans1 = max(ans1, ceil(sm, i)); } // 3 int ans2 = 0; rep(i, 1, N + 1) ans2 += max(0, S[i] - ans1); printf("%d %d\n", ans1, ans2); }
1. 同じコースターに同じ人は乗れないので、ある人の乗る回数の最大値分は必要
(こうすることで同じ人が同じカートに乗ってはいけないという条件は無視できる)
2. [1,i]列目のチケット数の総数をsmとすると、各コースターのi列目まで埋めていくと考えると、ceil(sm/i)コースター必要なので、これで最大値を更新していく
3. これで必要なコースター数が分かったので、座る席をずらさないといけないのは、各席についてコースター数を上回ったときなので、これを足していく
この貪欲で答えが出せる
C. Beaming With Joy
smallとlargeで解法が全然違う(と思う)
small解法
#define rrep(i,a,b) for(int i = a;i>=b;i--) int H, W; string B[60]; vector<int> v; //--------------------------------------------------------------------------------------------------- int C[60][60], ans[10101]; int chk() { rep(y, 0, H) rep(x, 0, W) if (B[y][x] == '.') if (C[y][x] == 0) return false; return true; } //--------------------------------------------------------------------------------------------------- bool dfs(int cu) { if (cu == v.size()) { return chk(); } int x = v[cu] % W; int y = v[cu] / W; // 囲まれている if (B[y - 1][x] == '#' && B[y + 1][x] == '#' && B[y][x - 1] == '#' && B[y][x + 1] == '#') return dfs(cu + 1); // '-' bool ok = true; rep(xx, x + 1, W) { if (B[y][xx] == '#') break; if (B[y][xx] == 'X') { ok = false; break; } } rrep(xx, x - 1, 0) { if (B[y][xx] == '#') break; if (B[y][xx] == 'X') { ok = false; break; } } if (ok) { rep(xx, x + 1, W) { if (B[y][xx] == '#') break; C[y][xx]++; } rrep(xx, x - 1, 0) { if (B[y][xx] == '#') break; C[y][xx]++; } ans[cu] = 0; bool a = dfs(cu + 1); if (a) return true; rep(xx, x + 1, W) { if (B[y][xx] == '#') break; C[y][xx]--; } rrep(xx, x - 1, 0) { if (B[y][xx] == '#') break; C[y][xx]--; } } // '|' ok = true; rep(yy, y + 1, H) { if (B[yy][x] == '#') break; if (B[yy][x] == 'X') { ok = false; break; } } rrep(yy, y - 1, 0) { if (B[yy][x] == '#') break; if (B[yy][x] == 'X') { ok = false; break; } } if (ok) { rep(yy, y + 1, H) { if (B[yy][x] == '#') break; C[yy][x]++; } rrep(yy, y - 1, 0) { if (B[yy][x] == '#') break; C[yy][x]++; } ans[cu] = 1; bool a = dfs(cu + 1); if (a) return true; rep(yy, y + 1, H) { if (B[yy][x] == '#') break; C[yy][x]--; } rrep(yy, y - 1, 0) { if (B[yy][x] == '#') break; C[yy][x]--; } } return false; } //--------------------------------------------------------------------------------------------------- void sol() { cin >> H >> W; rep(y, 1, H + 1) cin >> B[y]; rep(y, 1, H + 1) B[y] = "#" + B[y] + "#"; W += 2; H += 2; B[0] = ""; B[H - 1] = ""; rep(x, 0, W) B[0] += "#", B[H - 1] += "#"; v.clear(); rep(y, 0, H) rep(x, 0, W) if (B[y][x] == '|' || B[y][x] == '-') B[y][x] = 'X'; rep(y, 0, H) rep(x, 0, W) if (B[y][x] == 'X') v.push_back(y * W + x); rep(y, 0, H) rep(x, 0, W) C[y][x] = 0; if (!dfs(0)) { printf("IMPOSSIBLE\n"); return; } printf("POSSIBLE\n"); rep(i, 0, v.size()) { int x = v[i] % W; int y = v[i] / W; if (ans[i] == 0) B[y][x] = '-'; else B[y][x] = '|'; } rep(y, 1, H - 1) { string s = B[y].substr(1, W - 2); printf("%s\n", s.c_str()); } }
無駄に長いのだが、やってることは単純で、全ての発射機を-にするか|にするかの2択で全探索している。
全ての何もない所にビームが当たるかは「C[y][x] := (x,y)にビームが当たっている回数」を使って判定する。
そのままこれをやると、終わらないので、ちょっとした枝刈りが必要で、上下左右が壁で囲まれている場合はどちらでもいいので、1択で決め打ちすると、なぜかすぐ終わる。
large解法
2-SATを使う
hamayanhamayan.hatenablog.jp
確かになぁという感じ。
実装したらLargeが落ちてデバッグ無理!
D. Shoot the Turrets
プロは費用最小流とか言ってました。