ABCが通って393位.
A. Falling Balls
問題概要
列の2次元グリッドがあって, 各列の一番上からボールを落下させる.
グリッドは '/', '\', '.' のいずれかから構成されて, '/' ならそこに落ちてきたボールは左の列に, '\' ならそこに落ちてきたボールは右の列に移動する. 他のボール同士は重なることができる.
一番下の 列目に到達したボールの個数は 個だった. 下の行と, 左右の列はすべて '.' で構成されていたことがわかっている. そのようなグリッドが存在するか判定し, 存在する時考えられる最小の行からなるグリッドの例を出力せよ.
解法
まず, 左右の列の が のとき, IMPOSSIBLE. 3秒考えるとそれ以外のときは必ず構成できることがわかる.
具体的な構成方法は, 左に落ちてくるボールの数から順番に調整する. その列に落ちてくるべきボールの列の範囲 がわかるので, 一番下のその列から斜め方向に適切な数だけ '\' と '/' を 本ずつ生やせば良い.
.
#include<bits/stdc++.h> using namespace std; void beet() { int W, C[100]; scanf("%d", &W); for(int i = 0; i < W; i++) { scanf("%d", &C[i]); } if(C[0] == 0 || C[W - 1] == 0) { puts("IMPOSSIBLE"); return; } int t[110][110] = {{}}; int l = 0; int pos = 1; for(int i = 0; i < W; i++) { if(C[i] == 0) continue; int r = l + C[i]; // [l, r) for(int j = 0; j < i - l; j++) { t[104 - j][i - j - 1] = 1; pos = max(pos, j + 2); } for(int j = 0; j < r - i - 1; j++) { t[104 - j][i + j + 1] = 2; pos = max(pos, j + 2); } l = r; } printf("%d\n", pos); for(int i = 0; i < pos; i++) { for(int j = 0; j < W; j++) { if(t[106 - pos + i][j] == 1) putchar('\\'); else if(t[106 - pos + i][j] == 2) putchar('/'); else putchar('.'); } putchar('\n'); } } int main() { int T; scanf("%d", &T); for(int i = 1; i <= T; i++) { printf("Case #%d: ", i); beet(); } }
B. Graceful Chainsaw Jugglers
問題概要
個の赤いチェーンソーと 個の青いチェンソーがある. これを何人かで分け合うが, 次の条件を満たす必要がある.
- すべての人は つ以上のチェーンソーを持つ必要がある.
- ある人と赤の数も青の数がともに同数のチェーンソーを持っている人が存在してはならない.
最大で何人にチェーンソーを分け合えるか.
解法
なんか制約的にDPを疑う.
赤を 個と青を任意個のペアを作る前には, 赤を 個と青を任意個のペアを作っておいたほうがおとく.
そこで, 再帰関数 rec(k, r, b) を, 今までに赤を1人あたりの最大で 個使って, 赤が残り 個, 青が残り 個のときに得られる最大人数と定義する.
個の赤とペアリングする青は, 個の順番にするのが最適なので, まあこれは赤の数を全探索して遷移させればできる.
複数テストケースが与えられるが, メモ化配列を毎回初期化せずに使い回せるので, 全体で くらいと見積もれば, 実際はもっと少なそうなので間に合う.
#include<bits/stdc++.h> using namespace std; int dp[505][505][505]; int rec(int blackcur, int black, int white) { if(~dp[blackcur][black][white]) return dp[blackcur][black][white]; int ret = 0; for(int i = 1;; i++) { int blackrest = black - blackcur * i; int whiterest = white - i * (i - 1) / 2; if(blackrest < 0 || whiterest < 0) break; ret = max(ret, rec(blackcur + 1, blackrest, whiterest) + i); } return dp[blackcur][black][white] = ret; } void beet() { int x, y; scanf("%d %d", &x, &y); int ret = rec(1, x, y); for(int i = 1;; i++) { int whiterest = y - i * (i + 1) / 2; if(whiterest < 0) break; ret = max(ret, rec(1, x, whiterest) + i); } printf("%d\n", ret); } int main() { memset(dp, -1, sizeof(dp)); int T; scanf("%d", &T); for(int i = 1; i <= T; i++) { printf("Case #%d: ", i); beet(); } }
C. Costume Change
問題概要
のグリッドが与えられる. 行 列目には が書かれている.
次の操作がコスト でできる.
- あるマスの符号を反転させる
- あるマスの値を同符号の範囲で絶対値が 以上 以下の数に変更する.
すべての行, 列をみたときに同じ値が存在しないようにしたい. このために必要な操作の最小回数を求めよ.
解法
貪欲は無理そうとなると, どうみてもフロー以外の選択肢は残されていないのでフローを考える.
変更するマスの数の最小化はつまり, 残すマスの数の最大化である. そこで, から の値ごとに残すマスの数を最大化したい気持ちになるが, これは蟻本にも載っている一方に行, もう一方に列をおいた二部マッチングにより解ける.
使わなかったセルをどうしようかなーと思っていると, 適切に操作することでなんとなくコスト で変更できそうな気がしてきて, 変更できないと解ける問題には見えないので投げると通る(?).
#include<bits/stdc++.h> using namespace std; using int64 = long long; struct Bipartite_Matching { vector< vector< int > > graph; vector< int > dist, match; vector< bool > used, vv; Bipartite_Matching(int n, int m) { graph.resize(n); match.assign(m, -1); used.assign(n, false); } void add_edge(int u, int v) { graph[u].push_back(v); } void bfs() { dist.assign(graph.size(), -1); queue< int > que; for(int i = 0; i < graph.size(); i++) { if(!used[i]) { que.emplace(i); dist[i] = 0; } } while(!que.empty()) { int a = que.front(); que.pop(); for(auto &b : graph[a]) { int c = match[b]; if(c >= 0 && dist[c] == -1) { dist[c] = dist[a] + 1; que.emplace(c); } } } } bool dfs(int a) { vv[a] = true; for(auto &b : graph[a]) { int c = match[b]; if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) { match[b] = a; used[a] = true; return (true); } } return (false); } int bipartite_matching() { int ret = 0; while(true) { bfs(); vv.assign(graph.size(), false); int flow = 0; for(int i = 0; i < graph.size(); i++) { if(!used[i] && dfs(i)) ++flow; } if(flow == 0) return (ret); ret += flow; } } }; void beet() { int N, X[100][100]; scanf("%d", &N); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { scanf("%d", &X[i][j]); } } int ret = 0; for(int i = -N; i <= N; i++) { Bipartite_Matching flow(N, N); for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { if(X[j][k] == i) flow.add_edge(j, k); } } ret += flow.bipartite_matching(); } cout << N * N - ret << endl; } int main() { int T; scanf("%d", &T); for(int i = 1; i <= T; i++) { printf("Case #%d: ", i); beet(); } }
D. Gridception
えーなんかたぶん誤読しているので(悲しいね