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

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

SRM 666 div1 easy WalkOverATree

SRM トポロジカルソート dfs

問題

問題概要

木構造の情報が与えられる. すべての辺のコストを1として, コストLいないで通ることができる頂点の種類数の最大値を求める問題. ただしstart地点を0として, start,goal も通った頂点としてカウントする.

解法

一番の方針として, 頂点を巡ったあとに同じ頂点を通った戻ってくるのは無駄なので, 一番最後は行くだけ行って戻ってこないというのが考えられる. また, 1つの頂点を通るためには2回パスを通る必要があることがわかる.
これからの考察から, 任意の頂点i を最後にいくだけいく頂点として, 残りのステップ回数でほかの頂点を1つ訪れるのに2ステップ使って訪れればよい. つまり, 最後以外は2ステップで1つの頂点を訪れ, 最後だけd[i]ステップでd[i]個の頂点を巡ればいい.
実装はステップ回数が足りない時の処理や, 実際の頂点数より多く巡ったことにしないように気を付けて実装すればいい.

ミス

問題文読んでないから, For each i, parent[i] will be between 0 and i, inclusive.
を見逃して、iを順番に見ていけばトポロジカルソートされていているので, DAG上を走査するだけですべての頂点の深さを求められることに気が付かなかった. まあ, 普通にグラフの連結リストを作った後にdfsで深さ求めるだけでいいんだが. 木の上のdpなんかはそのままではDAGの順番がわからないからdfsでよくやるしね. 今回はありがたいことにトポロジカルソートした結果が与えられていた感じ.

コード

トポロジカルソートされているのを利用して, dpで深さを計算

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

class WalkOverATree{
public:
    int d[55];

    int maxNodesVisited(vector <int> parent, int L){
        int n = parent.size() + 1;
        //木構造をトポロジカルソートされている順番で並べられているので、DAG上をたどるだけでできる. 
        //For each i, parent[i] will be between 0 and i, inclusive.
        //上のような制約が書かれているので、ループで回していくだけok 
        //グラフの隣接リストを形成して、それで再帰関数で深さを求めるのもok
        d[0] = 0;
        int ret = 0;
        for (int i = 0; i < n - 1; ++i){
            d[i + 1] = d[parent[i]] + 1;
        }

        for (int i = 1; i <= n; ++i){
            int ans = 1, nokoriL = L, nokorin = n - 1;
            // printf("ans %d noL %d nn %d\n", ans, nokoriL, nokorin);
            if(d[i] <= L){
                ans += d[i]; // 最後に行きだけで稼ぐ分
                nokoriL -= d[i];
                nokorin -= d[i];
            }
            // printf("%d %d %d %d\n", d[i], ans, nokoriL, nokorin);
            ans += min(nokorin, nokoriL / 2); // 残りは1つ得るのに、行き帰りが必要
            chmax(ret, ans);
        }
        return ret;
    }
};

int main(void){
    WalkOverATree wa;
    // auto d = wa.maxNodesVisited({0, 0}, 2);
    auto d = wa.maxNodesVisited({0,0,0,0,2,4,2,3,1},1);
    printf("%d\n", d);
    return 0;
}

グラフを作ってdfsで深さを計算

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

class WalkOverATree{
public:
    int d[55];
    vector<int> G[55];
    //グラフの隣接リストを形成して、それで再帰関数で深さを求めるのもok
    void dfs(int u, int p){
        if(p != -1) d[u] = d[p] + 1;
        for(auto v : G[u]){
            if(v == p) continue;
            dfs(v, u);
        }
    }
    int maxNodesVisited(vector <int> parent, int L){
        int n = parent.size() + 1;
        rep(i, parent.size()){
            G[parent[i]].pb(i + 1);
            G[i + 1].pb(parent[i]);
        }
        d[0] = 0;
        dfs(0, -1);
        int ret = 0;
        for (int i = 1; i <= n; ++i){
            int ans = 1, nokoriL = L, nokorin = n - 1;
            // printf("ans %d noL %d nn %d\n", ans, nokoriL, nokorin);
            if(d[i] <= L){
                ans += d[i]; // 最後に行きだけで稼ぐ分
                nokoriL -= d[i];
                nokorin -= d[i];
            }
            // printf("%d %d %d %d\n", d[i], ans, nokoriL, nokorin);
            ans += min(nokorin, nokoriL / 2); // 残りは1つ得るのに、行き帰りが必要
            chmax(ret, ans);
        }
        return ret;
    }
};

int main(void){
    WalkOverATree wa;
    // auto d = wa.maxNodesVisited({0, 0}, 2);
    auto d = wa.maxNodesVisited({0,0,0,0,2,4,2,3,1},1);
    printf("%d\n", d);
    return 0;
}