Regionals 2011 :: Asia - Amritapuri
5983 - MAGRID
問題
R×Cのフィールドを左上から右下までいくことを考える（右または下にのみ移動可能）。
スタートするとき、ある値のパワーを持っている。
ある場所でのフィールドの数字をSとする。
S>0のときSだけパワーを得る。
S<0のとき|S|だけパワーを失う。
パワーが0以下になってはいけないという条件があるとき、スタートするときのパワーの最小値を求めよ。
解法
DP[i][j] = (i,j)まで行くとき、(0,0)で必要なパワーの最小値
として左上からDPしようとすると、次の値を計算するとき結局現在のパワーが必要になって困る。そこで、
DP[i][j] = (i,j)から(R-1,C-1)まで行くとき、(i,j)で必要なパワーの最小値
として右下からDPすると、
DP[i][j] = max(1, min(DP[i+1][j], DP[i][j+1])-S[i][j]))
と計算することが出来る。
答えはDP[0][0]。
5984 - Save the Students!
問題
三角形、正方形、円が複数個与えられるので、その図形どれかに含まれる（辺上も含む）格子点の数を求めよ。
解法
図形の大きさの制約が書かれていないが、そんなに大きくないらしい。
ということで、それぞれの図形に含まれる格子点をsetに入れて数えるだけ。
5985 - Robbing Gringotts
問題
M人のデスイーターがいて、N個の金庫がある。
デスイーターはそれぞれ容量V[i]のバッグを持っている。
金庫はX[i]個の金を保有し、それぞれの重さがg[i][j]で与えられる。
金の価値は重さに等しい。
デスイーターは１人につき多くて１つの金庫に盗みに入る。
また、１つの金庫に複数人のですイーターが盗みに入ることはない。
さらに、バッグにちょうどぴったり収まらなけらば盗むことはできない。
このとき、デスイーターが盗むことの出きる金の価値の合計を求めよ。
解法
- どのデスイーターがどの金庫に盗みに入ることが出来るか
- どのデスイーターをどの金庫に割り当てるか
という２つの問題に分けることが出来る。
1.は半分全列挙、2.は最小費用流で求めることが出来る。
- 1.について
X[i]<=25なので、
ある金庫において、2^(X[i]/2)通りの金の組み合わせにおける重さの合計をsetに入れ、
残りの2^(X[i]-X[i]/2)通りの金の組み合わせにおける重さの合計について、足してV[j]になるようなものがsetに含まれているかどうかで、デスイーターjが金庫iに盗みに入ることが出来るかを判定する。
- 2.について
盗みに入れるかどうかの関係は、デスイーターと金庫の二部グラフになる。
盗みに入れるなら、-V[j]を辺のコストとし、容量を1とする。
この二部グラフで最小重み二部マッチングを解き、最小コストのマイナスをとったものが答えとなる。
ソース
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <complex> #include <cstring> #include <cstdlib> #include <string> #include <cmath> #include <cassert> #include <queue> #include <set> #include <map> #include <valarray> #include <bitset> #include <stack> using namespace std; #define REP(i,n) for(int i=0;i<(int)n;++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(), (c).end() const int INF = 1<<28; typedef long long Weight; struct Edge { int src, dst; Weight capacity, cost; Edge(int src, int dst, Weight capacity, Weight cost) : src(src), dst(dst), capacity(capacity), cost(cost) { } }; bool operator < (const Edge &e, const Edge &f) { return e.cost != f.cost ? e.cost > f.cost : // !!INVERSE!! e.src != f.src ? e.src < f.src : e.dst < f.dst; } typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef vector<Weight> Array; typedef vector<Array> Matrix; void add_edge(Graph &g, int s, int d, Weight cap, Weight cost) { g[s].push_back(Edge(s,d,cap,cost)); g[d].push_back(Edge(d,s,0,-cost)); } #define RESIDUE(u,v) (capacity[u][v] - flow[u][v]) #define RCOST(u,v) (cost[u][v] + h[u] - h[v]) pair<Weight, Weight> minimumCostFlow(const Graph &g, int s, int t) { const int n = g.size(); Matrix capacity(n, Array(n)), cost(n, Array(n)), flow(n, Array(n)); REP(u,n) FOR(e,g[u]) { capacity[e->src][e->dst] += e->capacity; cost[e->src][e->dst] += e->cost; } pair<Weight, Weight> total; // (cost, flow) vector<Weight> h(n); for (Weight F = INF; F > 0; ) { // residual flow vector<Weight> d(n, INF); d[s] = 0; vector<int> p(n, -1); REP(k, n) REP(i, n) FOR(e,g[i]) if (RESIDUE(e->src, e->dst)) { if (d[e->dst] > d[e->src] + RCOST(e->src, e->dst)) { d[e->dst] = d[e->src] + RCOST(e->src, e->dst); p[e->dst] = e->src; } } if (d[t] == INF) break; Weight f = F; for (int u = t; u != s; u = p[u]) f = min(f, RESIDUE(p[u], u)); for (int u = t; u != s; u = p[u]) { total.first += f * cost[p[u]][u]; flow[p[u]][u] += f; flow[u][p[u]] -= f; } F -= f; total.second += f; REP(u, n) h[u] += d[u]; } return total; } int V[100]; int v[25]; int main() { int T; cin >> T; while(T--) { int n, m; cin >> m >> n; Graph G(m+n+2); REP(i, m) { add_edge(G, m+n, i, 1, 0); } REP(i, n) { add_edge(G, m+i, m+n+1, 1, 0); } REP(i, m) { cin >> V[i]; } REP(i, n) { int X; cin >> X; REP(j, X) { cin >> v[j]; } set<int> se; REP(j, 1<<(X/2)) { int sum = 0; REP(k, X/2) { if (j>>k&1) sum += v[k]; } se.insert(sum); } bool flag[m]; memset(flag,0,sizeof(flag)); REP(j, 1<<(X-X/2)) { int sum = 0; REP(k, X-X/2) { if (j>>k&1) sum += v[X/2+k]; } REP(k, m) { if (!flag[k] && se.count(V[k]-sum)) { flag[k] = 1; add_edge(G, k, m+i, 1, -V[k]); } } } } cout << -minimumCostFlow(G, m+n, m+n+1).first << endl; } }
5986 - Wizarding Duel
5987 - Distinct Primes
問題
３つ以上の異なる素数を約数に持つような数字をlucky numberと呼ぶ。
nが与えられるので、n番目のlucky numberを求めよ。
解法
最初にlucky numberを1000個求めておく。
それぞれの数について、3つ以上の素数で割りきれるかどうか普通にループで試せばいい。
5988 - Magical Bridges
問題
円状に並んだ塔がある。
ある塔のある階からある塔のある階までつながれた橋がいくつかある。
同じ塔の中で１階昇り降りするのは1秒かかる。
塔の１階から隣の塔の1階へ移動するのも1秒かかる。
橋を渡るのに何秒かかるかは指定される。
qbi,qfi,qbj,qfjからなるクエリが与えられるので、それぞれについて、塔qbiのqfi階から、塔qbjのqfj階までいくのに最短で何秒かかるかを求めよ。
解法
階段が繋がれた所、それぞれの塔の1階をノードとしてグラフを構成し、全点間最短距離を求めておく。
各クエリに対して、
(qbi,qfi)と一番近いところに対応するノードa、(qbj,qfj)と一番近いところに対応するノードbを求める（上と下で最も近いところを探すべきなので、aとbはそれぞれ最大2個ある）。
それぞれのaとbの組み合わせに対して
((qbi,qfi)からaの距離) + ((qbj,qfj)からbの距離) + (グラフにおけるaとbの最短距離)
を計算し、その最小を答えとする。
ただしqbi=qbjのときは、|qfi-qbj|も解候補とする。
5989 - Here Be Dragons!
問題
廊下を渡る。
ドラゴンがいると渡れない。
端まで廊下を渡り切ることが出来るかどうかを判定せよ。
解法
ドラゴンが１匹でもいるかどうか調べるだけ。
5990 - Array Diversity
問題
リストのdiversityを最大値と最小値の差で定める。
リストが与えられるので、diversityを変えないような部分文字列と部分列の数をmod1000000009で出力せよ。
解法
maxとなるものの数をn1, minとなるものの数をn2とする。
部分列は簡単で、n1から1個以上、n2から1個以上、その他からは何個でも取ればいいので、
となる。ただしmaxとminが等しい、つまりリスト全ての数が等しい時は例外処理必要。
部分文字列は、包徐原理を用いて、
(部分文字列全体の数) - (maxを含まないような部分文字列の数) - (minを含まないような部分文字列の数) + (maxもminも含まないような部分文字列の数)
で計算できる。ちなみに部分文字列の数は、n(n+1)/2で表せる。
また包徐原理を使わなくても、しゃくとり法により各iについてminとmaxをどちらかを含まない[i,j]を計算できるので、それを用いて計算することも出来る。
5991 - Generations
問題
ドラゴンの親子関係と、それぞれのドラゴンが何年から何年まで生きたかの情報が与えられる。
親子関係は多分木になっている。
また、全ての親子について、
（子供が生まれた年） >= （親が生まれた年）
が成り立つ。
それぞれのドラゴンについて、共通して生きている年があるドラゴンのうち最も下の世代はいくら下かを求めよ。
5992 - Goblin Wars
問題
R×Cのフィールドが与えられる。
＃は壁、英小文字はゴブリンの居住区を表す。
各単位時間において、ゴブリンは隣接する４方向に居住区を伸ばすことを考える。
同じタイミングで複数のゴブリンが同じ区画に進出しようとするとバトルになり、*で表される。
一度バトルになったらずっとそのままで、なっていない箇所では居住区を伸ばし続ける。
何も変わらなくなったら終了。
解法
queueを使った。
queueに入れる状態は、ゴブリンの種類、座標、そこに移動したターン数。
最初に、初期状態でゴブリンがいる場所全てに対してqueueに入れる。
ある状態から４方向を見て#では無かったら動かしてみる。
.だったらそのゴブリンを表す英小文字を書く。*だったら何もしない。
英数字でターン数が同じ時には*にする。
queueの中身がなくなったら終了。
