KS唯一の脱落者の執念

今日JOI結果発表された。
当然Bランク、JOI・AKBクラスタではケビンさんが合宿通ったので頑張ってもらいたい（経験的には順当）
KS生では唯一の脱落者となってしまったので来年は予選・本選満点でIOI代表にならなければならない。
あと今年中にTopCoder黄色行きます、それが目標です。

AOJ 0518

最初setから頂点探すのにcountつかってたらオーダーがO(N^3)になってしまっていたようでTLE。
findならば見つかったところで探索打ち切りなのでちゃんとO(N^2 log N)になる。
案外解法はちょっとまえにカンニングしてたかもしれないorz

#include <cstdio>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int, int> P;
int n;
P st[3000];
int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        set<P> stat;
        for (int i=0; i<n; i++) {
            scanf("%d%d",&st[i].first,&st[i].second);
            stat.insert(st[i]);
        }
        int res=0;
        for (int i=0; i<n; i++) {
            P a=st[i];
            for (int j=0; j<n; j++) {
                P b=st[j];
                int dist1=b.first-a.first, dist2=a.second-b.second;
                if (stat.find(P(b.first-dist2,b.second-dist1))!=stat.end()&&stat.find(P(a.first-dist2,a.second-dist1))!=stat.end()) {
                    res=max(res,dist1*dist1+dist2*dist2);
                }
            }
        }
        printf("%d\n",res);
    }
}

PKU 3670

DPだったらしい。
1->3って２つ飛ばしのパターンを失念していて前まで変な貪欲書いてた。
これもカンニング要素あり、DPなんとかしなければならない。

#include <cstdio>
#include <algorithm>
using namespace std;
int dp[30000][3];
int card[30000];
int main() {
    int n; scanf("%d",&n);
    for (int i=0; i<n; i++) scanf("%d",&card[i]);
    int ans=n;
    for (int k=0; k<2; k++) {
        for (int j=0; j<3; j++) dp[0][j]=(card[0]!=j+1);
        for (int i=1; i<n; i++) {
            dp[i][0]=dp[i-1][0]+(card[i]!=1);
            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+(card[i]!=2);
            dp[i][2]=min(min(dp[i-1][0],dp[i-1][1]),dp[i-1][2])+(card[i]!=3);
        }
        reverse(card, card+n);
        for (int i=0; i<3; i++) ans=min(ans,dp[n-1][i]);
    }
    printf("%d\n",ans);
}

PKU 3626

第一象限以外の象限も含めた座標でのBFS。
左端と右端、上端と下端がそれぞれ-500,500なので実際の座標に500足すと正だけの座標に直せる。

#include <cstdio>
#include <map>
#include <queue>
using namespace std;
typedef pair<int, int> P;
int x, y, n;
int field[1001][1001];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int main() {
    scanf("%d%d%d",&x,&y,&n);
    for (int i=0; i<n; i++) {
        int a, b; scanf("%d%d",&a,&b);
        field[a+500][b+500]=1;
    }
    queue<pair<P,int> > que;
    que.push(make_pair(P(500,500),0));
    int res=0;
    while (!que.empty()) {
        pair<P, int> p=que.front(); que.pop();
        int ax=p.first.first,ay=p.first.second;
        int cnt=p.second;
        if (ax==x+500&&ay==y+500) {
            res=cnt;
            break;
        }
        if (field[ax][ay]==1) continue;
        field[ax][ay]=1;
        for (int i=0; i<4; i++) {
            int nx=ax+dx[i], ny=ay+dy[i];
            if (nx>=0&&nx<1001&&ny>=0&&ny<1001&&field[nx][ny]==0) {
                que.push(make_pair(P(nx,ny),cnt+1));
            }
        }
    }
    printf("%d\n",res);
}

PKU 3625

最小全域木問題。各点の座標から考えうる道をすべて計算しておき、さらにすでに引いてある道があるのでこれは先にその端点同士をUnion-Find木でuniteしておく。
あとは普通にクラスカルをやるだけ。こういう問題みるとやっぱりプリムよりクラスカルが便利なのではと思う。
ちなみにデータ構造をstructでは初めて書いた。セグツリーとかstructでやったほうが明らかにいいですね。はい。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
struct unionfind {
    int par[1000], rank[1000];
    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;
    double cost;
};
bool comp(const edge& e1, const edge& e2) {
    return e1.cost<e2.cost;
}
int n,m;
ll x[1000],y[1000];
edge es[1000000];
int main() {
    scanf("%d%d",&n,&m);
    for (int i=0; i<n; i++) {
        scanf("%lld%lld",&x[i],&y[i]);
    }
    int edn=0;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            es[edn].u=i;
            es[edn].v=j;
            es[edn].cost=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            edn++;
        }
    }
    unionfind uf(n);
    for (int i=0; i<m; i++) {
        int a, b; scanf("%d%d",&a,&b);
        uf.unite(a-1,b-1);
    }
    sort(es, es+edn, comp);
    double res=0.0;
    for (int i=0; i<edn; i++) {
        edge e=es[i];
        if (!uf.same(e.u,e.v)) {
            uf.unite(e.u,e.v);
//            printf("%d %d %.2f\n",e.u,e.v,e.cost);
            res+=e.cost;
        }
    }
    printf("%.2f\n",res);
}