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

math314のブログ

主に競技プログラミング,CTFの結果を載せます

code festival 2014 上海

id math で出ていました. 5位で表彰された,やったぜ.

コンテストページ : http://code-festival-2014-china.contest.atcoder.jp/

A問題

難しい訳ではないんだけど,Aにしては実装が重い

http://code-festival-2014-china.contest.atcoder.jp/submissions/305593

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
 
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
 
int main(){
    int n; cin >> n;
    int _n = n;
    int x = 1;
    while (_n--) x *= 10;
    vector<string> vs;
    FOR(i, x) {
        string s;
        int y = i;
        FOR(j, n) {
            int cur = y % 10;
            int upper = y / 10 % 2;
            if (upper) cur = 9 - cur;
            s.push_back('0' + cur);
            y /= 10;
        }
        reverse(s.begin(), s.end());
        vs.push_back(s);
    }
    printf("%d\n", sz(vs) - 1);
    for (auto& a : vs) {
        printf("%s\n", a.c_str());
    }
}

テンプレート部分は以降省略します

B問題

二分探索して|x|+|y|を求めて,後は辻褄を合わせる問題.

http://code-festival-2014-china.contest.atcoder.jp/submissions/305674

int q;
 
ll abs_sum(ll n) {
    ll l = -1, r = ten(9);
    while (r - l != 1) {
        ll md = (l + r) / 2;
        ll val = md * (md + 1) * 2 + 1;
        if (n <= val) r = md;
        else l = md;
    }
    return r;
}
 
int main(){
    cin >> q;
    FOR(i, q) {
        ll n; cin >> n;
        ll abs_xy = abs_sum(n);
        n -= 1 + abs_xy * (abs_xy - 1) * 2;
        n--;
        ll x = (n + 1) / 2 - abs_xy;
        ll y = abs_xy - abs(x);
        if (n % 2 == 1) y = -y;
        cout << x << " " << y << endl;
    }
 
}

C問題

正多角形の頂点が全て格子点上にあるようなものの中で,最も頂点数の多い多角形を出力する問題. ぱっと見,正方形しかなさそうだったので"格子点 多角形"で検索して,wikipediaを見て確信する.

正方形となるような辺は,x,y軸に平行が,45度傾いている物と思い込んでいて2WAした.

http://code-festival-2014-china.contest.atcoder.jp/submissions/306262

typedef pair<Pll, int> P;
 
int main(){
    int n; cin >> n;
    vector<P> vp;
    FOR(i, n) {
        Pll p; cin >> p.first >> p.second;
        vp.emplace_back(p,i+1);
    }
    map<Pll,int> st;
    FOR(i, n) st[vp[i].first] = vp[i].second;
 
    vector<int> anses;
    FOR(i, sz(vp)) {
        for (int j = i + 1; j < sz(vp); j++) {
            Pll& p = vp[i].first;
            Pll& q = vp[j].first;
            ll xdiff = p.first - q.first;
            ll ydiff = p.second - q.second;
 
            Pll r(p.first - ydiff, p.second + xdiff);
            Pll s(q.first - ydiff, q.second + xdiff);
 
            if (st.count(r) && st.count(s)) {
                anses.push_back(st[p]);
                anses.push_back(st[q]);
                anses.push_back(st[r]);
                anses.push_back(st[s]);
            }
            if (sz(anses)) break;
        }
        if (sz(anses)) break;
    }
 
    cout << sz(anses) << endl;
    sort(anses.begin(), anses.end());
    for (auto i : anses) cout << i << endl;
 
}

D問題

どう見てもフローにしか見えなかった,後で聞くとbfsすると解けたらしいが思いつかなかった.

フローを2本流して,経路復元をする方法で解ける.解いている人はフローが多そう?

http://code-festival-2014-china.contest.atcoder.jp/submissions/306143

struct Edge {
    int cap; // capacity
    int to;
    int rev; // reverse edge id
 
    Edge() {}
    Edge(int c, int t, int r) :
        cap(c), to(t), rev(r) {
    }
};
 
