競技以外についてはこちら
チームに割り当てられた端末のホームディレクトリ以下のsouvenirフォルダに入れたファイルはおみやげとしてメールで送られてくるというシステムでした。 先ほど届いたので提出コードを貼り付けます
A
- solve(n,k,s) = solve(n-1,k-1,s-n) + solve(n-1,k,s) みたいな漸化式のほうが良さそう (DPの練習的には)
- もっと言えば for(int b = 0; b < (1 << n); b++) if(__builtin_popcount(b) == k) { .. } みたいなほうが良さそう (実装の容易さ的には)
#include <bits/stdc++.h> using namespace std; int solve(int n, int k, int s) { if(k == 0 && s == 0) return 1; int res = 0; for(int i = 1; i <= n; i++) { res += solve(i - 1, k - 1, s - i); } return res; } int main() { while(true) { int N, K, S; cin >> N >> K >> S; if(N == 0 && K == 0 && S == 0) break; cout << solve(N, K, S) << endl; } }
B
#include <bits/stdc++.h> using namespace std; #define DEBUG(x) cerr << #x << " = " << x << endl int main() { while(true) { int N, L; cin >> N >> L; if(N == 0 && L == 0) break; vector<int> pos(N); // L=-1, R=1 vector<int> dir(N); for(int i = 0; i < N; i++) { int p; char d; cin >> d >> p; pos[i] = p; dir[i] = (d == 'R') ? 1 : -1; } int last = 0; int lastsecond = 0; int second = 0; int lastPos = (int)1e9; vector<int> live(N, 1); while(true) { second++; vector<int> on(L + 1, 0); for(int i = 0; i < N; i++) { if(live[i]) { pos[i] += dir[i]; on[pos[i]]++; } } for(int i = 0; i < N; i++) { if(live[i]) { if(on[pos[i]] >= 2) { dir[i] *= -1; } } } for(int i = 0; i < N; i++) { if(live[i]) { if(pos[i] == 0 || pos[i] == L) { live[i] = 0; if(second == lastsecond) { if(pos[i] < lastPos) { last = i; lastsecond = second; lastPos = pos[i]; } } else { last = i; lastsecond = second; lastPos = pos[i]; } } } } bool f = false; for(int i = 0; i < N; i++) { if(live[i]) f = true; } if(!f) break; } cout << lastsecond << ' ' << last + 1 << endl; } }
C
- dfs関数の中でbfsしたりしていますが、最初に実装した時は本当にdfsだったんです…
#include <bits/stdc++.h> using namespace std; #define DEBUG(x) cerr << #x << " = " << x << endl const int MAX_N = 50; // x, y int field[2 * (2 * MAX_N) + 1][2 * (2 * MAX_N) + 1]; int X, Y; typedef pair<int, int> P; void dfs(int x, int y) { queue<P> Q; Q.push(P(x, y)); while(!Q.empty()) { P p = Q.front(); Q.pop(); for(int i = 0; i < 4; i++) { int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, 1, 0, -1 }; int nx = p.first + dx[i]; int ny = p.second + dy[i]; if(0 <= nx && nx < X && 0 <= ny && ny < Y && field[nx][ny] == 0) { field[nx][ny] = 1; Q.push(P(nx, ny)); } } } } void show() { #if 0 cerr << '-' << endl; for(int i = Y - 1; i >= 0; i--) { for(int j = 0; j < X; j++) { cerr << field[j][i]; } cerr << '|' << endl; } cerr << '-' << endl; #endif } int main() { while(true) { int N; cin >> N; if(N == 0) break; vector<int> x1(N), y1(N), x2(N), y2(N); vector<int> xs; vector<int> ys; for(int i = 0; i < N; i++) { cin >> x1[i] >> y1[i] >> x2[i] >> y2[i]; xs.push_back(x1[i]); xs.push_back(x2[i]); ys.push_back(y1[i]); ys.push_back(y2[i]); } sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); for(int i = 0; i < N; i++) { x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin(); y1[i] = find(ys.begin(), ys.end(), y1[i]) - ys.begin(); x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin(); y2[i] = find(ys.begin(), ys.end(), y2[i]) - ys.begin(); } memset(field, 0, sizeof(field)); for(int i = 0; i < N; i++) { for(int x = 2 * x1[i]; x <= 2 * x2[i]; x++) { field[x + 1][2 * y1[i] + 1] = 1; field[x + 1][2 * y2[i] + 1] = 1; } for(int y = 2 * y1[i]; y >= 2 * y2[i]; y--) { field[2 * x1[i] + 1][y + 1] = 1; field[2 * x2[i] + 1][y + 1] = 1; } } X = 2 * (int)xs.size() + 1; Y = 2 * (int)ys.size() + 1; show(); int ans = 0; for(int x = 0; x < X; x++) { for(int y = 0; y < Y; y++) { if(field[x][y] == 0) { ans++; field[x][y] = 1; dfs(x, y); show(); } } } cout << ans << endl; } }
E
- 最初は盤面の状態をstringで持っていたのですが、TLEしそうだったのでint64_tにエンコードしました
- ぶっちゃけstringでも通ると思う
#include <bits/stdc++.h> using namespace std; #define DEBUG(x) cerr << #x << " = " << x << endl const int swx[9][2] = { { 1, 8 }, { 2, 0 }, { 3, 1 }, { 4, 2 }, { 5, 3 }, { 6, 4 }, { 7, 5 }, { 8, 6 }, { 0, 7 } }; const int swy[9][2] = { { 6, 3 }, { 7, 4 }, { 8, 5 }, { 0, 6 }, { 1, 7 }, { 2, 8 }, { 3, 0 }, { 4, 1 }, { 5, 2 } }; typedef long long i64; const int INF = (int)1e9; typedef pair<int, i64> P; template <class T, class U> T lexical_cast(const U& from) { T to; stringstream ss; ss << from; ss >> to; return to; } // hidarikara i64 stateChange(i64 S, int i, int j) { i = 8 - i; j = 8 - j; i64 powI = 1LL; i64 powJ = 1LL; for(int x = 0; x < i; x++) powI *= 10LL; for(int x = 0; x < j; x++) powJ *= 10LL; i64 mulI = (S / powI) % 10; i64 mulJ = (S / powJ) % 10; return S - (mulI * powI) + (mulJ * powI) - (mulJ * powJ) + (mulI * powJ); } int main() { while(true) { int costX, costY; cin >> costX >> costY; if(costX == 0 && costY == 0) break; i64 start; i64 goal; string str; str = ""; for(int i = 0; i < 9; i++) { char c; cin >> c; str.push_back(c); } start = lexical_cast<i64>(str); str = ""; for(int i = 0; i < 9; i++) { char c; cin >> c; str.push_back(c); } goal = lexical_cast<i64>(str); map<i64, int> d; priority_queue<P, vector<P>, greater<P> > Q; Q.push(P(0, start)); d[start] = 0; while(!Q.empty()) { P p = Q.top(); Q.pop(); int costNow = p.first; i64 curS = p.second; if(curS == goal) break; if(d.count(curS) && costNow > d[curS]) continue; int zero; str = lexical_cast<string>(curS); if(curS < 100000000LL) zero = 0; else zero = find(begin(str), end(str), '0') - begin(str); i64 s; s = stateChange(curS, zero, swx[zero][0]); if(d.count(s) == 0 || d[s] > costNow + costX) { d[s] = costNow + costX; Q.push(P(d[s], s)); } s = stateChange(curS, zero, swx[zero][1]); if(d.count(s) == 0 || d[s] > costNow + costX) { d[s] = costNow + costX; Q.push(P(d[s], s)); } s = stateChange(curS, zero, swy[zero][0]); if(d.count(s) == 0 || d[s] > costNow + costY) { d[s] = costNow + costY; Q.push(P(d[s], s)); } s = stateChange(curS, zero, swy[zero][1]); if(d.count(s) == 0 || d[s] > costNow + costY) { d[s] = costNow + costY; Q.push(P(d[s], s)); } } cout << d[goal] << endl; } }
