夢追い人

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

普天間飛行場みてきた

そして精進

fiber

ただのunion-findですが、union-find木の特性を忘れていて最初WAしていました

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
struct unionfind {
    int par[10000], rank[10000];
    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;
        } else {
            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);
    }
    int cnt(int n) {
        set<int> pars;
        for (int i=0; i<n; i++) {
            int x=find(i);
            pars.insert(x);
        }
        return pars.size();
    }
};
int main() {
    int n, m; scanf("%d%d",&n,&m);
    unionfind uf(n);
    for (int i=0; i<m; i++) {
        int a, b; scanf("%d%d",&a,&b);
        uf.unite(a-1,b-1);
    }
    printf("%d\n",uf.cnt(n)-1);
}

ctpc a

スマホで書いたやつ

#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
int x=max(max(a,b),max(c,d));
if ((x+a+b+c+d)/5>=60) puts("Yes");
else puts("No");
}

ctpc b

座標がどこからどこまでになるのかとか考えるのがめんどくさかった

#include <cstdio>
#include <algorithm>
using namespace std;
int board[50][50];
int w,h,k;
bool isin(int x, int y) {
    return x>=0&&x<w&&y>=0&&y<h;
}
// P(x,y) : xが横,yが縦
int main() {
    scanf("%d%d%d",&w,&h,&k);
    for (int i=0; i<k; i++) {
        int x,y,l; scanf("%d%d%d",&x,&y,&l);
        int r=l;
        while (r<=max(w,h)) {
            bool flag=true;
            for (int j=x-r; j<=x+r; j++) {
                if (isin(j,y-r)) {
                    board[y-r][j]++;
                    flag=false;
                }
                if (isin(j,y+r)) {
                    board[y+r][j]++;
                    flag=false;
                }
            }
            for (int j=y-r+1; j<y+r; j++) {
                if (isin(x-r,j)) {
                    board[j][x-r]++;
                    flag=false;
                }
                if (isin(x+r,j)) {
                    board[j][x+r]++;
                    flag=false;
                }
            }
            if (flag) break;
            r+=l+1;
        }
    }
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            if (board[i][j]%2) putchar('#');
            else putchar('.');
            if (j==w-1) puts("");
        }
    }
}

ctpc c

スマホで書いたコード

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main() {
int n; scanf("%d",&n);
string str; getline(cin,str);
int tw=0,rt=0;
for (int i=0; i<n; i++) {
getline(cin,str);
int len=str.length();
if (1>len||140<len) continue;
if (str[0]=='@') rt++;
else tw++;
}
if (rt+tw==0) {
puts("Tweet:NA Reply:NA");
return 0;
}
int r1=0,r2=0;
if (tw) r1=tw*100/(tw+rt);
if (rt) r2=rt*100/(tw+rt);
printf("Tweet:%d Reply:%d\n",r1,r2);
}

ctpc d

ナップザック問題
毎回dp計算してて最初TLEしてた、普通に逆ですね。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,q;
int w[10000], v[10000];
int dp[10005];
int main() {
    scanf("%d%d",&n,&q);
    for (int i=0; i<n; i++) scanf("%d%d",&w[i],&v[i]);
    for (int i=0; i<=10000; i++) dp[i]=0;
    for (int i=0; i<n; i++) {
        for (int j=10000; j>=w[i]; j--) {
            dp[j]=max(dp[j], dp[j-w[i]]+v[i]);
        }
    }
    for (int ix=0; ix<q; ix++) {
        int x; scanf("%d",&x);
        if (x==0) {
            int a; scanf("%d",&a);
            printf("%d\n",dp[a]);
        } else {
            int a, b, c; scanf("%d%d%d",&a,&b,&c);
            w[a-1]=b;
            v[a-1]=c;
            for (int i=0; i<=10000; i++) dp[i]=0;
            for (int i=0; i<n; i++) {
                for (int j=10000; j>=w[i]; j--) {
                    dp[j]=max(dp[j], dp[j-w[i]]+v[i]);
                }
            }
        }
    }
}

まとめ

明日沖縄最終日〜
RUPC Day3からコンテスト日和に復帰します