読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

JAG模擬国内予選2016B (A-D)

チームMusyoku(ソロ)で参加し,4完で全チーム中24位でした.

模擬国内Aのときは自力では2完だったので,少しは解けるようになったかな.

A. カレー作り

式変形して,実行可能な最小の解xをループで求める.

(コードについて)本当はyの符号だけわかればよいのでcで割る必要はなかった.

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int r0, w0, c, r;
    while (cin >> r0 >> w0 >> c >> r, r0) {
        rep(x, 100000) {
            double y = 1. * (r0 + x * r - c * w0) / c;
            if (y >= 0) {
                cout << x << endl;
                break;
            }
        }
    }
}

B. jfen

簡単な構文解析(?)の問題.

変更されるのはスワップ対象の行だけだが,うまくやろうとするよりもまとめてjfen→盤面→jfenとした方が早そうだったのでそうした.

vector<string> getBoard(string s) {
    vector<string> t;
    stringstream ss(s);
    string line;
    while (getline(ss, line, '/')) {
        string temp = "";
        for (auto c : line) {
            if (c == 'b') {
                temp += 'b';
            } else {
                rep(i, c - '0') temp += '.';
            }
        }
        t.emplace_back(temp);
    }
    return t;
}

string make(vector<string> t) {
    string s = "";
    int cnt = 0;
    for (auto l : t) {
        cnt++;
        int n = 0;
        for (auto c : l) {
            if (c == 'b') {
                if (n > 0) {
                    s += n + '0';
                    n = 0;
                }
                s += 'b';
            } else {
                n++;
            }
        }
        if (n > 0) {
            s += n + '0';
            n = 0;
        }
        if (cnt < t.size()) s += '/';
    }

    return s;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    string s;
    while (cin >> s, s[0] != '#') {
        auto t = getBoard(s);

        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--, c--, d--;
        swap(t[a][b], t[c][d]);
        
        cout << make(t) << endl;
    }

}

C. カーテン

問題

  • 窓: 各辺がx軸またはy軸に平行であるようなN角形(自己交差を持たないが,凸とは限らない)
  • カーテン: 各辺がx軸またはy軸に平行であるような長方形

窓に含まれ,カーテンに含まれない部分の面積を求めよ.

制約

1 <= N <= 100

窓とカーテンの頂点のx, y座標: -20000 <= x, y <= 20000, x, y は整数

解法

窓は凸多角形とは限らないので,簡単に共通部分を求めることはできそうにない.

愚直な方法として,平面上の各1*1のマスについて窓/カーテンに含まれるかの内外判定を行い,「窓に含まれカーテンに含まれない」を満たすものの個数を数えるという方法がある.「マス」は左下の座標を(x, y)として,中心の座標(x + 0.5, y + 0.5)を用いれば点として表現でき,多角形と点の内外判定に帰着することが可能である.ただしこれではマスの数が40000 * 40000 = 1.2 * 109 個あり, 内外判定にO(N)*1かかるので全体で1011回程度の計算回数となり間に合わない.

しかし,実際現れる点の個数は高々104個であるから,x座標,y座標の種類も高々104個ずつであることがわかる.そこで座標圧縮を用いる.圧縮された座標系の各マスを調べれば104*104なので,内外判定と合わせて106回程度の計算でできる.

ただし,圧縮された座標系における1マスの面積は1とは限らないことに注意.(x座標の差) * (y座標の差) を復元する必要がある.

typedef complex<double> P;
typedef vector<P> G;
#define here(g, i) g[i]
#define next(g, i) g[(i + 1) % g.size()]
#define prev(g, i) g[(i - 1 + g.size()) % g.size()]
const double EPS = 1e-10;
const double INF = 1e12;

struct L {
    P a, b, v;
    L(){}
    L(P _a, P _b) : a(_a), b(_b), v(b - a) {}
    L(double _ax, double _ay, double _bx, double _by) : L(P(_ax, _ay), P(_bx, _by)) {}
};

double cross(P a, P b) {
    return imag(conj(a) * b);
}

double dot(P a, P b) {
    return real(conj(a) * b);
}

enum { OUT, ON, IN };
int containPG(const P& p, const G& g) {
    int n = g.size();
    bool in = false;
    rep(i, n) {
        P a = here(g, i) - p, b = next(g, i) - p;
        if (a.imag() > b.imag()) swap(a, b);
        if (a.imag() <= 0 && 0 < b.imag() && cross(a, b) > 0) in = !in;
        if (cross(a, b) == 0 && dot(a, b) <= 0) return ON;
    }
    return in ? IN : OUT;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N;
    while (cin >> N, N) {
        map<int, int> mpx, mpy;
        map<int, int> rmpx, rmpy;

        vector<int> x(N), y(N);
        rep(i, N) {
            cin >> x[i] >> y[i];
            mpx[x[i]] = 0;
            mpy[y[i]] = 0;
        }
        vector<int> a(4), b(4);
        rep(i, 4) {
            cin >> a[i] >> b[i];
            mpx[a[i]] = 0;
            mpy[b[i]] = 0;
        }

        int numx = 0;
        for (auto p : mpx) {
            mpx[p.first] = numx;
            rmpx[numx] = p.first;
            numx++;
        }

        int numy = 0;
        for (auto p : mpy) {
            mpy[p.first] = numy;
            rmpy[numy] = p.first;
            numy++;
        }

        vector<int> X(N), Y(N);
        rep(i, N) {
            X[i] = mpx[x[i]];
            Y[i] = mpy[y[i]];
        }

        vector<int> A(4), B(4);
        rep(i, 4) {
            A[i] = mpx[a[i]];
            B[i] = mpy[b[i]];
        }

        G g1;
        rep(i, N) {
            g1.emplace_back(P(1. * X[i], 1. * Y[i]));
        }

        G g2;
        rep(i, 4) {
            g2.emplace_back(P(1. * A[i], 1. * B[i]));
        }

        int ans = 0;
        rep(i, numx - 1) {
            rep(j, numy - 1) {
                P p(1. * i + 0.5, 1. * j + 0.5);
                if (containPG(p, g1) && !containPG(p, g2)) {
                    ans += (rmpx[i + 1] - rmpx[i]) * (rmpy[j + 1] - rmpy[j]);
                }
            }
        }

        cout << ans << endl;

    }

}

