ARC 056 B
今回はこの問題です。
n箇所の駐車場所があります。お互いにm本の道によってつながっています。s番目の駐車場所が駐車場の入り口になっています。1番からn番目の人が順番に駐車していきます。i番目の人はi番目の駐車場所に駐車します。すでに駐車された場所はとおることができません。このとき、自分の決められた場所に駐車できる人の番号を降順に求めてください、という問題です。
解けなかったので解説を見てときました。回答はこんな感じです。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int main() { int n, m, s; cin >> n >> m >> s; vector<vector<int> > road(200001); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; road[u].push_back(v); road[v].push_back(u); } vector<int> ans; vector<int> minnum_mustgo(n + 1, 0); minnum_mustgo[s] = s; priority_queue<int> qu; qu.push(s); while(!qu.empty()){ int nowplace = qu.top(); // cout << nowplace << " " << minnum_mustgo[nowplace] << endl; qu.pop(); for(int i = 0; i < road[nowplace].size(); i++){ int nextplace = road[nowplace][i]; if(min(minnum_mustgo[nowplace], nextplace) > minnum_mustgo[nextplace]){ minnum_mustgo[nextplace] = min(minnum_mustgo[nowplace], nextplace); qu.push(nextplace); } } } for(int i = 1; i <= n; i++){ if(minnum_mustgo[i] >= i) cout << i << endl; } return 0; }
minnum_mustgo[i]は駐車場の入り口からi番目の駐車場所に移動するのに通らないといけない駐車場所のうち最小の番号が記録されます。この番号がiよりも小さければ、すでに車が止められた場所を通らないと車を止められない、したがって車を止められないということになります。
minnum_mustgo[i]をダイクストラ法を用いてもとめていきます。min(minnum_mustgo[nowplace], nextplace)は入り口からnowplaceに行くのに通らなければいけない駐車場所のうちの最小の番号と、次に通る場所の番号のうち小さいもの、つまり入り口からnextplaceへ行くのに通らないといけない駐車場所のうち最小の番号となります。priority_queueでは値の大きいものから順に取り出されるので、大きい番号の駐車場所ばかり通っていく道から順に見つかっていきます(と思います)。
解説を理解するのに少し時間がかかりました…難しかったです。
ABC 008 D
今回はこの問題です。
問題文はめどいので省略します…単純な話ですが文章で説明するのは大変です。
この問題のやっかいなところは、wやhが10^6まで大きくなることです。メモ化するにも工夫が要ります。
今回はmapを使いました。キーは左下の座標、右上の座標の4つの数字になっています。pairがいっぱい出てくるので見にくいしちょっと汚い気がします…。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int w, h, n; vector<int> goldx, goldy; map<pair<pair<int, int>, pair<int, int> > , long long int> result; bool isin(int x1, int y1, int x2, int y2, int nowx, int nowy) { return (nowx >= x1 && nowx <= x2 && nowy >= y1 && nowy <= y2); } long long int solve(int x1, int y1, int x2, int y2) { // cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl; if(!isin(1, 1, w, h, x1, y1) || !isin(1, 1, w, h, x2, y2)) return 0; if(result.find(make_pair(make_pair(x1, y1), make_pair(x2, y2))) != result.end()) return result[make_pair(make_pair(x1, y1), make_pair(x2, y2))]; long long int ans = 0; for(int i = 0; i < n; i++){ int nowx = goldx[i], nowy = goldy[i]; if(!isin(x1, y1, x2, y2, nowx, nowy)) continue; long long int result = (x2 - x1) + (y2 - y1) + 1; if(nowx - 1 >= x1 && nowy - 1 >= y1) result += solve(x1, y1, nowx - 1, nowy - 1); if(nowx + 1 <= x2 && nowy - 1 >= y1) result += solve(nowx + 1, y1, x2, nowy - 1); if(nowx - 1 >= x1 && nowy + 1 <= y2) result += solve(x1, nowy + 1, nowx - 1, y2); if(nowx + 1 <= x2 && nowy + 1 <= y2) result += solve(nowx + 1, nowy + 1, x2, y2); ans = max(ans, result); } // cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << ans << endl; result[make_pair(make_pair(x1, y1), make_pair(x2, y2))] = ans; return ans; } int main() { cin >> w >> h >> n; for(int i = 0; i < n; i++){ int tmpx, tmpy; cin >> tmpx >> tmpy; goldx.push_back(tmpx); goldy.push_back(tmpy); } cout << solve(1, 1, w, h) << endl; }
メモ化再帰で、引数で指定された範囲で得られる金塊の数の最大値を求めていきます。resultにはその結果が書き込まれています。
まず、動かす装置を選びます。そのあと、その装置の上下左右の範囲について、得ることのできる金塊の数の最大値を求めます。その結果と、最初に選んだ装置を動かすことで得られる金塊の数の和を求めます。範囲内にある装置すべてに対して求め、その最大値を選んでresultに記録すればいいです。
ABC 022 C
今回はこの問題です。
頂点n個、辺m本からなる重みつきグラフが与えられます。頂点1を通る閉路(おなじ道を2回以上通らない)のうち、重みの和の最小値を求めましょうという問題です。
ダイクストラ法やワーシャルフロイド法ではおなじ道を2回以上通らないという条件を満たした解を得ることが難しいです。
そこで頂点1→(頂点1の隣接点)→(頂点1の隣接点)→頂点1の閉路を考えます。頂点1の隣接点ふたつの間の距離はワーシャルフロイド法で求めることができます。経路なのでおなじ道を2回以上通ることはありえません。したがって、頂点1の隣接点をa、bとすると(頂点aから頂点bの距離(ただし頂点1は通らない)) + (頂点1から頂点aの距離) + (頂点1から頂点bの距離)の最小値を求めればよいです。
回答は以下のようになります。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 void solve(int n, long long int r[301][301]) { for(int k = 2; k <= n; k++){ for(int i = 2; i <= n; i++){ for(int j = 2; j <= n; j++){ r[i][j] = min(r[i][j], r[i][k] + r[k][j]); } } } return; } int main() { int n, m; cin >> n >> m; long long int road[301][301]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ road[i][j] = (long long int)mod * 1000; } } for(int i = 0; i < m; i++){ int u, v, l; cin >> u >> v >> l; road[u][v] = l; if(u != 1) road[v][u] = l; } long long int ans = (long long int)mod * 1000; solve(n, road); for(int i = 2; i <= n; i++){ if(road[1][i] == 0) continue; for(int j = i + 1; j <= n; j++){ if(road[1][j] == 0) continue; ans = min(ans, road[1][i] + road[i][j] + road[1][j]); } } if(ans == (long long int)mod * 1000) cout << -1 << endl; else cout << ans << endl; return 0; }
ansとかroadの初期値をmod * 1000にしているのはmod以上の解がありそうだと思ったからです。
uが1のときはroad[v][u]の値を変更しないようにしているのは、vから1への道はないものとすることで1を通らない経路を見つけるためです。これは一回ダイクストラ法を使おうとしたときの名残です。それぞれの頂点に対してダイクストラ法を実行しようと思ったらTLEしたので、ワーシャルフロイド法を使うことにしました。ワーシャルフロイド法ならこんなことをしなくても大丈夫です。
ABC 035 D
今回はこの問題です。
n箇所の町をつなぐ道がm本あります。それぞれの道について、町aから町bへc分をかけて移動することができます(反対方向には移動できません)。またそれぞれの町について、1分滞在するごとにお金をA[i]だけ手に入れられます。高橋君はトレジャーハントに出かけることにしました。高橋君は時刻0のとき町1を出発し、T分後に町1に帰ってこないといけません。このとき、高橋君が得ることのできるお金の最大値を求めなさい、という問題です。
町1を出発→町i(2<=i<=n)に到着、滞在→町1に帰る、という場合のみ考えればいいです。寄り道してても得られるお金は最大値になりえません。もっとお金が得られる町に寄り道するというのなら、最初からその町に向かえばいいじゃんという話です。
そこで、それぞれの町について町1からその町へ向かうのにかかる最短時間と、その町から町1へ帰るのにかかる最短時間を求めます。余った時間はすべてその町で滞在するものとします。これで得られるお金がわかるので、その最大値を求めればいいです。
行き道と帰り道が異なるので、別々にダイクストラ法で最短距離を求めます。帰り道を求めるとき、それぞれの町から町1の通路を求めると、ダイクストラ法をn回実行することになるので時間がかかり過ぎてしまいます。そこで、入力された通路についてaとb、つまり出発点と到着点を入れ替えたものも記憶しておきます。すべての道を逆向きにしておけば、町1からそれぞれの道を求めればそれが帰り道になります。
回答はこんな感じです。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int main() { long long int n, m, t; cin >> n >> m >> t; long long int money[100001]; for(int i = 1; i <= n; i++){ cin >> money[i]; } vector<vector<pair<long long int, long long int> > > ikiroad(100001), kaeriroad(100001); for(int i = 0; i < m; i++){ long long int a, b, c; cin >> a >> b >> c; ikiroad[a].push_back(make_pair(b, c)); kaeriroad[b].push_back(make_pair(a, c)); } long long int iki[100001]; long long int kaeri[100001]; for(int i = 1; i <= n; i++){ iki[i] = mod; kaeri[i] = mod; } iki[1] = 0; kaeri[1] = 0; priority_queue<pair<long long int, long long int> > qu; qu.push(make_pair((long long int)0, 1)); while(!qu.empty()){ long long int nowplace = (qu.top()).second; long long int nowtime = (qu.top()).first; qu.pop(); if(iki[nowplace] < -nowtime) continue; iki[nowplace] = -nowtime; // cout << nowplace << " " << nowtime << endl; for(int i = 0; i < ikiroad[nowplace].size(); i++){ long long int nextplace = ikiroad[nowplace][i].first; long long int cost = ikiroad[nowplace][i].second; qu.push(make_pair(nowtime - cost, nextplace)); } } qu.push(make_pair((long long int)0, 1)); while(!qu.empty()){ long long int nowplace = (qu.top()).second; long long int nowtime = (qu.top()).first; qu.pop(); if(kaeri[nowplace] < -nowtime) continue; kaeri[nowplace] = -nowtime; // cout << nowplace << " " << nowtime << endl; for(int i = 0; i < kaeriroad[nowplace].size(); i++){ long long int nextplace = kaeriroad[nowplace][i].first; long long int cost = kaeriroad[nowplace][i].second; qu.push(make_pair(nowtime - cost, nextplace)); } } long long int ans = money[1] * t; for(int i = 2; i <= n; i++){ ans = max(ans, money[i] * max((long long int)0, t - iki[i] - kaeri[i])); } cout << ans << endl; return 0; }
ダイクストラ二回書いたのは頭悪いですね。汚いコードだ。
ちなみにACするまでこんな感じでした。
うーんこの。
ARC 060に参加しました
爆死しました。C問題部分点(しかも解いたのかなり遅い)のみでした。
しかもコンテスト終了後10分後にこの問題がACしたのでとてもつらい。メモっておきます。
数字が書かれたn枚のカードがあります。このうち1枚以上使って、平均がaになるようなカードの選び方は何通りあるでしょう。同じカードを複数回選んではいけません、という問題です。
何がつらかったというと、
- カードが最大50枚なので、全部で最大2^50通りあり全通り試していたら間に合わない
- DPを使いたかったが、平均を出すためには和と枚数の情報が必要
いろいろ悩んだ結果、メモ化再帰で解くことにしました。回答はこんな感じです。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 long long int n, a; int x[51]; long long int num[60][60][2510]; long long int solve(int restsum, int restcardnum, int selectcardnum) { if(restcardnum == 0 && restsum == 0){ num[selectcardnum][restcardnum][restsum] = 1; return 1; } if(num[selectcardnum][restcardnum][restsum] != -1) return num[selectcardnum][restcardnum][restsum]; long long int result = 0; for(int i = selectcardnum; i <= n; i++){ if(restcardnum > 0 && restsum >= x[i]) result += solve(restsum - x[i], restcardnum - 1, i + 1); } num[selectcardnum][restcardnum][restsum] = result; // cout << restsum << " " << restcardnum << " " << selectcardnum << " " << result << endl; return result; } int main() { cin >> n >> a; long long int xsum = 0; for(int i = 1; i <= n; i++){ cin >> x[i]; xsum += x[i]; } for(int i = 0; i < 51; i++){ for(int j = 0; j < 51; j++){ for(int k = 0; k < 2501; k++){ num[i][j][k] = -1; } } } long long int ans = 0; long long int nownum = a; long long int nowcardnum = 1; while(nowcardnum <= n && nownum <= xsum){ ans += solve(nownum, nowcardnum, 1); nownum += a; nowcardnum++; } cout << ans << endl; return 0; }
num[i][j][k]は、i枚目またはi枚目以降を使用してj枚使って和がkになる組み合わせの数になります(名前は適当に決めましたわかりにくくてよくない)。
まず枚数とその和を決定しておきます。枚数をpとしたとき、和がa * pとなるようにすれば平均がaになります。
これを引数として、solve関数を使って枚数とカードの和の条件を満たす組み合わせの数を求めます。
solve関数は、selectcardnum枚目またはそれ以降を使用して、restcardnum枚で和がrestsumになるような組み合わせの数を返します。numを更新しながら再帰で答えを求めていきます。
3次元配列のDPはなかなか難しいなあ。
レートも落ちてしまったのでしょんぼり。次回はわからなくてもとりあえず部分点をとりにがんばります。
AGC 001 C
今回はこの問題です。
n頂点からなる木があります。直径がK以下の木にするために削る必要のある頂点数の最小値を求めてください、という問題です。
解説を見て解きました。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 vector<vector<int> > road(2001); int n, k; int solve_even() { int ans = 2000; for(int i = 1; i <= n; i++){ vector<int> depth(n + 1, -1); depth[i] = 0; queue<int> qu; qu.push(i); int nowans = 1; while(!qu.empty()){ int now = qu.front(); qu.pop(); if(depth[now] >= k / 2) continue; for(int j = 0; j < road[now].size(); j++){ int next = road[now][j]; if(depth[next] == -1){ depth[next] = depth[now] + 1; qu.push(next); nowans++; } } } ans = min(ans, n - nowans); } return ans; } int solve_odd() { int ans = 2000; for(int i = 1; i <= n; i++){ for(int j = 0; j < road[i].size(); j++){ vector<int> depth(n + 1, -1); depth[i] = 0; depth[road[i][j]] = 0; queue<int> qu; qu.push(i); qu.push(road[i][j]); int nowans = 2; while(!qu.empty()){ int now = qu.front(); qu.pop(); if(depth[now] >= (k - 1) / 2) continue; for(int k = 0; k < road[now].size(); k++){ int next = road[now][k]; if(depth[next] == -1){ depth[next] = depth[now] + 1; qu.push(next); nowans++; } } } ans = min(ans, n - nowans); } } return ans; } int main() { cin >> n >> k; for(int i = 0; i < n - 1; i++){ int a, b; cin >> a >> b; road[a].push_back(b); road[b].push_back(a); } if(k % 2 == 0) cout << solve_even() << endl; else cout << solve_odd() << endl; return 0; }
kが偶数の時はどの他の頂点との距離もk/2以下になるような頂点が存在すればよく、kが奇数の時はどの他の頂点との距離も(k-1)/2以下になるような辺が存在すれば良いので、すべての頂点or辺について条件を満たす頂点の数を求め、そのうち最も大きいものを選ぶようにすればいいです。
ABC 012 D
本日最後の問題はこれです。
n地点とm本のバスの情報が与えられます。バスはa地点とb地点を時間tかけて移動します。バスはそれぞれその区間を往復し、行きも帰りも同じ時間かかり、好きな時間に乗ることができる(=バス同士ののりつぎの時間は考えなくてよい)とします。i地点を出発点として、出発点以外の場所へ移動するのにかかる最大の時間をT(i)としたとき、min(T(i))を求めなさい、という問題です。ちょっと問題文がややこしかった。
nも300と多くないのでそれぞれの地点についてダイクストラ法でT(i)を求め、その最小値を答えとしました。
解答はこんな感じです。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int n; int conection[301][301] = {}; int dijkstra(int i) { priority_queue<pair<int, int> > qu; vector<bool> ischecked(n + 1, false); qu.push(make_pair(0, i)); int checkedplacenum = 1; // cout << i << endl; while(!qu.empty()){ int nowtime = (qu.top()).first; int nowplace = (qu.top()).second; // cout << -nowtime << " " << nowplace << endl; qu.pop(); if(ischecked[nowplace]) continue; ischecked[nowplace] = true; checkedplacenum++; if(checkedplacenum == n + 1) return -nowtime; for(int j = 1; j <= n; j++){ if(!ischecked[j] && conection[nowplace][j] != 0){ qu.push(make_pair(nowtime + conection[nowplace][j], j)); } } } return mod; } int main() { int m; cin >> n >> m; for(int i = 0; i < m; i++){ int a, b, t; cin >> a >> b >> t; conection[a][b] = -t; conection[b][a] = -t; } int ans = mod; for(int i = 1; i <= n; i++){ ans = min(ans, dijkstra(i)); } cout << ans << endl; }
接続行列でtを-tにしているのは、ダイクストラ法で扱いやすくするためです。tの最小値がキューのトップに出てきてほしいのですが、優先度つきキューでは最大値がトップに出てきてしまうのでこうしました。すべての地点に対してチェックが完了した時がT(i)となります。あとはmain関数内で結果を比較すればいいだけです。
