ACM-ICPC 2016 国内予選 - team: nikku (A: AC, B: AC, C: AC, D: WA, E: WA)

A.cpp

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

void solve(int n){
    vector<long long> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    long long ans = 3000000;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ans = min(ans,abs(a[i]-a[j]));
        }
    }
    cout << ans << endl;
}

int main(void){
    int n;
    while(cin>>n){
        if(n==0) break;
        solve(n);
    }
    return 0;
}

B.cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
int main(){
    while(true){
        int n;cin>>n;
        if(n==0) break;
        string s;REP(i,n)cin>>s[i];
        int hyo[26];
        REP(i,26) hyo[i]=0;
        bool f=false;
        for(int i=0;i<n;i++){
            hyo[s[i]-'A'] ++;
            priority_queue<pair<int,int>,vector<pair<int,int> > > que;
            REP(j,26) que.push(make_pair(hyo[j],j) );
            pair<int,int> p1=que.top();que.pop();
            pair<int,int> p2=que.top();que.pop();
            if(p1.first>p2.first+(n-1-i)){
                printf("%c %d",p1.second+'A',i+1);cout<<endl;
                f=true;break;
            }
        }
        if(!f) cout<<"TIE"<<endl;
    }
    return 0;
}

C.cpp

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

const ll mx = 7368793;

void solve(ll m,ll n){
    vector<bool> u(mx,false);
    int cnt=0;
    for(ll i=m;i<mx;i++){
        if(cnt==n) break;
        if(u[i]==true){
            continue;
        }
        else{
            cnt++;
            for(int t=1;i*t<mx;t++) u[i*t] = true;
        }
    }

//    for(int i=0;i<20;i++){
//        cout << i << " : " << u[i] << endl;
//    }

    for(ll i=m+n;i<mx;i++){
        if(u[i] == false){
            cout << i << endl;
            return;
        }
    }
    cerr << "unexpected" <<endl; 
}

int main(){
    ll m,n;
    while(cin>>m>>n){
        if(m==0 && n==0) break;
        solve(m,n);
    }
}

D.cpp

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

#define rep(i, n) for(int i=0; i<n; ++i)
#define repl(i, s, n) for(int i=s; i<=n; ++i)
#define absd(x) (x>0 ? x : -(x))

#define N 305

int w[N];
int can[N][N];
int dp[N];

int main() {
    int n;
    while(cin >> n && n) { 
        rep(i, n) {
            cin >> w[i];
        }

        rep(i, N) rep(j, N) can[i][j] = 0;
        rep(i, N) dp[i] = 0;

        rep(i, n-1) {
            if(absd(w[i]-w[i+1]) <= 1) {
                can[i][i+1] = 1;
            }
            //cout << can[i][i+1] << endl;
        }

        repl(k, 1, n) {
            rep(i, n) {
                if(i+k >= n) break;
                if(i+1 <= i+k-1 && can[i+1][i+k-1] && absd(w[i] - w[i+k]) <= 1) {
                    can[i][i+k] = 1;
                }
                if(i+2 <= i+k && can[i+2][i+k] && can[i][i+1]) {
                    can[i][i+k] = 1;
                }
                if(i <= i+k-2 && can[i][i+k-2] && can[i+k-1][i+k]) {
                    can[i][i+k] = 1;
                }
                //cout << i << " " << i+k << " " << can[i][i+k] << endl;
            }
        }
        rep(j, n) {
            int res = dp[j];
            repl(i, 0, j) {
                if(can[i][j]) {
                    res = max(res, dp[i] + (j-i+1));
                }
            }
            dp[j+1] = res;
            //cout << dp[j+1] << endl;
        }
        cout << dp[n] << endl;
    }
}

E.cpp

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

#define rep(i, n) for(int i=0; i<n; ++i)
#define absd(x) ((x)>=0 ? (x) : -(x))

typedef pair<int, int> P;
typedef pair<int, P> IP;

#define N 2003
int n, k, s;
int x[N], y[N], z[N];
vector<IP> p;

int parent[N];
int root(int x) {
    if(x == parent[x]) return x;
    return parent[x] = root(parent[x]);
}
void unite(int x, int y) {
    int px = root(x), py = root(y);
    if(px < py) {
        parent[py] = px;
    } else {
        parent[px] = py;
    }
}

bool match(int x, int y) {
    return root(x) == root(y);
}

vector<P> g[N];
#define INF 1000000007
bool used[N];
int maxcost[N];

int main() {
    while(cin >> n >> k >> s && n+k+s) {
        p.clear();
        rep(i, n) g[i].clear();
        rep(i, n) parent[i] = i, used[i] = false;
        rep(i, n) {
            cin >> x[i] >> y[i] >> z[i];
        }
        rep(i, n) {
            rep(j, n) {
                int dx = absd(x[i] - x[j]);
                int dy = absd(y[i] - y[j]);
                int dz = absd(z[i] - z[j]);
                if(dx <= s && dy <= s && dz <= s) {
                    int ex = s - dx;
                    int ey = s - dy;
                    int ez = s - dz;
                    //int area = 2*(dx*dy + dy*dz + dz*dx);
                    int area = 2*(ex*ey + ey*ez + ez*ex);
                    g[i].push_back(P(j, area));
                    g[j].push_back(P(i, area));
                    //cout << i << " " << j << " " << area << endl;
                }
            }
        }
        int ans = -1;
        rep(i, n) {
            //priority_queue<P, vector<P>, greater<P> > que;
            priority_queue<P> que;
            rep(j, n) maxcost[j] = 0, used[j] = false;
            int res = 0;
            int cnt = 0;
            maxcost[i] = 0;
            que.push(P(0, i));
            while(!que.empty()) {
                P p = que.top(); que.pop();
                int cost = p.first, v = p.second;
                if(cost < maxcost[v] || used[v]) continue;
                //cout << v << " " << cost << endl;

                used[v] = true;
                res += maxcost[v];
                ++cnt;
                if(cnt == k) break;

                rep(j, g[v].size()) {
                    P &q = g[v][j];
                    int to = q.first, co = q.second;
                    if(maxcost[to] < co) {
                        maxcost[to] = co;
                        que.push(P(maxcost[to], to));
                    }
                }
            }
            //cout << i << " -> " << cnt << endl;

            if(cnt == k) {
                ans = max(ans, res);
            }
        }
        if(ans == -1) {
            cout << -1 << endl;
        } else {
            //cout << ans << endl;
            cout << 6*k*s*s - ans << endl;
        }
    } 
}