D. 夏合宿の朝は早い

問題

N人の人について,人iが寝坊する確率p_iが与えられる.

また,人iはm_i個の連絡先を知っており,それらはそれぞれ人a_i1, a_i2, ..., a_imのものである.

人iが起きたとき,人iは自分が連絡先を知っているすべての相手を起こす.このとき起こされた人は同様に,自分が連絡先を知っているすべての相手を起こす.

このとき,全員が起きられる確率を求めよ.

制約

1 <= N <= 100

解法

人を頂点,「人iが人jの連絡先を知っている」ことをi->jの有向辺で表した有向グラフGを考える.

まず,GがDAGである場合を考える.入次数 = 0 の人は誰にも起こしてもらえないので,必ず自力で起きなければならない.一方,入次数 = 0 の人が全員起きさえすれば,GはDAGであるから他のすべての人は起こされる.よって全ての人が起きられる確率は,入次数 = 0である人についてp_iを掛け合わせたものである.

次に,GがDAGでない場合を考える.Gを強連結成分分解し,各強連結成分を1つの頂点にまとめたグラフをG'とする.G'はDAGであるからGと同様の議論を当てはめることができる.よって全員が起きる確率は,入次数 = 0 である強連結成分C_iについて,"C_iが起きる確率"を掛け合わせたものである.

では,強連結成分C_iが起きる確率とは何であろうか.実は,強連結成分内の頂点については,全員が起きるか全員が寝坊するかのどちらかしかない.なぜなら1人が起きればその1人から強連結成分内の全員に到達可能だからである.よってグラフ全体の全員が起きるには,入次数 = 0 である強連結成分において,それぞれ少なくとも1人が起きればよい.

以上より,求める確率は,

「自身に含まれない頂点からの入次数 = 0である強連結成分について,1 - (強連結成分内の全員が寝坊する確率) を掛け合わせたもの」

である.

僕は強連結成分分解のライブラリを持っていなかったので,全点対についてbfsしてiからjに到達可能かつjからiに到達可能であれば同じ強連結成分にする(UnionFind),という方法を取りました.制約に甘えた.*2

class UnionFind {
private:
    int n;
    vector<int> uni;
public:
    UnionFind(int _n) {
        n = _n;
        uni.clear();
        uni.resize(n, -1);
    }
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

bool reachable(const VV &G, int s, int g) {
    int N = G.size();
    const int INF = 1e9;
    V d(N, INF);
    queue<int> que;
    que.push(s);
    d[s] = 0;

    while (!que.empty()) {
        int pre = que.front(); que.pop();
        if (pre == g)
             break;

        for (auto nxt: G[pre]) {
            if (d[nxt] == INF) {
                que.push(nxt);
                d[nxt] = d[pre] + 1;
            }
        }
    }

    return d[g] < INF;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N;
    while (cin >> N, N) {
        vector<double> pr(N);
        VV G(N);
        rep(i, N) {
            int m;
            cin >> pr[i] >> m;
            rep(j, m) {
                int x;
                cin >> x;
                x--;
                G[i].emplace_back(x);
            }
        }

        UnionFind uf(N);
        rep(j, N) {
            rep(i, j) {
                if (reachable(G, i, j) && reachable(G, j, i)) {
                    uf.unite(i, j);
                }
            }
        }

        map<int, bool> existIn;
        rep(i, N) existIn[uf.root(i)] = false;
        rep(from, N) {
            for (auto to : G[from]) {
                if (!uf.same(from, to)) existIn[uf.root(to)] = true;
            }
        }

        double ans = 1;
        for (auto p : existIn) {
            if (!p.second) {
                double temp = 1;
                rep(i, N) {
                    if (uf.root(i) == p.first) {
                        temp *= pr[i];
                    }
                }
                ans *= 1. - temp;
            }
        }

        printf("%.10f\n", ans);

    }
}

まとめ

作っておいた幾何のライブラリが役に立ってよかった.

強連結成分のライブラリも作ろう.

*1:点から半直線を引いて,交差回数の偶奇で判定するやつ

*2:実装が悪すぎてO(V^2 E)になっています (手元では4秒程度かかってた)