復習埋め

2012年が全部AOJに上がっていたので（早かった）埋めました。

予選２

やっぱりめんどくさい

#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連発してコピペに走った
でもよく考えたら改行忘れてただけかもｗ

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