struct CostEdge : public Edge {
    int cost;
    CostEdge() : Edge() {}
    CostEdge(int c, int t, int cs, int r) :
        Edge(c, t, r), cost(cs) {
    }
};
 
template<class E> // Edge type
class Graph {
public:
    typedef std::vector<std::vector<E> > G;
 
private:
    G g;
 
public:
    Graph(int n) : g(G(n)) {}
 
    void addEdge(int from, int to, int cap, int cost) {
        g[from].push_back(E(cap, to, cost, g[to].size()));
        g[to].push_back(E(0, from, -cost, g[from].size() - 1)); //rev edge
    }
 
    G &getRowGraph() {
        return g;
    }
};
 
// O(VE+FElogV)
template<class E>
int minCostFlow(Graph<E> &graph, int s, int t, int f, bool negative = false) {
    typedef pair<int, int> P;
    typename Graph<E>::G &g = graph.getRowGraph();
    int n = g.size();
    int res = 0;
    vector<int> h(n, 0);
    vector<int> prevv(n);
    vector<int> preve(n);
    const int inf = 10000000; //check
 
    //負の辺に対応?
    if (negative) {
        vector<int> dist(n, inf);
        dist[s] = 0;
 
        bool update = true;
 
        while (update) {
            update = false;
            for (int v = 0; v < n; v++) {
                if (dist[v] == inf) continue;
                for (int i = 0; i < (int)g[v].size(); i++) {
                    E &e = g[v][i];
                    if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }
 
        for (int i = 0; i < n; i++)
            h[i] = dist[i];
    }
 
    while (f > 0) {
        //ダイクストラで最短経路(cost = 辺の費用)
        priority_queue<P, vector<P>, greater<P> > que;
        vector<int> dist(n, inf);
        dist[s] = 0;
        que.push(P(0, s));
 
        while (!que.empty()) {
            P p = que.top(); que.pop();
            int v = p.second;
            if (dist[v] < p.first) continue;
            for (int i = 0; i < (int)g[v].size(); i++) {
                E &e = g[v][i];
 
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(P(dist[e.to], e.to));
                }
            }
        }
 
        if (dist[t] == inf) {
            return -1; //最短経路なし
        }
 
        for (int v = 0; v < n; v++) h[v] += dist[v];
 
        //s-t間に目一杯流す
        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, g[prevv[v]][preve[v]].cap);
        }
 
        f -= d;//流した分を引く
        res += d * h[t]; //流した分からコストの計算をする
 
        //逆辺の計算
        for (int v = t; v != s; v = prevv[v]) {
            E &e = g[prevv[v]][preve[v]];
            e.cap -= d;
            g[v][e.rev].cap += d;
        }
    }
    return res;
}
 
#define ID(a,b) (a*w+b)
 
char board[50][51];
 
