我ながらうまい当て字するもんだね↑

色々とやばいｗ

AOJ 0550

結局自分で解いたのかな？(*_*;

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
int n, dp[2][5050][2],t[10000];
int main() {
    scanf("%d",&n);
    for (int i=0; i<n-1; i++) {
        scanf("%d",&t[i]);
    }
    for (int i=0; i<2; i++) for (int j=0; j<5050; j++) for (int k=0; k<2; k++) dp[i][j][k]=INT_MAX/2;
    dp[0][0][0]=0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<=min(5009,i); j++) {
            dp[(i+1)&1][j+1][0]=min(dp[i&1][j][0], dp[i&1][j][1]+t[i]);
            dp[(i+1)&1][j][1]=min(dp[i&1][j][0]+t[i], dp[i&1][j][1]);
        }
        dp[i&1][0][0]=INT_MAX/2;
    }
    printf("%d\n",dp[n%2][n/2][0]);
}

PKU 2576

えーやばい

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n, pic[100];
bool dp[111][55001];
int main() {
    scanf("%d",&n);
    int sum=0;
    for (int i=0; i<n; i++) {
        scanf("%d",&pic[i]);
        sum+=pic[i];
    }
    dp[0][0]=true;
    for (int i=0; i<n; i++) {
        for (int u=n-1; u>=0; u--) {
            for (int j=0; j<=sum; j++) if (dp[u][j]) dp[u+1][j+pic[i]]=true;
        }
    }
    int r1=0, r2=sum;
    for (int i=0; i<sum; i++) {
        if (!dp[n/2][i]) continue;
        if (abs(r2-r1)>abs(sum-2*i)) {
            r1=i;
            r2=sum-i;
        }
    }
    if (r1>r2) swap(r1,r2);
    printf("%d %d\n",r1,r2);
}

PKU 2606

割り算やっぱだめなんすね

#include <cstdio>
#include <cmath>
#include <algorithm>
#define EPS 1e-10
using namespace std;
int n, x[200], y[200];
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) scanf("%d%d",&x[i],&y[i]);
    int res=0;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            int tit1=y[j]-y[i], tit2=x[j]-x[i];
            int cnt=0;
            for (int k=0; k<n; k++) {
                if ((y[k]-y[i])*tit2==(x[k]-x[i])*tit1) cnt++;
            }
            res=max(res, cnt);
        }
    }
    printf("%d\n",res);
}

Codeforces#130

A

最後のtmpを入れ忘れて色々やっちまった

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
string str;
vector<string> ans;
int main() {
    cin>>str;
    string tmp="";
    for (int i=0; i<str.length(); i++) {
        if (str[i]=='W') {
            if (i+1<str.length()&&str[i+1]=='U'&&i+2<str.length()&&str[i+2]=='B') {
                i+=2;
                if (tmp.length()!=0) ans.push_back(tmp);
                tmp="";
            } else {
                tmp+=str[i];
            }
        } else {
            tmp+=str[i];
        }
    }
    if (tmp.length()!=0) ans.push_back(tmp);
    if (ans.size()==0) cout<<endl;
    else {
        cout<<ans[0];
        for (int i=1; i<ans.size(); i++) {
            cout<<" "<<ans[i];
        }
        cout<<endl;
    }
}

B

全域木作ればいけるんじゃねとか思ったけどやっぱり嘘解法だった。
本当の解法はまだ見てない

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
struct unionfind {
    int par[60], rank[60];
    unionfind(int n) {
        for (int i=0; i<n; i++) {
            par[i]=i;
            rank[i]=0;
        }
    }
    int find(int x) {
        if (x==par[x]) return x;
        return par[x]=find(par[x]);
    }
    void unite(int x, int y) {
        x=find(x); y=find(y);
        if (x==y) return;
        if (rank[x]<rank[y]) par[x]=y;
        else {
            par[y]=x;
            if (rank[x]==rank[y]) rank[x]++;
        }
    }
    bool same(int x, int y) {
        return find(x)==find(y);
    }
};
struct edge { int s, e; };
int n;
string card[52];
vector<edge> es;
int d[4]={-1,-3,1,3};
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) cin>>card[i];
    for (int i=0; i<n; i++) {
        for (int j=0; j<4; j++) {
            int nx=i+d[j];
            if (nx>=0&&nx<n&&(card[i][0]==card[nx][0]||card[i][1]==card[nx][1])) {
                es.push_back((edge){i,nx});
            }
        }
    }
    unionfind uf(n);
    for (int i=0; i<es.size(); i++) {
        edge e=es[i];
        if (!uf.same(e.s,e.e)) {
            uf.unite(e.s,e.e);
        }
    }
    bool flag=true;
    int r=uf.find(0);
    for (int i=1; i<n; i++) {
        if (r!=uf.find(i)) flag=false;
    }
    if (flag) puts("YES");
    else puts("NO");
}

D

一番簡単だったのでは

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, p[50], a[5], b[5];
int main() {
    cin>>n;
    for (int i=0; i<n; i++) cin>>p[i];
    for (int i=0; i<5; i++) cin>>a[i];
    ll res=0;
    for (int i=0; i<n; i++) {
        res+=p[i];
        while (res>=a[0]) {
            ll use=upper_bound(a, a+5, res)-a-1;
            if (use<0) use=0;
            b[use]+=res/a[use];
            p[i]-=res/a[use]*a[use];
            res%=a[use];
        }
    }
    cout<<b[0];
    for (int i=1; i<5; i++) cout<<" "<<b[i];
    cout<<endl;
    cout<<res<<endl;
}