2017-07-03

Typical DP Contest D - サイコロ

競プロ AtCoder TDPC

問題文

解法

サイコロの出た目の積の素因数には 2, 3, 5 しかない．
つまり，D にそれ以外の素因数があればダメ．
そうでなければ，D = 2^a * 3^b * 5^c と一意的に表すことができる．
dp[x][y][z] := 今現在，2の素因数が x 個，3 の素因数が y 個，5 の素因数が z 個となる確率
というDPテーブルを考えれば，そこからもう一つサイコロを投げた時の遷移が簡単に書ける．
計算量は O(Nabc) となる．
N <= 100 だが，a, b, c はもっと小さいので余裕で間に合う．（2 ^ 64 で 10^18 を超えてしまう）

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template<typename T>
std::vector<T> table(int n, T v) { return std::vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return std::vector<decltype(val)>(n, std::move(val));
}

constexpr int dx[6] = {0, 1, 0, 2, 0, 1};
constexpr int dy[6] = {0, 0, 1, 0, 0, 1};
constexpr int dz[6] = {0, 0, 0, 0, 1, 0};

int main() {
    cout << fixed << setprecision(10);

    ll n, d; cin >> n >> d;

    vector<int> cnt;
    for(auto const v : {2, 3, 5}) {
        int c = 0;
        while(d % v == 0) {
            d /= v;
            ++c;
        }
        cnt.push_back(c);
    }
    if(d != 1) {
        cout << 0 << endl;
        return 0;
    }

    auto dp = table(cnt[0] + 1, cnt[1] + 1, cnt[2] + 1, 0.0);
    dp[0][0][0] = 1;
    for(int lp = 0; lp < n; ++lp) {
        auto nxt = table(cnt[0] + 1, cnt[1] + 1, cnt[2] + 1, 0.0);
        for(int x = 0; x <= cnt[0]; ++x) {
            for(int y = 0; y <= cnt[1]; ++y) {
                for(int z = 0; z <= cnt[2]; ++z) {
                    for(int i = 0; i < 6; ++i) {
                        const int nx = min(cnt[0], x + dx[i]);
                        const int ny = min(cnt[1], y + dy[i]);
                        const int nz = min(cnt[2], z + dz[i]);
                        nxt[nx][ny][nz] += dp[x][y][z] / 6;
                    }
                }
            }
        }
        dp = move(nxt);
    }

    cout << dp[cnt[0]][cnt[1]][cnt[2]] << endl;
}

2017-07-03

Typical DP Contest C - トーナメント

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament

解法

まず各山について考える．たとえば，8人いるなら [0, 7], [0, 3], [4, 7], [0, 1], … などが各山にあたる．
ある山 X に属する個人が，X の中で優勝する確率と，次に X が対戦することになる山 Y の同様の確率が求まるとする．
すると，山 X と Y を統合した山 Z について，Z の中で X および Y に属する個人が勝利する確率を求めることができる．
これをループあるいは再帰で実装すればよい．

計算量は O(K * 2^(2K))．

ソースコード

#include <bits/stdc++.h>
using namespace std;

double calc_prob(double r1, double r2) {
    return 1.0 / (1 + pow(10, (r2 - r1) / 400));
}

int main() {
    cout << fixed << setprecision(10);

    int k; cin >> k;
    vector<int> R(1 << k);
    for(auto& x : R) cin >> x;

    function<vector<double>(int, int)> solve = [&] (int l, int r) {
        if(r - l == 1) {
            return vector<double>{1.0};
        }
        vector<double> res(r - l);
        const int sz = (r - l) / 2;
        auto l_res = solve(l, l + sz), r_res = solve(l + sz, r);
        for(int i = 0; i < sz; ++i) {
            for(int j = 0; j < sz; ++j) {
                res[i] += calc_prob(R[l + i], R[l + j + sz]) * l_res[i] * r_res[j];
                res[j + sz] += calc_prob(R[l + j + sz], R[l + i]) * l_res[i] * r_res[j];
            }
        }
        return res;
    };

    for(auto&& ans : solve(0, 1 << k)) {
        cout << ans << endl;
    }
}

2017-07-03

Typical DP Contest B - ゲーム

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_game

解法

漸化式的にも解けるが，メモ化再帰で書くほうがわかりやすいかもしれない．
この場合，minimax法でやる．
dp[l][r] := 左の一番上が l 枚目，右の一番上が r 番目の状態から始めた時の，(その瞬間の)先手の得点 - 後手の得点の最大値
としてメモ化再帰する．
答えは sum を全カードの総和として (sum + dp[0][0]) / 2 で求まる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int inf = 1e9;

int main() {
    int A, B; cin >> A >> B;
    vector<int> a(A), b(B);
    for(auto& x : a) cin >> x;
    for(auto& x : b) cin >> x;

    const int sum = accumulate(a.begin(), a.end(), 0) + accumulate(b.begin(), b.end(), 0);

    vector<vector<int>> dp(A + 1, vector<int>(B + 1, -inf));
    function<int(int, int)> rec = [&] (int l, int r) {
        if(dp[l][r] != -inf) return dp[l][r];
        if(l == A && r == B) return dp[l][r] = 0;

        int& res = dp[l][r];
        if(l != A) res = a[l] - rec(l + 1, r);
        if(r != B) res = max(res, b[r] - rec(l, r + 1));
        return res;
    };

    cout << (sum + rec(0, 0)) / 2 << endl;
}

