JOI予選2011
切り捨てで 0点。 さすがに不参加でしょこれ。
一応コード晒します。
1番:やるだけ。
#include<cstdio> #include<algorithm> #include<queue> #include<string> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> P; const int INF = 100000000; int main(){ int a, b, c, d, e, x, y; scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); x = min(a,b); x = min(x,c); y = min(d,e); printf("%d\n",x+y-50); return 0; }
2番:ソート力
#include<cstdio> #include<algorithm> #include<queue> #include<string> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> P; const int INF = 100000000; int main(){ int i, n, a, b, c, d, ans[101], j, jx; P x[100]; scanf("%d",&n); for(i = 0; i < n; i++){ x[i].fi = 0; x[i].se = i;} for(i = 0; i < n*(n-1)/2; i++){ scanf("%d%d%d%d",&a,&b,&c,&d); if(c < d){ x[b-1].fi-=3; } else if(d < c){ x[a-1].fi-=3; } else { x[a-1].fi--; x[b-1].fi--; } } sort(x,x+n); jx = INF; for(i = 0; i < n; i++){ if(jx != x[i].fi){ j = i; jx = x[i].fi;} ans[x[i].se] = j+1; } for(i = 0; i < n; i++){ printf("%d\n",ans[i]); } return 0; }
3番:トッピングをカロリーでソートして貪欲に・・・
#include<cstdio> #include<algorithm> #include<queue> #include<string> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> P; const int INF = 100000000; int main(){ int i, n, a, b, c, d[100], x, y, ma; scanf("%d%d%d%d",&n,&a,&b,&c); x = a; y = c; ma = y/x; for(i = 0; i < n; i++){ scanf("%d",&d[i]); } sort(d,d+n); for(i = n-1; i >= 0; i--){ x += b; y += d[i]; ma = max(ma,y/x); } printf("%d\n",ma); return 0; }
4番:2つ前までの状態を記録するDP
#include<cstdio> #include<algorithm> #include<queue> #include<string> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> P; const int INF = 100000000, mod = 10000; int s[101], dp[101][4][4]; int main(){ int i, j, h, l, n, k, a, b; scanf("%d%d",&n,&k); for(i = 0; i < k; i++){ scanf("%d%d",&a,&b); s[a] = b; } dp[0][0][0] = 1; for(i = 1; i <= n; i++){ if(s[i]){ for(j = 0; j <= 3; j++){ for(h = 0; h <= 3; h++){ dp[i][j][s[i]] += dp[i-1][h][j]; dp[i][j][s[i]] %= mod; } } dp[i][s[i]][s[i]] -= dp[i-1][s[i]][s[i]]; dp[i][s[i]][s[i]] %= mod; } else { for(l = 1; l <= 3; l++){ for(j = 0; j <= 3; j++){ for(h = 0; h <= 3; h++){ dp[i][j][l] += dp[i-1][h][j]; dp[i][j][l] %= mod; } } dp[i][l][l] += mod - dp[i-1][l][l]; dp[i][l][l] %= mod; } } } a = 0; for(h = 0; h <= 3; h++){ for(j = 0; j <= 3; j++){ a += dp[n][h][j]; a %= mod; } } printf("%d\n",a); return 0; }
5番:BFS (DFSでもいけるらしい)
偶数段目と奇数段目で左右逆になってる感じのグラフ。
長方形上に並んでると考えれば良い。
#include<cstdio> #include<algorithm> #include<queue> #include<string> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> P; const int INF = 100000000; const int dx[2][6] = {{0,1,1,1,0,-1},{0,1,0,-1,-1,-1}}; const int dy[2][6] = {{-1,-1,0,1,1,0},{-1,0,1,1,0,-1}}; int m[105][105]; bool used[105][105]; int main(){ int i, j, w, h, a, ans = 0; queue<P> q; P p; scanf("%d%d",&w,&h); for(j = 2; j < h+2; j++){ for(i = 2; i < w+2; i++){ scanf("%d",&a); if(a){ m[i][j] = 2; } else { m[i][j] = 1; } } } for(i = 1; i < w+3; i++){ m[i][1] = 1; q.push(P(i,1)); m[i][h+2] = 1; q.push(P(i,h+2)); } for(i = 2; i < h+2; i++){ m[1][i] = 1; q.push(P(1,i)); m[w+2][i] = 1; q.push(P(w+2,i)); } while(!q.empty()){ p = q.front(); q.pop(); if(used[p.fi][p.se] || !m[p.fi][p.se]) continue; if(m[p.fi][p.se] == 2){ ans++; continue;} used[p.fi][p.se] = true; j = p.se&1; for(i = 0; i < 6; i++){ q.push(P(p.fi+dx[j][i],p.se+dy[j][i])); } } printf("%d\n",ans); return 0; }
1ヶ所、コピペの名残でwとhが逆になってて、縦長のマップでエンバグorz
6番:いろんな要素でDP
実装は重くない?
やり方がマズかったのかな?
There are too many bugs.
今年いっぱいはプロコンやって、年が明けたらHOJ禁して猛精進します。