JOI予選
全完できなかった、しぼんぬ。
いや予選で座圧とbitDP出てきてる時点であきらかに難化してる。
4完+6番の部分点です。たぶんあってるはず。
1
割って引き算するだけ。のはず。
#include <cstdio> int l, a, b, c, d; int max(int a, int b) { return a<b?b:a; } int main() { scanf("%d%d%d%d%d",&l,&a,&b,&c,&d); int need = max((a+c-1)/c,(b+d-1)/d); printf("%d\n",l-need); }
2
かぶってなかったら足すだけ。のはず。
#include <cstdio> #include <cstring> int n; int num[200][3]; int result[200]; int main() { scanf("%d",&n); for (int i=0; i<n; i++) for (int j=0; j<3; j++) scanf("%d",&num[i][j]); memset(result, 0, sizeof(result)); for (int i=0; i<n; i++) { for (int j=0; j<3; j++) { int flag=1; for (int k=0; k<n&&flag; k++) { if (k==i) continue; if (num[i][j]==num[k][j]) { flag=0; } } if (flag) result[i]+=num[i][j]; } } for (int i=0; i<n; i++) { printf("%d\n",result[i]); } }
3
とりあえずDFSで探してた。
#include <cstdio> #include <iostream> using namespace std; int n; string ne, ol; bool dfs(int pos, int np, int r) { if (np==ne.size()) return true; if (r==-1) { for (int i=pos+1; i<ol.size(); i++) { if (ne[np]==ol[i]) { if (dfs(i, np+1, i-pos)) return true; } } return false; } else { if (pos+r>=ol.size()||ol[pos+r]!=ne[np]) return false; else return dfs(pos+r, np+1, r); } } int main() { scanf("%d",&n); cin>>ne; int res=0; for (int i=0; i<n; i++) { cin>>ol; int flag=0; for (int j=0; j<ol.size(); j++) { if (ne[0]==ol[j]) if (dfs(j,1,-1)) { flag=1; break; } } if (flag) res++; } printf("%d\n",res); }
4
dp[何日目][服の種類]
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; int d, n, t[200], a[200], b[200], c[200]; int dp[200][200], cx[200][200]; 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=0; i<n; i++) for (int j=0; j<n; j++) { cx[i][j]=abs(c[i]-c[j]); } for (int i=0; i<n; i++) { if (t[0]<a[i]||b[i]<t[0]) dp[0][i]=-1; } for (int i=1; i<d; i++) { for (int j=0; j<n; j++) { if (t[i]<a[j]||b[j]<t[i]) { dp[i][j]=-1; continue; } for (int k=0; k<n; k++) { if (dp[i-1][k]==-1) continue; dp[i][j]=max(dp[i][j],dp[i-1][k]+cx[j][k]); } } } int res=0; for (int i=0; i<n; i++) res=max(res, dp[d-1][i]); printf("%d\n",res); }
5
座圧必要な時点でしぼんぬ。勉強しなきゃなー。
6
幅優先、部分点解。
#include <cstdio> #include <iostream> #include <map> #include <queue> #include <set> #include <algorithm> using namespace std; typedef pair<int, int> P; int h, w, k; string f[50]; int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; int main() { scanf("%d%d%d",&h,&w,&k); for (int i=0; i<h; i++) cin>>f[i]; queue<pair<pair<P, P>, set<P> > > que; que.push(make_pair(make_pair(P(0,0),P(0,0)),set<P>())); int res=0; while (!que.empty()) { int x=que.front().first.first.first; int y=que.front().first.first.second; int lim=que.front().first.second.first; int cnt=que.front().first.second.second; set<P> s=que.front().second; que.pop(); if (x==h-1&&y==w-1) res=max(res, cnt); for (int i=0; i<4; i++) { if (lim==k&&i<2) continue; int nx=x+dx[i], ny=y+dy[i]; if (nx<0||nx>=h||ny<0||ny>=w) continue; if (f[nx][ny]=='#') continue; if (f[nx][ny]=='.'||s.find(P(nx,ny))!=s.end()) { if (i>=2) que.push(make_pair(make_pair(P(nx,ny),P(lim,cnt)),s)); else que.push(make_pair(make_pair(P(nx,ny),P(lim+1,cnt)),s)); } else { set<P> ss=s; ss.insert(P(nx,ny)); int val=f[nx][ny]-'0'; if (i>=2) que.push(make_pair(make_pair(P(nx,ny),P(lim,cnt+val)),ss)); else que.push(make_pair(make_pair(P(nx,ny),P(lim+1,cnt+val)),ss)); } } } printf("%d\n",res); }
実行結果
- 1-1
13
- 1-2
5
- 1-3
27
- 1-4
3
- 1-5
9
- 2-1
170
173
258
71
72
257
73
88
166
153
- 2-2
0
155
112
27
164
49
0
16
0
15
67
33
95
91
80
0
38
27
81
46
45
143
0
55
101
98
119
137
87
103
20
196
76
162
83
244
113
100
116
47
136
75
36
142
34
160
69
141
87
66
- 2-3
73
66
160
0
45
38
69
121
47
0
5
22
135
24
87
10
0
0
143
110
43
66
0
137
55
1
20
0
0
84
62
232
64
67
2
0
0
16
90
0
86
0
79
0
67
77
43
0
93
56
0
0
0
52
101
30
0
31
0
32
0
0
95
98
56
23
136
137
0
0
4
165
0
23
82
97
85
80
76
65
89
0
78
107
42
62
0
41
84
14
49
27
46
5
134
49
0
180
0
74
- 2-4
91
0
43
33
55
0
189
0
97
73
49
89
0
0
31
27
0
0
0
28
80
0
55
0
0
8
37
0
31
98
26
0
71
0
92
0
46
7
0
156
90
45
28
0
0
0
184
60
39
47
0
0
0
41
0
100
179
162
42
0
216
1
61
0
78
96
47
0
32
66
92
0
34
80
0
0
61
0
64
0
9
0
0
0
19
165
10
0
41
0
12
139
0
0
63
0
0
88
99
46
57
29
0
0
0
57
156
13
41
36
0
0
0
48
45
83
0
54
0
0
0
65
0
8
0
73
43
123
0
95
0
164
0
0
0
44
81
28
117
0
68
47
86
0
34
0
108
0
53
39
- 2-5
0
0
88
0
0
0
0
83
0
0
0
8
0
82
0
0
15
0
0
0
0
0
59
0
0
9
0
0
0
0
0
63
0
99
0
0
11
45
0
0
7
0
0
22
48
16
0
0
0
0
13
0
0
0
43
33
0
56
0
64
0
54
0
0
36
4
8
97
0
0
65
0
52
0
95
0
0
0
57
89
0
23
0
0
103
121
19
0
0
0
42
25
0
0
37
0
27
0
0
0
7
100
0
0
0
0
0
0
0
0
19
0
34
60
0
0
0
30
1
0
40
81
0
55
0
28
53
0
0
20
0
0
0
0
0
0
0
54
0
0
0
0
24
0
0
0
0
19
0
0
0
93
0
0
0
0
42
0
85
25
28
52
0
0
0
0
6
0
0
0
61
0
0
181
0
0
0
0
0
0
0
5
0
2
3
0
0
0
0
170
25
48
95
0
53
0
78
0
39
0
- 3-1
7
- 3-2
11
- 3-3
63
- 3-4
42
- 3-5
47
- 4-1
235
- 4-2
409
- 4-3
18586
- 4-4
19556
- 4-5
19148
- 6-1
21
感想
実行結果さらしてみたけどヒヤヒヤもん(・_・;)
全部あっててくれ〜(;_;)