復習埋め
2012年が全部AOJに上がっていたので(早かった)埋めました。
予選2
やっぱりめんどくさい
#include <cstdio> #include <map> #include <algorithm> #include <functional> using namespace std; typedef pair<int, int> P; P po[100], res[100]; int main() { int n; scanf("%d",&n); for (int i=0; i<n; i++) { po[i].second=i; po[i].first=0; } for (int i=0; i<n*(n-1)/2; i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); if (c>d) { po[a-1].first+=3; } else if (c<d) { po[b-1].first+=3; } else { po[a-1].first++; po[b-1].first++; } } sort(po, po+n); int pos=1, cnt=0, bef=0; for (int i=n-1; i>=0; i--) { if (bef!=po[i].first) { pos+=cnt; res[i].first=po[i].second; res[i].second=pos; cnt=1; bef=po[i].first; } else { res[i].first=po[i].second; res[i].second=pos; cnt++; } } sort(res,res+n); for (int i=0; i<n; i++) printf("%d\n",res[i].second); }
予選3
ここらへんは書くだけ
#include <cstdio> #include <cmath> #include <algorithm> using namespace std; int d[100]; int main() { int n,a,b,c; scanf("%d%d%d%d",&n,&a,&b,&c); for (int i=0; i<n; i++) scanf("%d",&d[i]); sort(d, d+n); int sum=c, res=0; for (int i=n-1; i>=0; i--) { sum+=d[i]; res=max(res, (int)floor(sum/(a+(n-i)*b))); } printf("%d\n",res); }
本選1
Run-Length圧縮で実装しようとおもったけどWA連発してコピペに走った
でもよく考えたら改行忘れてただけかもw
本選2
1の流れでめんどくさかったのでコピペしました
本選3
やろうとしてまた間違えた・・・
ナップザックって一次元配列なんですね、、、いや違うか。。。
なんで間違えてたんだろう???
謎
kagamizさんのカンニングした
#include <cstdio> #include <algorithm> using namespace std; int a[3000], b[3000]; int dp[5000]; int main() { int n, t, s; scanf("%d%d%d",&n,&t,&s); for (int i=0; i<n; i++) scanf("%d%d",&a[i],&b[i]); int res=0; for (int i=0; i<n; i++) { for (int j=t-b[i]; j>=0; j--) { if (j<s&&s<j+b[i]) continue; dp[j+b[i]]=max(dp[j+b[i]], dp[j]+a[i]); res=max(res,dp[j+b[i]]); } } printf("%d\n",res); }
予選4
結局imos法を理解してなかったので最大値の伝搬をやった
#include <cstdio> #include <algorithm> using namespace std; int tri[5002][5002]; int main() { int n,m; scanf("%d%d",&n,&m); for (int i=0; i<m; i++) { int x, y, r; scanf("%d%d%d",&x,&y,&r); tri[x-1][y-1]=max(tri[x-1][y-1],r+1); } for (int i=1; i<n; i++) { tri[i][0]=max(tri[i-1][0]-1, tri[i][0]); tri[i][i]=max(tri[i-1][i-1]-1,tri[i][i]); for (int j=1; j<i; j++) { tri[i][j]=max(tri[i][j], max(tri[i-1][j-1],tri[i-1][j])-1); } } int res=0; for (int i=0; i<n; i++) { for (int j=0; j<=i; j++) { if (tri[i][j]!=0) res++; } } printf("%d\n",res); }
あしたPastaやります。
LCA勉強して本選5も理解しないとな〜