情報オリンピック予選 2012-2013
4完 + 部分点4点 = 84
だと思う。
1
#include <cstdio> #include <algorithm> using namespace std; int main(){ int l, a, b, c, d; scanf("%d %d %d %d %d", &l, &a, &b, &c, &d); printf("%d\n", l - max((a+c-1)/c, (b+d-1)/d)); return 0; }
2
#include <cstdio> #include <algorithm> using namespace std; int main(){ int n; scanf("%d", &n); int a[n][3]; for(int i = 0; i < n; i++){ scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]); } int score[n]; fill(score, score + n, 0); for(int k = 0; k < 3; k++){ for(int i = 0; i < n; i++){ bool f = true; for(int j = 0; j < n; j++){ if(i==j)continue; if(a[i][k] == a[j][k]) f = false; } if(f){ score[i] += a[i][k]; } } } for(int i = 0; i < n; i++) printf("%d\n", score[i]); return 0; }
3
#include <iostream> #include <algorithm> using namespace std; int main(){ int n; string name; cin >> n; cin >> name; int ans = 0; for(int k = 0; k < n; k++){ string old; cin >> old; for(int i = 0; i < old.size(); i++){ if(old[i] != name[0]) continue; for(int j = i+1; j < old.size(); j++){ if(old[j] != name[1]) continue; int d = j - i; bool f = true; for(int p = 2; p < name.size(); p++){ if(i + d * p >= old.size()){ f = false; break; } if(old[i + d * p] != name[p]){ f = false; break; } } if(f){ ans++; goto fin; } } } fin: ; } cout << ans << endl; return 0; }
4
2通りの方法でコード書いてあってるか確認して提出しました
メモ化再帰
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 200; const int MAX_D = 200; int D, N; int T[MAX_D]; int A[MAX_N], B[MAX_N], C[MAX_N]; int memo[MAX_D][MAX_N][MAX_N]; //d日目、前日の服q 今日の服p int solve(int d, int q, int p){ int m; if(d == 0) m = 0; else m = abs(C[q] - C[p]); if(d == D-1) return m; if(memo[d][q][p] != -1) return memo[d][q][p]; int ret = 0; for(int i = 0; i < N; i++){ if(A[i] <= T[d+1] && T[d+1] <= B[i]){ ret = max(ret, solve(d+1, p, i)); } } return memo[d][q][p] = ret + m; } int main(){ scanf("%d %d", &D, &N); for(int i = 0; i < MAX_D; i++) for(int j = 0; j < MAX_N; j++) for(int k = 0; k < MAX_N; k++) memo[i][j][k] = -1; for(int i = 0; i < D; i++) scanf("%d", &T[i]); for(int j = 0; j < N; j++){ scanf("%d %d %d", &A[j], &B[j], &C[j]); } int ans = 0; for(int i = 0; i < N; i++){ if(A[i] <= T[0] && T[0] <= B[i]){ ans = max(ans, solve(0, 0, i)); } } printf("%d\n", ans); return 0; }
#include <cstdio> #include <algorithm> using namespace std; int D, N; int T[201]; int A[201], B[201], C[201]; int dp[201][201]; int main(){ scanf("%d %d", &D, &N); for(int i = 0; i < D; i++) scanf("%d", &T[i]); for(int i = 0; i < N; i++) scanf("%d %d %d", &A[i], &B[i], &C[i]); for(int i = 1; i < D; i++){ for(int j = 0; j < N; j++){ if(!(A[j] <= T[i-1] && T[i-1] <= B[j]))continue; for(int k = 0; k < N; k++){ if(!(A[k] <= T[i] && T[i] <= B[k]))continue; dp[i][k] = max(dp[i][k], dp[i-1][j] + abs(C[j] - C[k])); } } } int ans = 0; for(int i = 0; i < N; i++){ ans = max(ans, dp[D-1][i]); } printf("%d\n", ans); return 0; }
5
部分点解法
#include <cstdio> #include <algorithm> using namespace std; const int MAX = 101; int a[MAX][MAX][MAX]; int main(){ int n, k; scanf("%d %d", &n, &k); for(int i = 0; i < n; i++){ int x1, y1, d1, x2, y2, d2; scanf("%d %d %d %d %d %d", &x1, &y1, &d1, &x2, &y2, &d2); for(int x = x1; x < x2; x++) for(int y = y1; y < y2; y++) for(int d = d1; d < d2; d++) a[x][y][d]++; } int ans = 0; for(int x = 0; x < MAX; x++) for(int y = 0; y < MAX; y++) for(int d = 0; d < MAX; d++) if(a[x][y][d] >= k) ans++; printf("%d\n",ans); return 0; }