AOJ 1181: Biased Dice

問題

Biased Dice | Aizu Online Judge

  • サイコロがある場所に積まれていき、転がり落ちることができる場合は6, 5, 4という優先順位でその目の方向に転がる
  • ルールに従ってサイコロを転がしていった時に見えるサイコロについて、1〜6の目がいくつずつ上を向いているか調べよ
  • 入力として、積まれるサイコロの上面の目(t)と前面の目(f)の組がn個与えられる

方針

  • 頑張ってシミュレーションする
  • 6, 5, 4の目について[t][f]を与えたときにどちらの方向にあるかを求める配列を用意する
  • 優先順位に従って転がしていき、各場所の高さとサイコロのt, fを更新していく

コード

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

#define NO 0
#define UP 1
#define RIGHT 2
#define LEFT 3
#define DOWN 4

int h[201][201], face[201][201];
const int six[7][7] = {
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, UP, NO, LEFT, RIGHT, NO, DOWN},
    {NO, UP, RIGHT, NO, NO, LEFT, DOWN},
    {NO, UP, LEFT, NO, NO, RIGHT, DOWN},
    {NO, UP, NO, RIGHT, LEFT, NO, DOWN},
    {NO, NO, NO, NO, NO, NO, NO}
};
const int five[7][7] = {
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, UP, RIGHT, LEFT, DOWN, NO},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, LEFT, UP, NO, NO, DOWN, RIGHT},
    {NO, RIGHT, UP, NO, NO, DOWN, LEFT},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, UP, LEFT, RIGHT, DOWN, NO}
};
const int four[7][7] = {
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, LEFT, UP, DOWN, RIGHT, NO},
    {NO, RIGHT, NO, UP, DOWN, NO, LEFT},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, NO, NO, NO, NO, NO, NO},
    {NO, LEFT, NO, UP, DOWN, NO, RIGHT},
    {NO, NO, RIGHT, UP, DOWN, LEFT, NO}
};
int main(void){
    int n;
    while(cin >> n && n) {
        int t, f;
        rep(i, 201) rep(j, 201) {h[i][j] = 0; face[i][j] = -1;}
        rep(i, n) {
            cin >> t >> f;
            t; f;
            int x = 100, y = 100;
            int nx, ny;
            h[y][x]++;
            bool fall = true;
            while(fall) {
                nx = x;
                ny = y;
                fall = false;
                if(six[t][f] == UP && h[y+1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y+1;
                    f = 7-t; t = 1; 
                } else if(six[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) {
                    fall = true;
                    nx = x+1;
                    t = 1;
                } else if(six[t][f] == LEFT && h[y][x-1] < h[y][x]-1) {
                    fall = true;
                    nx = x-1;
                    t = 1;
                } else if(six[t][f] == DOWN && h[y-1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y-1;
                    f = t; t = 1; 
                } else if(five[t][f] == UP && h[y+1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y+1;
                    f = 7-t; t = 2;
                } else if(five[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) {
                    fall = true;
                    nx = x+1;
                    t = 2;
                } else if(five[t][f] == LEFT && h[y][x-1] < h[y][x]-1) {
                    fall = true;
                    nx = x-1;
                    t = 2;
                } else if(five[t][f] == DOWN && h[y-1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y-1;
                    f = t; t = 2;
                } else if(four[t][f] == UP && h[y+1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y+1;
                    f = 7-t; t = 3;
                } else if(four[t][f] == RIGHT && h[y][x+1] < h[y][x]-1) {
                    fall = true;
                    nx = x+1;
                    t = 3;
                } else if(four[t][f] == LEFT && h[y][x-1] < h[y][x]-1) {
                    fall = true;
                    nx = x-1;
                    t = 3;
                } else if(four[t][f] == DOWN && h[y-1][x] < h[y][x]-1) {
                    fall = true;
                    ny = y-1;
                    f = t; t = 3;
                }
                if(fall) {
                    h[y][x]--;
                    h[ny][nx]++;
                    x = nx; y = ny;
                }
                else {
                }
            }
            face[y][x] = t;
        }
        int ans[6] = {};
        rep(i, 201) rep(j, 201) {if(face[i][j] != -1) ans[face[i][j]-1]++;}
        cout << ans[0];
        rep(i, 5) cout << " " << ans[i+1];
        cout << endl;
    }
}

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

反省

  • コードが汚い

AOJ 1174: Identically Colored Panels Connection

問題

Identically Colored Panels Connection | Aizu Online Judge

  • 電気を流すと隣接した同じ色のパネルを含めて色が変わるパネルがある
  • 隣接した同じ色のパネルは結合する
  • 左上のパネルに5回電気を流したとき、指定された色で左上と結合している最大のパネル数を求めよ

方針

  • dfsであらゆる変色パターンを試す (6の5乗なので間に合いそう)
  • パネルの変色とパネル数カウントはbfsでやる

コード

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

typedef pair<int, int> P;

int p[10][10], visited[10][10];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int h, w, c;

int dfs(int count) {
    if(count == 5) {
        int ret = 0;
        if(p[0][0] != c) return 0;
        rep(i, 10) rep(j, 10) visited[i][j] = 0;
        queue<P> que;
        que.push(P(0, 0));
        while(!que.empty()) {
            P point = que.front(); que.pop();
            if(visited[point.first][point.second] == 0) {
               visited[point.first][point.second] = 1;
               ret++;
                rep(i, 4) {
                    int ny = point.first + dy[i];
                    int nx = point.second + dx[i];
                    if(nx >= 0 && nx < w && ny >= 0 && ny < h &&
                       visited[ny][nx] == 0 && p[ny][nx] == c) {
                        que.push(P(ny, nx));
                    }
                }
            }
        }
        return ret;
    }
    int org[10][10];
    int ret = 0;
    rep(i, h) rep(j, w) org[i][j] = p[i][j];
    rep(color, 6) {
        int org_c = p[0][0];
        rep(i, 10) rep(j, 10) visited[i][j] = 0;
        queue<P> que;
        que.push(P(0, 0));
        while(!que.empty()) {
            P point = que.front(); que.pop();
            p[point.first][point.second] = color+1;
            visited[point.first][point.second] = 1;
            rep(i, 4) {
                int ny = point.first + dy[i];
                int nx = point.second + dx[i];
                if(nx >= 0 && nx < w && ny >= 0 && ny < h &&
                   visited[ny][nx] == 0 && p[ny][nx] == org_c) {
                    que.push(P(ny, nx));
                }
            }
        }
        ret = max(ret, dfs(count+1));
        rep(i, 10) rep(j, 10) p[i][j] = org[i][j];
    }
    return ret;
}

int main(void){
    while(cin >> h >> w >> c && h) {
        rep(i, h) rep(j, w) cin >> p[i][j];
        cout << dfs(0) << endl;
    }
}

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

反省

  • visitedの処理がうまく書けなくて重複カウントしていてハマった
  • 遅い(1.7s)のは仕方ないのかなと思ったら、同じような解法でもvisitedの更新をしないで済むよう実装すれば0.02sで解けていた(これとか)

AOJ 1155: How can I satisfy thee? Let me count the ways...

問題

How can I satisfy thee? Let me count the ways... | Aizu Online Judge

"true", "false", "unknown"の3種類があるロジックで、与えられた式を満たすP, Q, Rの組み合わせが何種類あるか数えよ

方針

  • P, Q, Rがそれぞれ3通りの値を取るため27通りしかないから全てを評価して満たす場合を数えればよい
  • 再帰下降構文解析をすればよい

コード

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

int formula(string &s, int P, int Q, int R, int &i) {
    if(s[i] == '-') {
        i++;
        return 2-formula(s, P, Q, R, i);
    } else if(s[i] == '(') {
        int X, Y;
        i++;
        X = formula(s, P, Q, R, i);
        if(s[i] == '*') {
            i++;
            Y = formula(s, P, Q, R, i);
            i++;
            if(X == 0) return 0;
            if(X == 1) {
                if(Y == 0) return 0;
                else return 1;
            } else {
                return Y;
            }
        } else {
            i++;
            Y = formula(s, P, Q, R, i);
            i++;
            if(X == 0) return Y;
            if(X == 1) {
                if(Y == 0) return 1;
                else return Y;
            } else {
                return 2;
            }
        }
    } else {
        int ret;
        if(s[i] >= '0' && s[i] <= '2') ret = s[i]-'0';
        else if(s[i] == 'P') ret = P;
        else if(s[i] == 'Q') ret = Q;
        else if(s[i] == 'R') ret = R;
        i++;
        return ret;
    }
}

int main(void){
    string s;
    while(cin >> s && s != ".") {
        int cnt = 0;
        rep(i, 3) rep(j, 3) {
            rep(k, 3) {
                int index = 0;
                if(formula(s, i, j, k, index) == 2) cnt++;
            }
        }
        cout << cnt << endl;
    }
}

反省

  • LL(1)文法のパーサーは初めてだったので手間取った

AOJ 1602: ICPC Calculator

問題

ICPC Calculator | Aizu Online Judge

国際反括弧会議が考えた変な記法に従って計算するプログラムを作れ

  • 各行は入れ子レベルを表す'.'・加算を表す'+'・乗算を表す'*'・整数からなる
  • 式の最初の行は入れ子レベルの数だけの'.'からなる
  • レベルnの演算子はそれ以降の行にあるレベルn+1の式に対して適用される

Lispの記法をイメージすると多分分かりやすくて

+
.2
.3

(+ 2 3)
*
.+
..2
..3
..4
.5

(* (+ 2 3 4) 5)

に対応する

方針

  • 整数のみの式ならその整数を返す
  • レベルnで演算子が来たら、レベルn+1の式全部に対して演算子を適用する
  • 再帰実行すれば何段でも対応できる

コード

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

typedef pair<int, char> P;

int getLevel(string &expr) {
    int ret = 0;
    while(expr[ret] == '.') ret++;
    return ret;
}

bool isdigit(char c) {
    return c >= '0' && c <= '9';
}

int process(vector<string> &expr, int* line) {
    int ret;
    int level = getLevel(expr[*line]);
    if(level == 0 && isdigit(expr[*line][level])) 
        return expr[*line][level]-'0';
    else if(expr[*line][level] == '+') {
        (*line)++;
        ret = 0;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret += expr[*line][new_level]-'0';
                else 
                    ret += process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    } else if(expr[*line][level] == '*') {
        (*line)++;
        ret = 1;
        while((*line) < expr.size()) {
            int new_level = getLevel(expr[*line]);
            if(new_level == level+1) {
                if(isdigit(expr[*line][new_level]))
                    ret *= expr[*line][new_level]-'0';
                else 
                    ret *= process(expr, line);
                (*line)++;
            } else {
                (*line)--;
                break;
            }
        }
        return ret;
    }
}

int main(void){
    int n;
    string s;
    vector<string> expr;
    while(cin >> n && n) {
        cin.ignore();
        expr.clear();
        rep(i, n) {
            getline(cin, s);
            expr.push_back(s);
        }
        int line = 0;
        cout << process(expr, &line) << endl;
    }
}

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

反省

AOJ 1194: Vampire

問題

Vampire | Aizu Online Judge

  • 与えられたビルの位置から、あと何秒間太陽が隠れているか求めよ

方針

  • ビルの位置が整数値なのでビルがある場所についてグリッドを埋めていく
  • 太陽が通りうる位置についてグリッドが埋まっていなかったら太陽が通過する瞬間の時間を求める
  • 全ての埋まっていないグリッドの中で時間の最小値を求める

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
  
int s[21][41];
int main(void){
    int r, n, xl, xr, h;
    while(cin >> r >> n && r) {
        rep(i, 21) rep(j, 41) s[i][j] = 0;
        rep(i, n) {
            cin >> xl >> xr >> h;
            for(int y=0; y<h; ++y) {
                for(int x=xl+20; x<xr+20; ++x) {
                    s[y][x] = 1;
                }
            }
        }
        double mint = numeric_limits<double>::max();
        rep(y, 21) {
            for(int x=-r+20; x<r+20; ++x) {
                if(s[y][x] == 0) {
                    double t;
                    if(x<20) t = (double) y+r-sqrt(pow((double)r,2.0)-pow(x-19.0, 2.0));
                    else t = (double) y+r-sqrt(pow((double)r,2.0)-pow(x-20.0, 2.0));
                    mint = min(mint, t);
                }
            }
        }
        printf("%.4lf\n", mint);
    }
}

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

反省

  • 検索すると2分探索で決めるという解法があり、そのほうが一般的に使える解法だと思った
  • たまたま間違えて配列外アクセスしたら、coutとprintfで挙動が違うという現象に遭遇した

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して楽しかった