夢追い人

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

バレンタインのカンニング

プログラミング

自分との共通項が０でもなぜかロマンチストになってしまうバレンタインデー、自力で解けた問題少ない。
頭悪すぎて生きてる意味がない。

3615

ある点からある点に行く時に通る辺の最大コストが最小になるような行き方を求める問題。
ある点iからある点jの答えはある点kを通過するかしないかというのはワーシャルフロイドと同じ考え方で、つまりiからkまでの最大コストとkからjまでの最大コストの大きい方がiからjまでの最大コストになる。
だからワーシャルフロイドの足し算の項をmax()に置き換えればいい。

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int INF=INT_MAX/2;
int n, m, t;
int d[300][300];
int main() {
    for (int i=0; i<300; i++) for (int j=0; j<300; j++) d[i][j]=INF;
    scanf("%d%d%d",&n,&m,&t);
    for (int i=0; i<m; i++) {
        int s, e, h; scanf("%d%d%d",&s,&e,&h);
        d[s-1][e-1]=h;
    }
    for (int k=0; k<n; k++) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
        }
    }
    for (int i=0; i<t; i++) {
        int a,b;scanf("%d%d",&a,&b);
        if (d[a-1][b-1]==INF) puts("-1");
        else printf("%d\n",d[a-1][b-1]);
    }
}

1182

Union-Find木蟻本例題。
結局終始蟻本だよりだった気がする(^_^;)
でも要するにただの論理です。

#include <cstdio>
struct unionfind {
    int par[150001], rank[150001];
    unionfind(int n) {
        for (int i=0; i<n; i++) {
            par[i]=i;
            rank[i]=0;
        }
    }
    int find(int x) {
        if (par[x]==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 n, k;
int main() {
    scanf("%d%d",&n,&k);
    unionfind uf(3*n);
    int res=0;
    for (int i=0; i<k; i++) {
        int t,x,y; scanf("%d%d%d",&t,&x,&y);
        x--; y--;
        if (x<0||n<=x||y<0||n<=y) {
            res++;
            continue;
        }
        if (t==1) {
            if (uf.same(x,y+n)||uf.same(x,y+2*n)) {
                res++;
            } else {
                uf.unite(x,y);
                uf.unite(x+n,y+n);
                uf.unite(x+2*n,y+2*n);
            }
        } else {
            if (uf.same(x,y)||uf.same(x,y+2*n)) {
                res++;
            } else {
                uf.unite(x,y+n);
                uf.unite(x+n,y+2*n);
                uf.unite(x+2*n,y);
            }
        }
    }
    printf("%d\n",res);
}

3723

またもや蟻本。。。
日本語文見ても解法みるまで題意がわからなかったｗｗｗ

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
struct unionfind {
    int par[20001], rank[20001];
    unionfind(int n) {
        for (int i=0; i<n; i++) {
            par[i]=i;
            rank[i]=0;
        }
    }
    int find(int x) {
        if (par[x]==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);
    }
};
struct edge { int u, v, cost; };
bool comp(const edge& a, const edge& b) { return a.cost<b.cost; }
int n,m,r;
edge es[50000];
int main() {
    int t; scanf("%d",&t);
    for (int ix=0; ix<t; ix++) {
        scanf("%d%d%d",&n,&m,&r);
        for (int i=0; i<r; i++) {
            int x, y, d; scanf("%d%d%d",&x,&y,&d);
            es[i]=(edge){x,y+n,-1*d};
        }
        unionfind uf(n+m);
        sort(es, es+r, comp);
        ll res=10000*(n+m);
        for (int i=0; i<r; i++) {
            edge e=es[i];
//            printf("%d %d\n",e.u,e.v);
            if (!uf.same(e.u,e.v)) {
                uf.unite(e.u,e.v);
                res+=e.cost;
            }
        }
        printf("%lld\n",res);
    }
}

2030

ACM/ICPCの過去問だそうです。
DPです。解法みたら頭いいって思えました。はい。

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
int w,h;
int dx[2]={-1,0};
int dy[2]={0,-1};
string mat[70];
string dp[70][70];
int main() {
    while (scanf("%d%d",&w,&h)){
        if (!w&&!h) break;
        for (int i=0; i<70; i++) for (int j=0; j<70; j++) dp[i][j]="";
        for (int i=0; i<h; i++) cin>>mat[i];
        bool bef=false;
        if ('0'<mat[0][0]&&mat[0][0]<='9') {
            bef=true;
            dp[0][0]=mat[0][0];
        }
        for (int i=1; i<w; i++) {
            if (bef&&'0'<=mat[0][i]&&mat[0][i]<='9') {
                dp[0][i]=dp[0][i-1]+mat[0][i];
            } else if ('0'<mat[0][i]&&mat[0][i]<='9') {
                dp[0][i]=mat[0][i];
                bef=true;
            } else if (mat[0][i]!='0') {
                bef=false;
            }
        }
        for (int i=1; i<h; i++) {
            for (int j=0; j<w; j++) {
                if ('0'<=mat[i][j]&&mat[i][j]<='9') {
                    for (int k=0; k<2; k++) {
                        int nx=i+dx[k], ny=j+dy[k];
                        if (nx>=0&&nx<h&&ny>=0&&ny<w) {
                            int len=dp[i][j].length(), len2=dp[nx][ny].length()+1;
                            if (len<len2&&len2!=1) dp[i][j]=dp[nx][ny]+mat[i][j];
                            else if (len==len2&&dp[i][j]<dp[nx][ny]+mat[i][j]) {
                                dp[i][j]=dp[nx][ny]+mat[i][j];
                            }
                        }
                    }
                    if (dp[i][j].length()==0&&mat[i][j]!='0') dp[i][j]=mat[i][j];
                }
            }
        }
        int rlen=0;
        string rstr;
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (rlen<dp[i][j].length()) {
                    rlen=dp[i][j].length();
                    rstr=dp[i][j];
                } else if (rlen==dp[i][j].length()&&rstr<dp[i][j]) {
                    rstr=dp[i][j];
                }
            }
        }
        cout<<rstr<<endl;
    }
}

1458

LCS、向かってみたら自分がLCSの漸化式さえ考えつかないことにようやく気づきました・・・
蟻本

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string x, y;
    while (cin>>x>>y) {
        int xlen=x.length(), ylen=y.length();
        int dp[xlen+1][ylen+1];
        for (int i=0; i<=xlen; i++) for (int j=0; j<=ylen; j++) dp[i][j]=0;
        for (int i=0; i<xlen; i++) {
            for (int j=0; j<ylen; j++) {
                if (x[i]==y[j]) {
                    dp[i+1][j+1]=dp[i][j]+1;
                } else {
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        printf("%d\n",dp[xlen][ylen]);
    }
}

あれ？昨日やった一問以外本当に全部自力で解いたものがない・・・

2028

やるだけ問題付け加えた。自力だけど慰めにもならなかったｗ

#include <cstdio>
int n, q;
int cnt[101];
int main() {
    while (scanf("%d%d",&n,&q)) {
        if (!n&&!q) break;
        for (int i=0; i<101; i++) cnt[i]=0;
        for (int i=0; i<n; i++) {
            int m; scanf("%d",&m);
            for (int j=0; j<m; j++) {
                int day; scanf("%d",&day);
                cnt[day-1]++;
            }
        }
        int rcnt=0, res=0;
        for (int i=0; i<101; i++) {
            if (cnt[i]>=q&&rcnt<cnt[i]) {
                res=i+1;
                rcnt=cnt[i];
            }
        }
        printf("%d\n",res);
    }
}