１Bと１C

１Bは眠くて０完太陽、１Cはミスって1182位でギリ落ち。
敗退
萎えた

1B A

問題文が結局正確に把握できなかった
他人のコードで見なおしたところ非常に惜しい
観客のパーセンテージをにぶたん

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-5
typedef long long ll;
int T, N, X;
int s[200];
bool C(double p, int id) {
    double target=s[id]+p*X;
    double sum=p;
    for (int i=0; i<N; i++) {
        if (i==id) continue;
        if (s[i]>target) continue;
        sum+=(target-s[i])/X;
    }
    return sum<=1.0;
}
int main() {
    scanf("%d",&T);
    for (int ix=1; ix<=T; ix++) {
        scanf("%d",&N);
        memset(s,0,sizeof(s));
        for (int i=0; i<N; i++) scanf("%d",&s[i]);
        X=0;
        for (int i=0; i<N; i++) X+=s[i];
        printf("Case #%d: ",ix);
        for (int i=0; i<N; i++) {
            double lb=0.0, ub=1.1;
            for (int j=0; j<1000; j++) {
                double mid=(lb+ub)/2;
                if (C(mid,i)) {
                    lb=mid;
                } else {
                    ub=mid;
                }
            }
            printf("%.6f%c",lb*100,i==N-1?'\n':' ');
        }
    }
}

PKU 1308

前通らなかったのは実は入力のせいだったという悲しい結果。
コメントアウトはネットでよくやられている手法

//#include <cstdio>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <set>
//using namespace std;
//vector<int> G[300];
//vector<int> to[300];
//set<int> s;
//bool vis[300], ok;
//int st, et, num;
//void dfs(int v) {
//    if (vis[v]) {
//        ok=false;
//        return;
//    }
//    vis[v]=true; num++;
//    for (int i=0; i<G[v].size(); i++) {
//        dfs(G[v][i]);
//    }
//}
//int main() {
//    int cn=1;
//    while (scanf("%d%d",&st,&et)) {
//        if (st==-1&&et==-1) break;
//        for (int i=0; i<300; i++) {
//            G[i].clear();
//            to[i].clear();
//        }
//        num=0; s.clear(); ok=true;
//        memset(vis, 0, sizeof(vis));
//        while (st||et) {
//            G[st].push_back(et);
//            to[et].push_back(st);
//            s.insert(st); s.insert(et);
//            scanf("%d%d",&st,&et);
//        }
//        for (int i=0; i<300; i++) {
//            if (to[i].size()==0&&G[i].size()>0) {
//                dfs(i);
//                break;
//            }
//        }
//        printf("Case %d is ",cn++);
//        if (ok&&num>=s.size()) puts("a tree.");
//        else puts("not a tree.");
//    }
//}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
set<int> s;
int st, et, cnt[10000];
bool istree() {
    set<int>::iterator it;
    int rcnt=0;
    for (it=s.begin(); it!=s.end(); it++) {
        if (cnt[*it]>1) return false;
        if (cnt[*it]==0) rcnt++;
    }
    if (s.size()==0) return true;
    return rcnt==1;
}
int main() {
    int cn=1;
    while (scanf("%d%d",&st,&et)) {
        if (st==-1&&et==-1) break;
        memset(cnt, 0, sizeof(cnt));
        s.clear();
        if (st||et) {
            cnt[et]++;
            s.insert(st); s.insert(et);
            while (scanf("%d%d",&st,&et)) {
                if (!st&&!et) break;
                cnt[et]++;
                s.insert(st); s.insert(et);
            }
        }
        printf("Case %d is ",cn++);
        if (istree()) puts("a tree.");
        else puts("not a tree.");
    }
}

AOJ 0520

ようやく実装する気になった
けど一回モビールの仕組みを間違えるという非常事態で１WA←問題文読め

#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
struct mob {
    int l, r, a, b;
    mob () {}
    mob (int l, int r, int a, int b) : l(l),r(r),a(a),b(b) {}
};
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
ll lcm(ll a, ll b) { return a*b/gcd(a,b); }

vector<int> to[101];
mob mobs[101];
int n;

ll dfs(int id) {
    ll a=1, b=1;
    if (mobs[id].a) a=dfs(mobs[id].a);
    if (mobs[id].b) b=dfs(mobs[id].b);
    ll x=lcm(a*mobs[id].l, b*mobs[id].r);
    return x/mobs[id].r+x/mobs[id].l;
}

int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<101; i++) {
            to[i].clear();
        }
        for (int i=1; i<=n; i++) {
            int l, r, a, b; scanf("%d%d%d%d",&l,&r,&a,&b);
            mobs[i]=mob(l,r,a,b);
            if (a) to[a].push_back(i);
            if (b) to[b].push_back(i);
        }
        ll res=0;
        for (int i=1; i<=n; i++) {
            if (to[i].size()==0) {
                res=dfs(i);
                break;
            }
        }
        printf("%lld\n",res);
    }
}

1C A

これはやるだけ

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int t, n;
vector<int> g[1000];
bool vis[1000];
bool dfs(int id) {
    if (vis[id]) return true;
    vis[id]=true;
    bool flag=false;
    for (int i=0; i<g[id].size(); i++) {
        flag=dfs(g[id][i]);
        if (flag) return true;
    }
    return false;
}
int main() {
    scanf("%d",&t);
    for (int ix=1; ix<=t; ix++) {
        scanf("%d",&n);
        for (int i=0; i<1000; i++) g[i].clear();
        for (int i=0; i<n; i++) {
            int m; scanf("%d",&m);
            for (int j=0; j<m; j++) {
                int c; scanf("%d",&c);
                g[i].push_back(c-1);
            }
        }
        bool flag=false;
        for (int i=0; i<n; i++) {
            if (g[i].size()==0) continue;
            memset(vis, 0, sizeof(vis));
            flag=dfs(i);
            if (flag) break;
        }
        printf("Case #%d: ",ix);
        if (flag) puts("Yes");
        else puts("No");
    }
}

1C C

メモ化再帰は自明
ただし簡単にやろうとするといろんなケースが飛ばされてしまってWA
あるところで同じ種類になったら、それを取った後の全てのケースを列挙してDFSしなければならない

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
int t, n, m;
P a[100], b[100];
ll dp[101][101];
ll dfs(int i, int j) {
    if (i>=n||j>=m) return 0;
    if (dp[i][j]!=-1) return dp[i][j];
    ll res=0;
    if (a[i].second!=b[j].second) res=max(dfs(i,j+1),dfs(i+1,j));
    else {
        ll useA=0, useB=0;
        int x=a[i].second;
        for (int k=i; k<n; k++) {
            if (a[k].second!=x) continue;
            useA+=a[k].first;
            useB=0;
            for (int l=j; l<m; l++) {
                if (b[l].second!=x) continue;
                useB+=b[l].first;
                res=max(res,dfs(k+1,l+1)+min(useA,useB));
            }
        }
    }
    return dp[i][j]=res;
}
int main() {
    scanf("%d",&t);
    for (int ix=1; ix<=t; ix++) {
        scanf("%d%d",&n,&m);
        memset(dp,-1,sizeof(dp));
        for (int i=0; i<n; i++) {
            scanf("%lld%d",&a[i].first,&a[i].second);
        }
        for (int i=0; i<m; i++) {
            scanf("%lld%d",&b[i].first,&b[i].second);
        }
        printf("Case #%d: %lld\n",ix,dfs(0,0));
    }
}