int main(){
    int h, w; cin >> h >> w;
    FOR(i, h) cin >> board[i];
 
    const int n = 2 + 2 * h*w;
    int a, b, s;
    FOR(i, h) FOR(j, w) {
        if (board[i][j] == 'A') a = ID(i, j);
        if (board[i][j] == 'B') b = ID(i, j);
        if (board[i][j] == 'S') s = ID(i, j);
    }
 
    Graph<CostEdge> g(n);
    FOR(i, h) FOR(j, w) {
        if (board[i][j] == '#') continue;
        const int dx[] = { 0, 1, 0, -1 };
        const int dy[] = { 1, 0, -1, 0 };
        int id = ID(i, j);
        FOR(k, 4) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (0 <= ni && ni < h && 0 <= nj && nj < w && board[ni][nj] != '#') {
                int nid = ID(ni, nj);
                g.addEdge(id * 2 + 1, nid * 2, 1,1);
            }
        }
    }
 
    FOR(i, h) FOR(j, w) {
        if (board[i][j] == '#') continue;
        int id = ID(i, j);
        int cap = (id == s) ? 2 : 1;
        g.addEdge(id * 2, id * 2 + 1 , cap, 0);
    }
 
    const int src = n - 2, dst = n - 1;
    g.addEdge(src, s * 2, 2, 0);
 
    auto g2 = g;
    g2.addEdge(a * 2 + 1, dst, 1 , 0);
    int s2a = minCostFlow(g2, src, dst, 1);
    
    auto g3 = g;
    g3.addEdge(b * 2 + 1, dst, 1 , 0);
    int s2b = minCostFlow(g3, src, dst, 1);
 
    g.addEdge(a * 2 + 1, dst, 1, 0);
    g.addEdge(b * 2 + 1, dst, 1, 0);
    int s2ab = minCostFlow(g, src, dst, 2);
 
    if (s2ab != s2a + s2b) {
        puts("NA");
    } else {
        {
            int cur = 2 * a;
            auto rG = g.getRowGraph();
            while (cur != 2 * s) {
                for (auto e : rG[cur]) {
                    if (e.cost == -1 && e.cap == 1) {
                        int from = e.to;
                        cur = from - 1;
                        int i = cur / 2 / w;
                        int j = cur / 2 % w;
                        board[i][j] = 'a';
                        //fprintf(stderr,"%d %d\n",i,j);
                        break;
                    }
                }
            }
        }
        {
            int cur = 2 * b;
            auto rG = g.getRowGraph();
            while (cur != 2 * s) {
                for (auto e : rG[cur]) {
                    if (e.cost == -1 && e.cap == 1) {
                        int from = e.to;
                        cur = from - 1;
                        int i = cur / 2 / w;
                        int j = cur / 2 % w;
                        //fprintf(stderr, "%d %d\n", i, j);
                        board[i][j] = 'b';
                        break;
                    }
                }
            }
        }
        board[s / w][s%w] = 'S';
        FOR(i, h) puts(board[i]);
    }
}

E問題

条件付き期待値の式を立てて,ゲームの結果をメモ化再帰する. 1回で3~4回ゲームが出来るので,状態数をn3持って計算したいけれど,その場合計算量が n3 43 = 81 n3 くらいになって間に合わない様子,その上実装が面倒くさい. そこで1ゲーム毎に状態を持つようにする.すると状態数がn3 * 4 ,計算量がn3 * 4 * 3 = 12 *n3 になり,高速でかつ実装も楽に.

実装する時にはTLEを重要視せず実装量を重視して書いたが,定数倍に気をつけないとだめだったらしい.

http://code-festival-2014-china.contest.atcoder.jp/submissions/306554

double p[3];
double tbl[101][101][101][4];
 
double dfs(int p1, int p2, int p3,int game) {
    if (tbl[p1][p2][p3][game] >= 0) {
        return tbl[p1][p2][p3][game];
    }
    double ret = 1e300;
    bool first_stage = (game == 0); // 初回
    if (p1 > 0) {
        int ngame = game + 1;
        if (ngame >= 3) ngame = 0; //extraはないので
        double suc = dfs(p1 - 1, p2, p3, ngame);
        double ans;
        if (first_stage) {
            if (p[0] == 1.0) ans = 1 + suc;
            else ans = (1 + suc * p[0]) / p[0];
        } else {
            double fil = dfs(p1, p2, p3, 0);
            ans = suc * p[0] + fil * (1 - p[0]);
        }
        ret = min(ret, ans);
    }
    if (p2 > 0) {
        int ngame = game + 1;
        if (ngame >= 4) ngame = 0; //extraあり!
        double suc = dfs(p1, p2 - 1, p3, ngame);
        double ans;
        if (first_stage) {
            if (p[1] == 1.0) ans = 1 + suc;
            else ans = (1 + suc * p[1]) / p[1];
        } else {
            double fil = dfs(p1, p2, p3, 0);
            ans = suc * p[1] + fil * (1 - p[1]);
        }
        ret = min(ret, ans);
    }
    if (p3 > 0) {
        int ngame = game + 1;
        if (ngame >= 4) ngame = 0; //extraあり!
        double suc = dfs(p1, p2, p3 - 1, ngame);
        double ans;
        if (first_stage) {
            if (p[2] == 1.0) ans = 1 + suc;
            else ans = (1 + suc * p[2]) / p[2];
        } else {
            double fil = dfs(p1, p2, p3, 0);
            ans = suc * p[2] + fil * (1 - p[2]);
        }
        ret = min(ret, ans);
    }
 
    return tbl[p1][p2][p3][game] = ret;
}
 
