AOJ 1127: Building a Space Station

問題

Building a Space Station | Aizu Online Judge

• 宇宙ステーションの各ユニットを全てつなぎたい
• 各ユニットは座標(x, y, z)に存在し、半径がrの球形である。球が接触していない場合は廊下でつなぐ必要がある
• 必要な廊下の長さの最小値を求めよ

方針

• いわゆる最小全域木の問題
• 各辺の長さはmin(0, 中心間距離-2球の半径の和)と表される
• 辺が密なのでプリム法を使う

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

double cost[101][101];
double mincost[101];
bool used[101];
double x[101], y[101], z[101], r[101];
double INF = numeric_limits<double>::max();
int main(void){
    int n;
    while(cin >> n && n) {
        rep(i, n) {
            cin >> x[i] >> y[i] >> z[i] >> r[i];
        }
        rep(i, n) rep(j, n) {
            cost[i][j] = max(sqrt(pow(x[i]-x[j], 2.0) + pow(y[i]-y[j], 2.0) + pow(z[i]-z[j], 2.0)) - r[i] - r[j], 0.0);
        }
        // prim
        rep(i, n) {
            mincost[i] = INF;
            used[i] = false;
        }
        mincost[0] = 0;
        double res = 0;

        while(true) {
            int v = -1;
            rep(u, n) {
                if(!used[u] && (v==-1 || mincost[u] < mincost[v])) v = u;
            }
            if(v == -1) break;
            used[v] = true;
            res += mincost[v];

            rep(u, n) {
                mincost[u] = min(mincost[u], cost[v][u]);
            }
        }
        printf("%.3lf\n", res);
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1905345

反省

• プリム法が蟻本を見ないと書けなかった

クラスカルでも解いた

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

struct UnionFind {
  vector<int> par;
  vector<int> rank;

  UnionFind(int n) : par(n), rank(n, 1) {
    for(int i=0; i<n; ++i) par[i] = i;
  }

  int find(int x) {
    if (x == par[x]) return x;
    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]) swap(x, y);
    par[y] = x;
    rank[x] += rank[y];
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

typedef double Cost;

struct edge{
    int src, dst; Cost cost;
    edge(int s, int t, Cost c) : src(s), dst(t), cost(c) {}
    bool operator < (const edge &rhs) const {return cost < rhs.cost;}
};

Cost kruskal(int V, vector<edge> &edges) {
    UnionFind uf(V);
    sort(edges.begin(), edges.end());
    Cost ans = 0;
    for(auto e : edges) {
        if(!uf.same(e.src, e.dst)) {
            uf.unite(e.src, e.dst);
            ans += e.cost;
        }
    }
    return ans;
}

int main(void) {
    int n;
    while(cin >> n && n) {
        vector<double> x(n), y(n), z(n), r(n);
        vector<edge> edges;
        REP(i, n) {
            cin >> x[i] >> y[i] >> z[i] >> r[i];
        }
        REP(i, n)  {
            REP(j, n) {
                if(i == j) continue;
                double c = sqrt(pow(x[i]-x[j], 2.0) + pow(y[i]-y[j], 2.0) + pow(z[i]-z[j], 2.0)) - r[i] - r[j];
                edges.push_back(edge(i, j, max(0.0, c)));
            }
        }
        printf("%.3f\n", kruskal(n, edges));
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2099226

AOJ 1188: Hierarchical Democracy

問題

Hierarchical Democracy | Aizu Online Judge

• [[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]という形で与えられる選挙区の区割りから、当選するために必要な最低得票数を求めよ
• [99]とある場合はその選挙区に99人の有権者がおり、過半数の得票を得ると1段階目の選挙区で勝利する。（有権者数が奇数であることは保証される）
• [[99][59][63][85][51]]とあるときは5つの選挙区があり、過半数の選挙区で勝利するとその2段階目の選挙区で勝利する（選挙区数が奇数であることが保証される）
• [[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]とあるときは3つの2段階目の選挙区があり、過半数の2段階目の選挙区で勝利すると勝利する（奇数であることは保証される）
• このような階層構造がある中で、一番上の段階で勝利すると全体で当選することができる

方針

• [99]のように数字のみが入っている場合は過半数n/2+1票取るのが最小
• [[3][5][7]]のように2段階あるときは各選挙区の過半数をソートして少ないものからn/2+1選挙区分足すのが最小
• [[[1][3][5]][[3][5][7]][[5][7][9]]]のように3段階以上あるときは、まず内側の選挙区について最小を求め、[[3][5][7]]のように潰して2段階の場合に帰着させる
• 構文解析っぽいので構文解析 Howto · GitHubを参考にした

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int getNumber(string& s, int* i) {
    int n = 0;
    while(s[(*i)] != ']') {
        n *= 10;
        n += s[*i]-'0';
        (*i)++;
    }
    return n;
}

int analyze(string& s, int* i) {
    if(s[(*i)] != '[') {
        cerr << "error!" << endl;
        return -1;
    }
    if(s[++(*i)] != '[') {
        return getNumber(s, i)/2 + 1;
    }
    vector<int> a;
    while(s[(*i)] == '[') {
        a.push_back(analyze(s, i));
        (*i)++;
    }
    sort(a.begin(), a.end());
    int ans = 0;
    rep(k, a.size()/2+1) ans += a[k];
    return ans;
}

int main(void){
    int n;
    string s;
    getline(cin, s);
    sscanf(s.c_str(), "%d", &n);
    rep(data, n) {
        getline(cin, s);
        int i = 0;
        cout << analyze(s, &i) << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1904350

反省

• カッコの内容を抜き出す方法とかがよく分からなかったので構文解析の方法をかなり見てしまった
• 最初のnの読み込みはcin.ignore()でOK
• エイヤでやったら一発ACして楽しかった

AOJ 1149: Cut the Cake

問題

Cut the Cake | Aizu Online Judge

• 大きさwxdのケーキをn回切り分ける
• 入力はp, sという形で与えられ、p番目のピースの左上から時計回りにs進んだところを起点に垂直に切断する
• ピースの番号はカットが終わるたびに出来たのが古い順、出来たのが同じなら小さい順に振られる
• 面積が小さい順に各ピースの面積を表示

方針

• 上のルールに従った切断をそのまま書く
• 番号を簡単に振るために<演算子をオーバーロードする
• 面積による比較関数を使って最後の並び替えもsort()だけで出来るようにする

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

class cake {
public:
    int b, w, d;
    cake(int birth, int width, int depth)
        : b(birth), w(width), d(depth) {}
    bool operator<(const cake& r) const {
        if(b != r.b) return b < r.b;
        else return w*d < r.w*r.d;
    }
};

bool compare_area(const cake& r, const cake& l) {
    return r.w*r.d < l.w*l.d;
}

int main(void){
    vector<cake> C;
    int n, w, d, p, s;
    while(cin >> n >> w >> d && w && d) {
        C.clear();
        C.push_back(cake(0, w, d));
        rep(i, n) {
            cin >> p >> s;
            p--;
            sort(C.begin(), C.end());
            s = s%(C[p].w+C[p].d);
            if(s < C[p].w) {
                C.push_back(cake(i+1, C[p].w-s, C[p].d));
                C[p] = cake(i+1, s, C[p].d);
            } else {
                s -= C[p].w;
                C.push_back(cake(i+1, C[p].w, C[p].d-s));
                C[p] = cake(i+1, C[p].w, s);
            }
        }
        sort(C.begin(), C.end(), compare_area);
        rep(i, n) cout << C[i].w*C[i].d << " ";
        cout << C[n].w*C[n].d << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1904076

反省

合ってるはずなのにずっとWAだったから、一度全消去してから書き直したら通った（2回目）

AOJ 1144: Curling 2.0

問題

Curling 2.0 | Aizu Online Judge

• カーリングっぽいゲームを10回以内でクリアできるか調べよ

方針

• シミュレーションして10回以内にクリアできるか調べる
• 障害物にぶつかったら消去するという盤面変化を記録する方法がbfsだと思いつかなかったのでdfsして最小値を求めることにした

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int w, h, a[21][21];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, 1, -1, 0};

int INF = numeric_limits<int>::max();

int dfs(int y, int x, int cnt) {
    if(cnt == 10) return INF;
    int ret = INF;
    rep(i, 4) {
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(ny<0 || ny>=h || nx<0 || nx>=w ||
           a[ny][nx] == 1) continue;
        while(ny>=0 && ny<h && nx>=0 && nx<w) {
            if(a[ny][nx] == 3) {
                ret = min(ret, cnt+1);
                break;
            }
            if(a[ny][nx] == 1) {
                a[ny][nx] = 0;
                ret = min(ret, dfs(ny-dy[i], nx-dx[i], cnt+1));
                a[ny][nx] = 1;
                break;
            }
            ny += dy[i];
            nx += dx[i];
        }
    }
    return ret;
}

int main(void){
    while(cin >> w >> h && w && h) {
        rep(i, h) rep(j, w) cin >> a[i][j];
        rep(i, h) rep(j, w) if(a[i][j]==2) {
            int ans = dfs(i, j, 0);
            if(ans==INF) cout << -1 << endl;
            else cout << ans << endl;
        }
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1903131

反省

NEW GAME!放送までに間に合わせようと焦っていた間はWAだったが、NEW GAME!を見終わって新入社員の気持ちでイチから書き直したらACした。何が悪かったのか分からない。

AOJ 2400: You Are the Judge

問題

You Are the Judge | Aizu Online Judge

提出ログから求まる順位の順に、ID・正解数・ペネルティを表示せよ

方針

AOJ 1187: ICPC Ranking - はやくプロになりたいとほぼ同じ

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
class status {
public:
    int miss[11], solve, time, id;
    bool operator<(const status & rhs) const{
        if(solve > rhs.solve) return true;
        else if(solve==rhs.solve && time < rhs.time) return true;
        else if(solve==rhs.solve && time == rhs.time && id < rhs.id) return true;
        return false;
    }
};

status a[51];

int main(void){
    int T, P, R;
    int team, prob, time;
    string msg;
    while(cin >> T >> P >> R && T) {
        rep(i, 52) {
            a[i].solve = a[i].time = 0;
            a[i].id = i+1;
            rep(j, 11) a[i].miss[j] = 0;
        }
        rep(i, R) {
            cin >> team >> prob >> time >> msg;
            team--;
            if(msg == "CORRECT") {
                a[team].solve++;
                a[team].time += a[team].miss[prob]*1200+time;
            } else {
                a[team].miss[prob]++;
            }
        }
        sort(a, a+T);
        rep(i, T) cout << a[i].id << " "<<  a[i].solve << " " << a[i].time << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1902008

反省

演算子オーバーロードを何も見ずに書けるようにならねば。

AOJ 1007: JPEG Compression

問題

JPEG Compression | Aizu Online Judge

NxNのマスをジグザグに走査するとき、各マスにアクセスする順番を求めよ

方針

• 合計sumになる(y,x)の組ごとに考える
• sumが偶数なら右上に、奇数なら左下に進んでいく
• 次に進むマスが範囲外ならsumの偶奇とnとの関係に気をつけてsum+1における最初のマスに移動する

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int a[10][10];
int main(void){
    int n, c=1;
    while(cin >> n && n) {
        int idx = 1;
        int x = 1;
        int y = 0;
        int d = 1;
        a[0][0] = 1;
        for(int sum = 1; sum <= 2*n-2; ++sum) {
            for(;;) {
                a[y][x] = ++idx;
                if(y==n-1 && x==n-1) break;
                if(sum%2==0) {x++; y--;}
                else {x--; y++;}
                if(x < 0 || y < 0 || x >= n || y >= n) break;
            }
            if(sum < n-1) {
                if(sum%2==1) {x=0; y=sum+1;}
                else {y=0; x=sum+1;}
            } else {
                if(sum%2==1) {y=n-1; x=sum+1-y;}
                else {x=n-1; y=sum+1-x;}
            }
        }
        printf("Case %d:\n", c);
        rep(i, n) {
            rep(j, n) {
                if(a[i][j]>=100) cout << a[i][j];
                else if(a[i][j]>=10) cout << " " << a[i][j];
                else cout << "  " << a[i][j];
            }
            cout << endl;
        }
        c++;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1901570

反省

• 意外とジグザグの処理に手間取った
• すごいコードはすごい（分かりやすいのだとhttp://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=187849#1）

AOJ 0101: Aizu PR

問題

Aizu PR | Aizu Online Judge

文字列中の"Hoshino"を"Hoshina"に書き換えろ

方針

"Hoshino"という文字列があったら最後の文字を'a'にする

置換関数を使わずに書く練習ということで。

cin >> nした後にgetline(cin, s)すると変な挙動をしたので、数字もgetlineした後数字に変換する仕様にした

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int main(void){
    int n;
    string h = "Hoshino";
    string s;
    cin >> n;
    getline(cin, s);
    stringstream ss(s);
    ss >> n;
    rep(loop, n) {
        getline(cin, s);
        rep(i, s.size()){
            if(i+h.size()-1 >= s.size()) break;
            bool same = true;
            rep(j, h.size()) {
                if(s[i+j]!=h[j]) {
                    same = false;
                    break;
                }
            }
            if(same) s[i+h.size()-1] = 'a';
        }
        cout << s << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1899752

反省

境界チェックを怠ってREした