2016-07-11

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)文法のパーサーは初めてだったので手間取った

2016-07-09

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

反省

レベルが下がったときの処理を書くのに戸惑った
このくらい短く書けるらしい http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1885506#1

2016-07-08

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で挙動が違うという現象に遭遇した
Wandboxでは再現しなかったけど、僕のPCでは本来Segmentation Faultするべきプログラムがcoutすることでエラーなく実行できる謎の現象が確認された。 https://t.co/vcMM9lxfsn
— 川奈清 (@kivantium) 2016年7月8日

AOJのジャッジサーバでも同様の現象が確認できた。
cout版 (https://t.co/FwCOKJqaCh)→AC
printf版 (https://t.co/MFLFVKrSex)→RE
— 川奈清 (@kivantium) 2016年7月8日

2016-07-07

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

2016-07-07

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

2016-07-07

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回目）

2016-07-06

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した。何が悪かったのか分からない。