05.25.2013 (Sat)SRM 579 Div1 
ものすごく眠い中参加しました.
結果 : o-- +0/-0 143.42 pts 1494 → 1508 (+14) !!黄色!!
250 UndoHistory
問題文 -> コチラ
問題概要 :
複雑な仕様のエディタがある.
タイプ+クリック数の最小値を求めよ.
解法 :
問題文で記述しているとおりに実装するだけ. 最初にbuffer に"" を詰めておけば怖いことはない.
"複雑な仕様" を微妙に読み違えていて亀コーディングしましたが, Systest は通ったしよかったよかった...
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <deque> using namespace std; typedef long long lint; class UndoHistory { public: int minPresses(vector <string> l) { int res = l.size(); vector<string> buffers; buffers.push_back(""); string prevstr = ""; for (int i = 0; i < l.size(); i++){ int idx = -1; for (int j = l[i].size(); (int)l[i].size() - j >= 0; j--){ for (int k = 0; k < buffers.size(); k++){ if (l[i].substr(0, j) == buffers[k]){ idx = j; } if (~idx) break; } if (~idx) break; } int cost1 = (l[i].size() >= prevstr.size() && l[i].substr(0, prevstr.size()) == prevstr) ? l[i].size() - prevstr.size() : 9999999; int cost2 = l[i].size() - idx + 2; if (cost1 < cost2){ res += cost1; for (int j = prevstr.size(); j < l[i].size(); j++) buffers.push_back(l[i].substr(0, j + 1)); } else { res += cost2; for (int j = idx; j < l[i].size(); j++){ buffers.push_back(l[i].substr(0, j + 1)); } } prevstr = l[i]; } return (res); } };
450 TravellingPurchasingMan
問題文 -> コチラ
問題概要 :
N 個のお店があって, 0 から N - 1 までの番号がついている. あなたは0 から M - 1 番目までのお店に興味がある.
また, いくつかの店間には重み付きの無向辺がはられている.
0 ≦ x ≦ M - 1 を満たすx について, 時刻A[x] から B[x] の間にC[x] 時間滞在すればあなたはその店で満足できる.
店 N - 1 から出発するとき, 満足できる店の最大値を求めよ.
1 ≦ N ≦ 50, 1 ≦ M ≦ min(N, 16)
解法 :
M 頂点だけのグラフに縮約して, Warshall-Floyd + bitDP で十分.
しかし, 癖で店番号をデクリメントしていてサンプルが通らなかった... ザンネン
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <deque> using namespace std; typedef long long lint; int st[64], en[64], stay[64]; struct Edge { int to, cost; Edge(int to, int cost) : to(to), cost(cost) {} }; int mask; vector<Edge> G[64]; int dp[64][1 << 16]; class TravellingPurchasingMan { public: int maxStores(int N, vector <string> iStores, vector <string> rds) { int res = 0; for (int i = 0; i < iStores.size(); i++){ sscanf(iStores[i].c_str(), "%d %d %d", st + i, en + i, stay + i); } int cst[64][64]; for (int i = 0; i < 64; i++){ for (int j = 0; j < 64; j++) cst[i][j] = 1000000000; cst[i][i] = 0; } for (int i = 0; i < rds.size(); i++){ int a, b, c; sscanf(rds[i].c_str(), "%d %d %d", &a, &b, &c); cst[a][b] = c; cst[b][a] = c; } for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cst[i][j] = min(cst[i][j], cst[i][k] + cst[k][j]); for (int i = 0; i < 64; i++) G[i].clear(); for (int i = 0; i < iStores.size(); i++){ for (int j = 0; j < iStores.size(); j++){ if (cst[i][j] != 1000000000) G[i].push_back(Edge(j, cst[i][j])); } } mask = (1 << iStores.size()) - 1; for (int i = 0; i < 64; i++) for (int j = 0; j < 1 << 16; j++) dp[i][j] = 1000000000; for (int i = 0; i < iStores.size(); i++){ if (cst[N - 1][i] <= en[i]){ dp[i][1 << i] = max(st[i], cst[N - 1][i]) + stay[i]; } } for (int j = 0; j < 1 << (iStores.size()); j++){ for (int i = 0; i < iStores.size(); i++){ if (dp[i][j] != 1000000000){ res = max(res, __builtin_popcount(j)); for (int k = 0; k < G[i].size(); k++){ if (dp[i][j] + G[i][k].cost <= en[G[i][k].to]){ dp[G[i][k].to][j | ((1ll << G[i][k].to) & mask)] = min(dp[G[i][k].to][j | ((1ll << G[i][k].to) & mask)], max(dp[i][j] + G[i][k].cost, st[G[i][k].to]) + stay[G[i][k].to]); } } } } } return (res); } };
コメントを書く