夢追い人

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

猛精進

プログラミング 競技プログラミング

AOJ+PKU=333
でJOI行ってきます(^O^)
明日の食事会楽しみやわ〜

PKU 3273

にぶたん
にぶたんってどの値を初期値にしてどの値を答えとして出力すればいいのかとっても難しいよね

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m;
ll money[100000];
bool C(ll cost) {
    ll sum=0, mon=1;
    for (int i=0; i<n; i++) {
        if (sum+money[i]>cost) {
            sum=money[i];
            mon++;
        } else {
            sum+=money[i];
        }
    }
    if (mon<=m) return true;
    else return false;
}
int main() {
    scanf("%d%d",&n,&m);
    ll l=0, u=1;
    for (int i=0; i<n; i++) {
        scanf("%lld",&money[i]);
        l=max(l,money[i]);
        u+=money[i];
    }
    while (u>l) {
        int mid=(l+u)/2;
        if (C(mid)) u=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
}

PKU 3104

にぶたん
他人のコードみなきゃkの解釈違い気づかないよ・・・
less thanって言葉怖い

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, k;
int a[100000];
bool C(int x) {
    ll sum=0;
    for (int i=0; i<n; i++) {
        if (a[i]>x) {
            if ((a[i]-x)%k) sum+=floor((double)(a[i]-x)/(double)k)+1;
            else sum+=(a[i]-x)/k;
        }
    }
    if (sum<=x) return true;
    else return false;
}
int main() {
    scanf("%d",&n);
    int l=-1, u=0;
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
        u=max(u, a[i]);
    }
    scanf("%d",&k);
    k--;
    if (k==0) {
        int ans=-1;
        for (int i=0; i<n; i++) ans=max(ans,a[i]);
        printf("%d\n",ans);
        return 0;
    }
    while (u-l>1) {
        int mid=(l+u)/2;
        if (C(mid)) u=mid;
        else l=mid;
    }
    printf("%d\n",u);
}

PKU 3009

あり本BFSの練習問題だけどDFSじゃないと普通の人は解けません

#include <cstdio>
#include <algorithm>
using namespace std;
int w, h, sx, sy, gx, gy;
int board[20][20];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
bool isin(int x, int y) { return x>=0&&x<h&&y>=0&&y<w; }
int dfs(int x, int y, int cnt) {
    if (cnt==10) return 11;
    int res=11;
    for (int i=0; i<4; i++) {
        int nx=x+dx[i], ny=y+dy[i];
        if (!isin(nx,ny)) continue;
        if (isin(nx,ny)&&nx==gx&&ny==gy) return cnt+1;
        if (isin(nx,ny)&&board[nx][ny]==1) continue;
        while (isin(nx+dx[i],ny+dy[i])) {
            nx+=dx[i]; ny+=dy[i];
            if (!isin(nx,ny)) break;
            if (isin(nx,ny)&&nx==gx&&ny==gy) return cnt+1;
            if (isin(nx,ny)&&board[nx][ny]==1) {
                board[nx][ny]=0;
                res=min(res,dfs(nx-dx[i],ny-dy[i],cnt+1));
                board[nx][ny]=1;
                break;
            }
        }
    }
    return res;
}
int main() {
    while (scanf("%d%d",&w,&h)) {
        if (!w&&!h) break;
        for (int i=0; i<h; i++) for (int j=0; j<w; j++) {
            scanf("%d",&board[i][j]);
            if (board[i][j]==2) {
                board[i][j]=0;
                sx=i; sy=j;
            }
            if (board[i][j]==3) {
                board[i][j]=0;
                gx=i; gy=j;
            }
        }
        int ans=dfs(sx,sy,0);
        printf("%d\n",ans==11?-1:ans);
    }
}

PKU 3669

BFS
勢いで書いて0秒の時でも隕石が落ちてくることを忘れないように

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct npos {
    int x, y, t;
    npos(int _x, int _y, int _t) {
        x=_x; y=_y; t=_t;
    }
};
int m;
int board[400][400];
bool visited[400][400];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool isin(int x, int y) { return x>=0&&y>=0; }
int main() {
    for (int i=0; i<400; i++) for (int j=0; j<400; j++) board[i][j]=2000;
    scanf("%d",&m);
    for (int i=0; i<m; i++) {
        int x, y, t; scanf("%d%d%d",&x,&y,&t);
        board[x][y]=min(board[x][y],t);
        for (int j=0; j<4; j++) {
            int nx=x+dx[j], ny=y+dy[j];
            if (isin(nx,ny)) board[nx][ny]=min(board[nx][ny],t);
            // printf("%d %d %d\n",nx,ny,isin(nx,ny)?1:0);
        }
    }
    /*for (int i=0; i<10; i++) for (int j=0; j<10; j++) {
        printf("%d%c",board[i][j],j==9?'\n':' ');
    }*/
    queue<npos> que;
    que.push(npos(0,0,0));
    while (!que.empty()) {
        npos n=que.front(); que.pop();
        if (visited[n.x][n.y]) continue;
        visited[n.x][n.y]=true;
        if (board[n.x][n.y]==2000) {
            printf("%d\n",n.t);
            return 0;
        }
        // printf("%d %d %d\n",n.x,n.y,n.t);
        for (int i=0; i<4; i++) {
            int nx=n.x+dx[i], ny=n.y+dy[i];
            if (isin(nx,ny)&&!visited[nx][ny]) {
                if (board[nx][ny]<=n.t+1) continue;
                else {
                    que.push(npos(nx,ny,n.t+1));
                }
            }
        }
    }
    puts("-1");
}

