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);
}

実行結果

170
173
258
71
72
257
73
88
166
153

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

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

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

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