hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 715 Div1 Easy: MaximumRange

TopCoder

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

+1 と -1 のみからなる数列が与えられる。 (原文は文字列だけどまあ同じことなので)

この数列の (連続とは限らない) 部分列を取ることを考える。部分列の累積和を取った時の最大と最小の差の最大値を求めよ。

解説

打ち消し合ってしまうので、プラスの要素とマイナスの要素を両方使うことにメリットはありません。よってプラスだけ・もしくはマイナスだけ使うのがよいため、プラスの個数とマイナスの個数のうち大きいほうが答えになります。

ソースコード

class MaximumRange {
    public:
    int findMax(string s) {
        int a = 0, b = 0;
        for(auto x : s) {
            (x == '+' ? a : b)++;
        }
        return max(a, b);
    }
};

ABC の B 問題でありそう。少なくとも Div1 Easy ではない・・・。

TopCoder SRM 716 Div1 Easy: ConstructLCS

TopCoder

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

以下の条件を全て満たすような '0' と '1' のみからなる文字列 A, B, C を構成せよ。

解説

ab \gt bc \gt ca を仮定すると、次のような文字列を構成すれば良いことが分かります。

  • 文字列 A → ab 文字の '0'
  • 文字列 B → ab 文字の '0' と、 bc 文字の '1'
  • 文字列 C → bc 文字の '1' と、 ca 文字の '0'

なぜ大小関係が必要かというと、これがないと色々と不都合が生じる可能性があるからです ( B と C の LCS について、 bc のほうではなく \min(ab, ca) の方が採用されるかも、などなど)

しかし実際にはこの仮定はないため、どうするかと言うと、上と同じ方法で文字列を 3 つ作り、そのうちどれを A に、どれを B に、どれを C に当てはめるかを全て試し、その都度 LCS を取ります。どれかは必ず条件を満たしているので、これで解くことが出来ます。

ソースコード

class ConstructLCS {
    public:
    int calclcs(string a, string b) {
        int dp[1010][1010] = {};
        int n = a.length(), m = b.length();
        rep(i,0,n) rep(j,0,m) {
            if(a[i] == b[j]) dp[i+1][j+1] = dp[i][j] + 1;
            else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
        }
        return dp[n][m];
    }

    string construct(int ab, int bc, int ca) {
        vector<int> ns = {ab, bc, ca};
        sort(ns.begin(), ns.end(), greater<int>());

        vector<string> strs(3);
        strs[0] = string(ns[0], '1');
        strs[1] = string(ns[0], '1') + string(ns[1], '0');
        strs[2] = string(ns[1], '0') + string(ns[2], '1');
        vector<int> perm = {0, 1, 2};
        do {
            string ra = strs[perm[0]], rb = strs[perm[1]], rc = strs[perm[2]];
            int nab = calclcs(ra, rb);
            int nbc = calclcs(rb, rc);
            int nca = calclcs(rc, ra);
            if(nab == ab && nbc == bc && nca == ca) {
                return ra + " " + rb + " " + rc;
            }
        }while(next_permutation(perm.begin(), perm.end()));
        return "";
    }
};

TopCoder SRM 716 Div1 Med (Div2 Hard): JumpDistancesOnTree

TopCoder グラフ

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

N 頂点からなる木がある。頂点 0 を起点として、いくつかの頂点に移動することを考える。集合 S が与えられるので、頂点 v_{1} \rightarrow v_{2} \rightarrow \dots \rightarrow v_{k} の順に移動したときの隣り合う要素どうしの距離 d_{1}, d_{2}, \dots, d_{k-1} の中に S の要素が全て含まれるような移動方法があるかを判定せよ。

解説

頂点 0 から行ける場所であって、頂点間の距離が S の元であるような要素を管理したいです。これをするにはどうすればよいでしょうか？

S に含まれている移動距離であるような頂点間が何であるかを把握します。これは全点対の距離を調べることで可能です。そして、その頂点間にのみ辺を貼ったグラフを新たに考え、 Union Find で連結成分を把握します。頂点 0 が属している連結成分に S の元が全てあればよいので、それを判定すれば解くことが出来ます。

Div1 では制約が大きいだけなのですが、LCA 使った全点対を書いたら O(N^{2} \log N) を通してくれないようで悲しい・・・もう少し考えます・・・

(追記) 木なら普通に dfs なりをやって全点対 O(N^{2}) だから LCA とかいらなかったですね (アホすぎる)

ソースコード

Div1 (UnionFind 省略, Div2 でもこれで通るはず)

class JumpDistancesOnTree {
    public:
    int dist[MAX_N + 10][MAX_N + 10];
    int assigned[MAX_N + 10];

    void dfs(Graph<int> &G, int cur, int orig, int par=-1, int d=0) {
        dist[cur][orig] = dist[orig][cur] = d;
        for(auto e : G[cur]) {
            if(e.to == par) continue;
            dfs(G, e.to, orig, cur, d+e.cost);
        }
    }

    string isPossible(vector<int> p, vector<int> S) {
        memset(assigned, false, sizeof(assigned));
        int N = p.size() + 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                dist[i][j] = (i == j ? 0 : INF);
            }
        }

        for(auto x : S) {
            assigned[x] = true;
        }

        Graph<int> G(N);
        for(int i=0; i<N-1; i++) {
            int u = i+1, v = p[i];
            G[u].push_back(Edge<int>(v, 1));
            G[v].push_back(Edge<int>(u, 1));
        }
        for(int i=0; i<N; i++) {
            dfs(G, i, i);
        }

        UnionFind uf;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(assigned[ dist[i][j] ]) {
                    uf.unite(i, j);
                }
            }
        }

        int ans = 0, root = uf.find(0);
        vector<int> cnt(MAX_N);
        for(int i=0; i<N; i++) {
            int idx = uf.find(i);
            if(idx != root) continue;
            for(int j=0; j<N; j++) {
                if(assigned[ dist[i][j] ]) {
                    if(!cnt[dist[i][j]]) ans++;
                    cnt[dist[i][j]] = true;
                }
            }
        }

        bool ok = (ans == (int)S.size());
        return (ok ? "Possible" : "Impossible");
    }
};