読者です 読者をやめる 読者になる 読者になる

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

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

色々とやばいw

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;
}
広告を非表示にする