AOJ 2224

フェンスで囲まれている猫たちをフェンスの一部を取り除いて脱出させるために必要な最小のコスト
これはつまり問題文をよく読んでませんが最大全域木を作ると、それ以外の辺が最小になるので合計から引けばいいと。
なんだか調べてると最大全域木ってあり本でもそうですがプリムで、コストを-1倍しておき最後に出てきたコストを-1倍する方法でやるのが主流らしいんですが、まぁ前も最大全域木問題で僕がやったようにクラスカルで逆順ソートのほうがよっぽどわかりやすいです。
なぜこれでいいのかというとクラスカルはコストが小さい辺から貪欲に、その端点同士が同じ木に入ってなければその辺を使うということで、これはなんだかんだいって理屈は自明なのですが、それを考えるとコストが大きい辺から貪欲にとれば閉路のない最大コストの全域木ができることも自明だからです。

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int par[10000];
int rank[10000];
void init(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 point { int x, y; };
struct edge {
    int u, v;
    double cost;
};
bool comp(const edge& e1, const edge& e2) {
    return e1.cost>e2.cost;
}
double dist(point p1, point p2) {
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
point p[10000];
vector<edge> es;
int main() {
    int n, m;
    scanf("%d%d",&n,&m);
    init(n);
    for (int i=0; i<n; i++) scanf("%d%d",&p[i].x,&p[i].y);
    double all=0.0;
    for (int i=0; i<m; i++) {
        int s, e; scanf("%d%d",&s,&e);
        edge ne=(edge){s-1,e-1,dist(p[s-1],p[e-1])};
        es.push_back(ne);
        all+=ne.cost;
    }
    sort(es.begin(), es.end(), comp);
    double res=0.0;
    for (int i=0; i<m; i++) {
        edge e=es[i];
        if (!same(e.u,e.v)) {
            unite(e.u, e.v);
            res+=e.cost;
        }
    }
    printf("%.3f\n",all-res);
}

AOJ 0130

やるだけ

#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    int t; scanf("%d",&t);
    for (int ix=0; ix<t; ix++) {
        string str; cin>>str;
        string res="", temp="";
        res+=str[0];
        int pos=0;
        for (int i=1; i<str.length(); i++) {
            if (str[i]!='-'&&str[i]!='>'&&str[i]!='<') {
                if (temp=="->") {
                    pos++;
                    if (res.length()==pos) res+=str[i];
                    else if (res[pos]!=str[i]) {
                        res+='x';
                        for (int j=res.length()-1; j>pos; j--) {
                            res[j]=res[j-1];
                        }
                        res[pos]=str[i];
                    }
                } else {
                    pos--;
                    if (pos==-1) {
                        res=str[i]+res;
                        pos=0;
                    } else if (res[pos]!=str[i]) {
                        res='x'+res;
                        for (int j=0; j<pos; j++) {
                            res[j]=res[j+1];
                        }
                        res[pos]=str[i];
                    }
                }
                temp="";
            } else temp+=str[i];
        }
        cout<<res<<endl;
    }
}

AOJ 2104

その範囲を白領域、黒領域、もしくはどちらでもない領域のいずれの領域として加算するのか判定する必要があるのでDFSでもできないことはないですが、BFSのほうが楽です。
あとはやるだけ

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> P;
int w,h,wnum, bnum;
string field[50];
bool isin(int x, int y) { return x>=0&&x<h&&y>=0&&y<w; }
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int main() {
    while (scanf("%d%d",&w,&h)) {
        if (!w&&!h) break;
        wnum=bnum=0;
        for (int i=0; i<h; i++) cin>>field[i];
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                if (field[i][j]=='.') {
                    int cnt=1;
                    char flag='0';
                    field[i][j]='-';
                    queue<P> que;
                    que.push(P(i,j));
                    while (!que.empty()) {
                        P p=que.front(); que.pop();
                        for (int k=0; k<4; k++) {
                            int nx=p.first+dx[k], ny=p.second+dy[k];
                            if (!isin(nx,ny)) continue;
                            if (field[nx][ny]=='.') {
                                que.push(P(nx,ny));
                                field[nx][ny]='-';
                                cnt++;
                            }
                            if (flag=='0') {
                                if (field[nx][ny]=='W') {
                                    flag='W';
                                } else if (field[nx][ny]=='B') {
                                    flag='B';
                                }
                            } else if (field[nx][ny]=='W'&&flag=='B') {
                                flag='X';
                            } else if (field[nx][ny]=='B'&&flag=='W') {
                                flag='X';
                            }
                        }
                    }
                    if (flag=='W') wnum+=cnt;
                    if (flag=='B') bnum+=cnt;
                }
            }
        }
        // for (int i=0; i<h; i++) cout<<field[i]<<endl;
        printf("%d %d\n",bnum,wnum);
    }
}

まとめ

JOIがんばるどー
JOI・AKBクラスタは何人いるのでしょうか？？？？（現在３人）
それにしてもAOJのレートの低さはどげんかせんといかんですね