夢追い人

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

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って2つ飛ばしのパターンを失念していて前まで変な貪欲書いてた。
これもカンニング要素あり、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);
}

まとめ・今後のやること

  • とりあえず勉強もやらなければならないので時間を有効的につかう
  • ツイッターはだから最小限に
  • 蟻本を読む
  • 今やってることだけどPKUで一番問題数近くてJOIメダリストのkitayutaさんとdiffをとる。kitayutaさんはSilver結構うめてるのでいい練習にもなる。
  • 自分を戒め続ける
広告を非表示にする