int main() {
    int n[3];
    FOR(i, 3) cin >> n[i];
    FOR(i, 3) cin >> p[i];
    FOR(i,3) p[i] /= 100;
    FOR(p0, 101) {
        FOR(p1, 101) {
            FOR(p2, 101) {
                FOR(i, 4) {
                    tbl[p0][p1][p2][i] = -1;
                }
            }
        }
    }
 
    FOR(i,4) tbl[0][0][0][i] = 0;
 
    double ans = dfs(n[0], n[1], n[2], 0);
    printf("%.15lf\n", ans);
}

F問題

実は累積の積を持っておけば焼き肉が"生焼け","丁度","焼き過ぎ"になる確率を計算出来る.

時間sに網に置かれて,時間t-1の時点でもまだ網に残っている確率を求めたい. これが求められれば,上記の3つの確率が求められる.

時刻 s < a <= t-1 で,この肉が取られる確率は, 1 / {時刻aにおける肉の数} である. よって,t-1 でも肉が残っている確率は, 1 - 1 / {時刻aにおける肉の数} を s < a <= t-1 で掛けあわせたものになる.

ところで,素直に累積するとオーバーフローが怖かったので,segment treeを使って必要な部分だけを計算した.

class seg_tree {
public:
    vector<double> dat;
    int n;
 
    void init(double *d, int size) {
        n = 1;
        while (n < size) n <<= 1;
        dat.resize(2 * n - 1);
        fill(dat.begin(), dat.end(), 0);
        for (int i = 0; i < size; i++) dat[n - 1 + i] = d[i];
        for (int i = n - 2; i >= 0; i--) propagate(i);
    }
 
    void propagate(int i) {
        dat[i] = dat[i * 2 + 1] *  dat[i * 2 + 2];
    }
 
    //k番目(0-indexed)をvalに更新
    void update(int k, int val) {
        k += n - 1;
        dat[k] = val;
        while (k > 0) {
            k = (k - 1) / 2;
            propagate(k);
        }
    }
 
    //[a,b)において求めたい値を得る
    double query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
 
    //[a,b)において求めたい値を得る
    // k = 現在見ている接点の番号
    // [l,r)はkに対応した範囲
    double query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return 1.0; //範囲外
        if (a <= l && r <= b) return dat[k]; //[l,r) ⊂ [a,b)
 
        //[l,r)の一部が[a,b)に含まれる
        int md = (l + r) / 2; //[l,md),[md,r)
        int nl = k * 2 + 1, nr = nl + 1; //子の接点
        double lval = query(a, b, nl, l, md);
        double rval = query(a, b, nr, md, r);
 
        return lval * rval; //calc
    }
};
 
int n;
int s[ten(5)], t[ten(5)];
 
int main() {
    cin >> n;
    FOR(i, n) cin >> s[i] >> t[i];
    vector<int> comp;
    FOR(i, n) comp.push_back(s[i]), comp.push_back(t[i]);
    sort(comp.begin(), comp.end());
    FOR(i, n) {
        s[i] = lower_bound(comp.begin(), comp.end(), s[i]) - comp.begin();
        t[i] = lower_bound(comp.begin(), comp.end(), t[i]) - comp.begin();
    }
 
    vector<Pii> ev;
    FOR(i, n) ev.push_back(Pii(s[i], 1));
    FOR(i, n) ev.push_back(Pii(t[i], -1));
    sort(ev.begin(), ev.end());
 
    int meet = 0;
    vector<int> order;
    vector<double> db;
    for (auto e : ev) {
        if (e.second == 1) {
            order.push_back(e.first);
            db.push_back(1.0); // rem
        } else {
            //took
            db.push_back(1.0 - 1.0 / meet); // rem
        }
        meet += e.second;
    }
 
    seg_tree sg;
    sg.init(&db[0], sz(db));
 
    FOR(i, n) {
        double q = sg.query(s[i], t[i]);
        double prev = 1.0 - q;
        double rem = q * db[t[i]];
        printf("%.10lf %.10lf\n",prev, rem);
    }
 
}

スイーツ