ICPC国内予選模擬 - team: IQ1

A.cpp

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using pii = pair<int,int>;

template<typename T> ostream& operator<< (ostream& os,const vector<T>& vec){ os << "{"; for(T v:vec) os << v << ","; os << "}"; }
template<typename T> ostream& operator<< (ostream& os,const set<T>& st){ os << "{"; for(T v:st) os << v << ","; os << "}"; }

int n,m;

void solve(){
    vector<int> a(m+10,0);

    rep(i,n){
        int d,v;
        cin >> d >> v;
        a[d] = max(a[d],v);
    }

    int ans = 0;
    for(int i=1;i<=m;i++){
        ans += a[i];
    }
    cout << ans << endl;
}

int main(){
   while(1){
       cin >> n >> m;
       if(n==0 and m==0) break;
       solve();
   }
}

B.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using pii = pair<int,int>;

template<typename T> ostream& operator<< (ostream& os,const vector<T>& vec){ os << "{"; for(T v:vec) os << v << ","; os << "}"; }
template<typename T> ostream& operator<< (ostream& os,const set<T>& st){ os << "{"; for(T v:st) os << v << ","; os << "}"; }


int main()  {
    int T, D, L;
    int x[100000];
    while (true) {
        cin >> T >> D >> L;
        if (T == 0 && D == 0 && L == 0) break;
        for (int j = 0; j < T; ++j) {
            cin >> x[j];
        }

        int prev = -10000000;
        int ans = 0;
        for (int j = 0; j < T-1; ++j) {
            if (x[j] >= L) {
                prev = j;
            }

            if (j - prev < D) {
                ++ans;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C.py

while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    ma = [0]*n
    mi = [0]*n
    for i in xrange(m):
        ipt = map(int, raw_input().split())
        s = ipt[0]; k = ipt[1]; C = ipt[2:]
        for c in C:
            ma[c-1] += s
            if k == 1:
                mi[c-1] += s
    ans = 0
    A = range(n); B = range(n)
    A.sort(key=lambda x:ma[x])
    B.sort(key=lambda x:mi[x])
    if A[-1] != B[0]:
        print ma[A[-1]] - mi[B[0]] + 1
    else:
        print max(ma[A[-2]] - mi[B[0]], ma[A[-1]] - mi[B[1]])+1

D.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using pii = pair<int,int>;

template<typename T> ostream& operator<< (ostream& os,const vector<T>& vec){ os << "{"; for(T v:vec) os << v << ","; os << "}"; }
template<typename T> ostream& operator<< (ostream& os,const set<T>& st){ os << "{"; for(T v:st) os << v << ","; os << "}"; }

const int INF = 1LL<<30;

int N, M, s[100000];

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    while (true) {
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        for (int j = 0; j < N; ++j) {
            cin >> s[j];
        }

        int dp[2000001];
        int xl = max(1, s[0]), xr = s[N-1];
        while (xl+1 < xr) {
            fill(dp, dp+2000001, INF);
            dp[1] = 0;

            int x = (xl + xr) / 2;
            for (int j = 1; j < s[N-1]; ++j) {
                int* p = lower_bound(s, s+N, j);
                if (p > s) {
                    if (abs(j - *(p-1)) < abs(j - *p)) {
                        p = p-1;
                    }
                }

                int up = max(1, x - abs(j - *p));
                dp[j + up] = min(dp[j + up], dp[j] + 1);
            }

            int ans = INF;
            for (int j = s[N-1]-x+1; j <= 2000000; ++j) {
                ans = min(ans, dp[j]+1);
            }


            if (ans < M) {
                xr = x;
            } else {
                xl = x;
            }
        }


        fill(dp, dp+2000001, INF);
        dp[1] = 0;
        for (int j = 1; j < s[N-1]; ++j) {
            int* p = lower_bound(s, s+N, j);
            if (p > s) {
                if (abs(j - *(p-1)) < abs(j - *p)) {
                    p = p-1;
                }
            }
            int up = max(1, xl - abs(j - *p));
            dp[j + up] = min(dp[j + up], dp[j] + 1);
        }

        int ans = INF;
        for (int j = s[N-1]-xl+1; j <= 2000000; ++j) {
            ans = min(ans, dp[j]+1);
        }

        if (ans >= M) {
            cout << xl << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

E(WA).py

from math import *
def cross((x0, y0), (x1, y1), (x2, y2)):
    return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)
def convex_hull(P):
    P.sort()
    st = []
    for p in P:
        while len(st) > 1 and cross(st[-2], st[-1], p) >= 0:
            st.pop()
        st.append(p)
    k = len(st)
    for p in reversed(P):
        while len(st) > k and cross(st[-2], st[-1], p) >= 0:
            st.pop()
        st.append(p)
    return st
def contain(P, q):
    base = None
    for i in xrange(len(P)):
        p0 = P[i-1]; p1 = P[i]
        res = cross(p0, p1, q)
        if base:
            if base*res < 0:
                return 0
        else:
            base = res
    return 1
def contains(P, Q):
    for i in xrange(len(P)):
        p0 = P[i-1]; p1 = P[i]
        for j in xrange(len(Q)):
            q0 = Q[j-1]; q1 = Q[j]
            if cross(p0, p1, q0) * cross(p0, p1, q1) < 0 and cross(q0, q1, p0) * cross(q0, q1, p1) < 0:
                return 1
    return any(contain(P, q) for q in Q) or any(contain(Q, p) for p in P)

def calc((x0, y0), (x1, y1)):
    return sqrt((x1 - x0)**2 + (y1 - y0)**2)
def dist(P, q):
    res = min(calc(p, q) for p in P)
    x, y = q
    for i in xrange(len(P)):
        x0, y0 = p0 = P[i-1]; x1, y1 = p1 = P[i]
        xd = x1 - x0; yd = y1 - y0
        if 0 < xd*(x - x0) + yd*(y - y0) < xd**2 + yd**2:
            d = sqrt( (x - x0)**2 + (y - y0)**2 - (xd*(x-x0) + yd*(y-y0))**2 / (xd**2 + yd**2) )
            res = min(res, d)
    return res
def dists(P, Q):
    return min(min(dist(P, q) for q in Q), min(dist(Q, p) for p in P))
while 1:
    n = input()
    if n == 0:
        break
    H = []
    T = []
    for i in xrange(n):
        ipt = map(int, raw_input().split())
        nv = ipt[0]; T.append(ipt[1])
        tmp = []
        for i in xrange(nv):
            x = ipt[2+2*i]; y = ipt[3+2*i]
            tmp.append((x, y))
        H.append(tmp)
    theta, phi = map(int, raw_input().split())
    sx, sy, tx, ty = map(int, raw_input().split())
    for i in xrange(n):
        t = T[i]
        tmp = []
        for x, y in H[i]:
            l = t * tan((90-phi) / 180.*pi)
            hx = x - l * cos(theta / 180.*pi)
            hy = y - l * sin(theta / 180.*pi)
            tmp.append((hx, hy))
        H[i].extend(tmp)
        H[i] = convex_hull(H[i])
    E = [[10**18]*(n+2) for i in xrange(n+2)]
    for i in xrange(n):
        for j in xrange(n):
            if i == j:
                continue
            if contains(H[i], H[j]):
                E[i][j] = E[j][i] = 0
            else:
                E[i][j] = E[j][i] = dists(H[i], H[j])
    for i in xrange(n):
        if contain(H[i], (sx, sy)):
            E[i][n] = E[n][i] = 0
        else:
            E[i][n] = E[n][i] = dist(H[i], (sx, sy))
    for i in xrange(n):
        if contain(H[i], (tx, ty)):
            E[i][n+1] = E[n+1][i] = 0
        else:
            E[i][n+1] = E[n+1][i] = dist(H[i], (tx, ty))
    for k in xrange(n+2):
        for i in xrange(n+2):
            for j in xrange(n+2):
                E[i][j] = min(E[i][j], E[i][k] + E[k][j])
    print "%.06f" % E[n][n+1]

F(WA).cpp

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using pii = pair<int,int>;

template<typename T> ostream& operator<< (ostream& os,const vector<T>& vec){ os << "{"; for(T v:vec) os << v << ","; os << "}"; }
template<typename T> ostream& operator<< (ostream& os,const set<T>& st){ os << "{"; for(T v:st) os << v << ","; os << "}"; }

int N;
vector<vector<ll>> x;
bool used[128];
struct Node{
    int index;
    int taiseki;
    Node(){}
    Node(int a,int b) : index(a),taiseki(b){}
};

set<int> roots;
vector<Node> nodes;
ll ans = 0;

vector<set<int>> g; // g[i].count(j) --> i can have j (i > j)

void make_graph(){
    rep(i,N) if(!used[i]){
        rep(j,N) if(!used[j]){
            if(i==j) continue;
            bool ok=true;
            rep(k,3) if(x[i]>=x[j]) ok=false;
            if(ok) g[j].insert(i);
        }
    }
}

pair<int,set<int>> dfs(int node){
    //cout << "node : " << node << endl;
    if((int)g[node].size()==0){ // leaf
        set<int> ret;
        ret.insert(node);
        return mp(nodes[node].taiseki,ret);
    }

    int n = g[node].size();
    int maxv = -1;
    set<int> ret;

    for(int child : g[node]){
        auto p = dfs(child);
        int a = p.fi;
        set<int> b = p.se;

        if(maxv < a){
            maxv = a;
            ret = b;
        }
    }

    ret.insert(node);
    return mp(maxv,ret);
}


void solve(){
    x.resize(N);
    g.resize(N);
    nodes.resize(N);
    rep(i,N){
        ll a,b,c;cin >> a >> b >> c;
        x[i].pb(a);
        x[i].pb(b);
        x[i].pb(c);
        sort(x.begin(),x.end());
        nodes[i] =  Node(i,a*b*c);
    }

    while(1){
        bool ok=true;
        rep(i,N) if(!used[i]){
            ok=false;
        }
        if(ok) break;
        make_graph();

        //cout << g << endl;

        vector<int> poi(N,0);
        rep(i,N){
            if(g[i].size() > 0) poi[i]++;
            for(int v : g[i]) poi[v]++;
        }

        rep(i,N) if(poi[i]==0){        // 孤立点
            //cout << "i : " << i << endl;
            roots.insert(i);
            used[i] = true;
        }

        int cnt = -1;
        int root = -1;
        for(int i=0;i<N;i++){
            if(used[i]==false and cnt < (int)g[i].size()){
                cnt = g[i].size();
                root = i;
            }
        }

        //cout << "root : " << root<< endl;

        if(root<0) break;
        auto p = dfs(root);
        roots.insert(root);

        cout << "root : " << root  << endl;
        cout << p.se << endl;

        //cout << p.se << endl;

        for(int xx : p.se){
            used[xx] = true;
        }

    }


    for(int xx : roots){
        ans += nodes[xx].taiseki;
    }

    cout << ans << endl;
}

int main(){
    while(1){
        rep(i,128) used[i]=false;
        cin >> N;
        ans = 0;
        roots.clear();
        if(N==0) break;
        solve();
    }
}