2017-07-02

Typical DP Contest A - コンテスト

競プロ AtCoder TDPC

問題文

http://tdpc.contest.atcoder.jp/tasks/tdpc_contest

解法

基本的なナップサック問題．
p(i), N <= 100 なので，高々 10^6 のループで終わる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int max_p = 10000;

int main() {
    int n; cin >> n;
    vector<int> p(n);
    for(auto& x : p) cin >> x;

    vector<bool> dp(max_p + 1);
    dp[0] = true;
    for(int i = 0; i < n; ++i) {
        for(int j = max_p - p[i]; j >= 0; --j) {
            dp[j + p[i]] = dp[j + p[i]] | dp[j];
        }
    }

    cout << count(dp.begin(), dp.end(), true) << endl;
}

2017-07-02

Typical DP Contest まとめ

競プロ AtCoder TDPC

Typical DP Contest - Typical DP Contest | AtCoder

Typical DP Contest の全ての問題の解法を書いていきたい．

・2017/08/27
無事全部解き切りました．一部の問題は自力で解けなかったけど．

2017-06-28

AOJ 1359 Wall Clocks

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1359

解法

各点から半直線が2本出て，長方形の周上の2点で交わるが，それをそのまま処理すると面倒．
なので，(0, 0) -> (0, d) -> (w, d) -> (w, 0) -> (0, 0) という4辺を展開して，[0, 2(w+d)] という数直線上の区間にしてしまうと楽になる．
半直線は 45度なので，展開後の座標は簡単な計算により求まる．
各点 i から見える範囲が [li, ri] とすると，ri の昇順にソートしてやるとよい．最初にどこに時計を置くかを決めれば，あとは時計回り（つまり数直線の右方向）に，置いた時計が見えなくなるまで飛ばして，見えなくなったら追加することで解が得られる．
あとは，最初に時計を置く位置を全探索すれば最適解が求まる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int n, w, d;
    cin >> n >> w >> d;
    vector<pii> v;
    for(int i=0; i<n; ++i) {
        int x, y;
        char f;
        cin >> x >> y >> f;
        if(f == 'W') {
            v.emplace_back(x + y, -x + y);
        } else if(f == 'N') {
            v.emplace_back(2*d + x - y, x + y);
        } else if(f == 'E') {
            v.emplace_back(2*(d+w) - x - y, 2*d + x - y);
        } else {
            v.emplace_back(2*(d+w) - x + y ,2*(d+w) - x - y);
        }
    }
    sort(v.begin(), v.end());
    int L = 2*(w + d);
    int res = 1e9;
    for(int i=0; i<n; ++i) {
        auto tmp = v;
        for(int j=i-1; j>=0; --j) {
            if(tmp[j].first < tmp[i].first) {
                tmp[j].first += L;
                tmp[j].second += L;
            }
        }
        sort(tmp.begin(), tmp.end());
        int cnt = 1;
        int now = tmp[0].first;
        for(int j=0; j<n; ++j) {
            if(tmp[j].second > now) {
                now = tmp[j].first;
                cnt++;
            }
        }
        res = min(res, cnt);
    }
    cout << res << endl;
}

2017-06-27

AOJ 1348 Space Golf

競プロ AOJ

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1348

解法

完全にやるだけ．多少無駄なことをしても入力サイズが小さいので余裕で通る．
ご丁寧に式が書かれているので，それに従って候補を全部列挙し，それらが条件をみたすか（つまり接触しないか）を判定する．条件をみたす中で最小の値が答え．

明らかに最適なのは vx = vy となるときで，これでうまくいかないならどれかに接触してしまうということ．その時は，接触するギリギリを全て試してみて，その中で条件を満たし，かつ最小の値を求める．

g = 9.8 じゃないので注意．

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr double INF = 1e9;
constexpr double eps = 1e-8;

int main() {
    double d;
    int n, b;
    cin >> d >> n >> b;
    vector<double> p(n), h(n);
    for(int i=0; i<n; ++i) {
        cin >> p[i] >> h[i];
    }
    double res = INF;
    for(int i=0; i<=b; ++i) {
        double interval = d / (i+1);
        bool neg = false;
        for(int j=0; j<=i; ++j) {
            for(int i=0; i<n; ++i) {
                neg |= abs(interval * j - p[i]) < eps;
            }
        }
        if(neg) {
            continue;
        }
        vector<double> vx, vy;
        vx.push_back(sqrt(interval / 2));
        vy.push_back(vx.back());
        for(int j=0; j<=i; ++j) {
            double now = interval * j;
            for(int k=0; k<n; ++k) {
                double pp = p[k] - now;
                if(0 < pp && pp < interval) {
                    vx.push_back(sqrt(1 / (2*h[k]) * pp * (interval - pp)));
                    vy.push_back(interval / (2 * vx.back()));
                }
            }
        }
        for(int j=0; j<vx.size(); ++j) {
            bool ok = true;
            for(int k=0; k<=i; ++k) {
                double now = interval * k;
                for(int l=0; l<n; ++l) {
                    double pp = p[l] - now;
                    if(0 < pp && pp < interval) {
                        double t = pp / vx[j];
                        double hh = vy[j] * t - 0.5 * t*t;
                        ok &= (hh - h[l]) >= -eps;
                    }
                }
            }
            if(ok) {
                res = min(res, hypot(vx[j], vy[j]));
            }
        }
    }
    cout << fixed << setprecision(10) << res << endl;
}