WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Statement訳あなたは0からN-1までの番号が付けられたN個のコンピュータを持っている。これらは1つのネットワークとして繋がっている。ネットワークの構造はツリー状になっている。あなたはその状態の説明としてint配列のparentとdistが与えられる。これらint配列は、ちょうどN-1個の要素を持つ。iを0からN-2としたとき、i+1番目のコンピュータはparent[i]番目のコンピュータとケーブルで繋がれており、その長さはdist[i]である。maxDistが与えられる。同じネットワーク上にある、任意の2つのコンピュータの距離はmaxDistを超えてはならない。(2つのコンピュータの距離はそれらを繋ぐケーブルの長さの合計とする)もし、現在のネットワークが上記の性質を満たしていなければ、あなたはそれをより小さないくつかのネットワークに分割しなくてはならない。形式的に言えば、あなたはまず小さなネットワークの数Kを決め、それからK個のネットワークの1つにそれぞれのコンピュータを配置する必要がある。それは下記のような性質を満たさなければならない。K個の新しいネットワークは元のツリーのサブツリーである。新しいネットワークの直径は、大きくてもmaxDistでなければならない。上記のような性質を満たすように、元のネットワークをK個の新しいネットワークに分割したときの、最小のKを返せ。simezi_tanの日記コチラを参考にしました。_)mdfsで木DPする。頂点vを根とするサブツリーで、使える長さがdとしたときの、ケーブルを切る最小の数サブツリーには使えるケーブルの長さに以下のような2つの制限がある。maxDist)としてやる。c))としてやればよい。問題は2で、サブツリー上においても、直径はmaxDist以下としなくてはならない。サブツリー内の直径は、子供の末端までの距離上位2つの合計であるため、一番長い距離を使う子供と、その距離を決め打ちしてやる。すると他の子供の使える距離がでてくるので、1と2の小さいほうをdとしてdfsを呼べばよい。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。