No.30 たこやき工場

No.30 たこやき工場 - yukicoder

  • TLE するかなーと思ってたら案の定 TLE した問題。予測してるなら対応せんと。
  • いまいち累積をメモ化する方法が思いつかず、頂点への入力辺が全て辿られてから次の頂点へ移動する。みたいな遅延評価でやってみた。N 以外のノードで入ってくる辺の数が 0 のものは取り除くをしないとWAになってしまったけど。
  • solve_memo の方が解説にあった手法。次同じような問題をとくときはこっちのような実装をしよう。y を固定してやるのがミソなのだと思った。
class TakoyakiFactory {
public:
    struct Edge {
        Edge(int t, ll c) : to(t), cost(c) {}
        int to;
        ll  cost;
    };
    void solve_dfs(void) {
            int N,M;
            cin>>N>>M;
            // 木を逆にたどればよい
            // dfs + 遅延評価
            vector<vector<Edge>> tree(N);
            vector<int> ins(N,0); // 入ってくる辺の数

            REP(i,M)
            {
                int p,q,r;
                cin>>p>>q>>r;
                --p;
                --r;
                tree[r].emplace_back(p,q);
                ++ins[p];
            }
            // N 以外のノードで入ってくる辺の数が 0 のものは取り除く
            REP(i, N-1)
            {
                if (ins[i] > 0)
                    continue;
                for (auto e : tree[i])
                    --ins[e.to];
            }

            vector<ll>  sum(N,0);
            vector<ll>  cache(N,0);
            vector<int> vis(N,0);
            function<void(int,ll)> dfs = [&](int x, ll n) {
                ++vis[x];
                cache[x] += n;
                if (vis[x] < ins[x])
                    return;
                // 入ってくる辺がたまったら次の辺を見る
                if (tree[x].empty())
                {
                    sum[x] = cache[x];
                    return;
                }
                for (auto e : tree[x])
                    dfs(e.to, cache[x]*e.cost);
            };
            dfs(N-1,1);
            REP(i,N-1)
                cout<<sum[i]<<endl;
    }
    void solve_memo() {
            int N,M;
            cin>>N>>M;
            vector<vector<Edge>> tree(N);
            REP(i,M)
            {
                int p,q,r;
                cin>>p>>q>>r;
                --p;
                --r;
                tree[r].emplace_back(p,q);
            }
            vector<vector<ll>>   dp(N,vector<ll>(N,-1));
            // x を 1 個作るのに必要な y の個数を返す
            function<ll(int,int)> dfs = [&](int x, int y) {
                ll res = 0;
                if (dp[x][y] >= 0)
                    return dp[x][y];
                if (tree[x].empty()) // 葉に到達した
                    return (x==y)? 1LL : 0LL; // y が葉でなければ 0 (購入の必要なし)
                for (auto e : tree[x])
                    res += (dfs(e.to, y) * e.cost);
                return dp[x][y] = res;
            };
            REP(i,N-1)
                cout<<dfs(N-1,i)<<endl;
    }
    void solve() {
            solve_memo();
    }
};